Number theory

If a₁, a₂, ..., a_n are nonzero positive integers, then the equation a₁ x₁ + a₂ x₂ + ... + a_n x_n = c has infinite integral solutions if (a₁, a₂, ..., a_n) divides c, otherwise it has no solutions (incomplete)

integer representations

Basis Representation Theorem

balanced ternary expansion

prime numbers

if p is prime and p|αβ, then p|α or p|β

if p is prime and p∤α, then (p, α) = 1

any integer is either a prime or a product of primes

fundamental theorem of arithmetic

if n is composite then there is a prime divisor ≤ √n

all composite integers can be expressed as a product of two coprime integers

there are infinite number of primes

there are infinite primes of the form 4k+3

there are infinite primes of the form 3k+2

if p is a prime ≥ 5, then (p²-1)|24

no prime can be expressed as a⁴ - b⁴

for any positive integer n, there are at least n consecutive composite integers

if 2^p-1 is prime, then p is prime

if n > 1 and aⁿ - 1 is prime, then a=2

if aⁿ+1 is an odd prime, then a is even and n is a power of 2

if n²+1 is prime, then n² = 4k

a powerful number is a product of a square and a cube

any integer greater than 6 can be represented as a sum of two relatively prime integers

if a^k|b^k then a|b

if p is prime and p|aⁿ then p|a

If the smallest prime p of the positive integer n exceeds n^1/3, then n/p must be prime or 1

every integer greater than 11 is the sum of two composite integers

if [2n/3 ≤ p < n] then [p∤_2nC_n]

p₁p₂...p_t < 4ⁿ where p_t ≤ n (incomplete)

Bertrand's postulate (incomplete)

If p_n is the nth prime, then p_n ≤ 2ⁿ

every positive integer n ≥ 7 is the sum of disctinct primes (incomplete)

Dirichlet's theorem on arithmetic progressions (incomplete)

root of xⁿ+c_n-1x^n-1+...+c₁x+c₀ is either an integer or an irrational

log_pb is irrational, where p is prime and b is a positive integer that is not a power of p

every prime divisor of a composite Fermat number F_n is of the form 2ⁿ⁺²k+1 (incomplete)

F₀F₁...F_n-1 + 2 = F_n

Fermat numbers F_n and F_m are coprime when n ≠ m

exactly divides

[p^a ∥ m] ∧ [p^b ∥ n] ⇒ [p^min(a,b) ∥ m+n]

[p^a ∥ m] ∧ [p^b ∥ n] ⇒ [p^a+b ∥ mn]

[p^a ∥ m] ⇒ [p^an ∥ m^n]

Legendre's formula

lower bound for Legendre's formula

more gcd

(α, ε) = 1 ∧ (β, ε) = 1 ⇒ (αβ, ε) = 1

(α, β) = 1 ⇒ (αβ, ε) = (α, ε) * (β, ε)

(α, β) = 1 ∧ ε|(α+β) ⇒ (α, ε) = (β, ε) = 1

(α, β) = δ ⇒ (α/δ, β/δ) = 1

(m, β) = 1 ⇒ (mα, β) = (α, β)

(α, β) = 1 ∧ αβ = cⁿ ⇒ ∃x, y ∈ Z⁺ such that α = xⁿ ∧ β = yⁿ

if α is odd, then gcd(α, α-2) = 1

(α₁, α₂, α₃, ..., α_n) ⇒ ((α₁, α₂), α₃, ..., α_n)

(α, β, ε) = 1 ⇒ (αβ, ε) = (α, ε)(β, ε)

if (x, y) divides (x + y), then there are infinite values of x and y

m * (α₁, α₂, ...) = (mα₁, mα₂, ...)

(α, β) = δ ∧ (α, ε) = δ ⇒ (α, β, ε) = δ

(α, β) = 1 ⇒ (α^m, βⁿ) = 1

(α, β) = (α + kβ, β) where k is any integer

(α, β) = 1 ⇒ (α+β, α-β) is ≤ 2

(α, β) = 1 ⇒ (α²+β², α+β) is ≤ 2

(α, β) = 1 ⇒ (α + β, αβ) = 1

[(a,b) = (c,d) = 1 ∧ a/b + c/d ∈ Z] ⇒ b = d

6n-1, 6n+1, 6n+2, 6n+3 and 6n+5 are pairwise relatively prime

Lamé's theorem (incomplete)

lcm

gcd(α, β) * lcm(α, β) = αβ

[ca, cb] = c[a, b]

[a, b, c] = [[a, b], c]

[a, b]|c ⟺ a|c and b|c

a,b ∈ N⁺ ⇒ [a, b] = cd where c|a, d|b and (c, d) = 1

(a, b) = (a + b, [a, b]) where a, b ∈ Z⁺

[(a, b), c] = ([a, c], [b, c]) and ([a, b], c) = [(a, c), (b, c)] where a, b, c ∈ Z⁺

[a, b, c] = abc(a,b,c)/(a,b)(a,c)(b,c) where a, b, c ∈ Z⁺

[(a, b), (a, c), (b, c)] = ([a, b], [a, c], [b, c]) where a, b, c ∈ Z⁺

modular arithmetic

(α ≡ β mod M) ∧ (ε ≡ δ mod M) ⇒ (α + ε ≡ β + δ mod M)

(α ≡ β mod M) ∧ (ε ≡ δ mod M) ⇒ (αε ≡ βδ mod M)

(α ≡ β mod M) ∧ (ε ≡ δ mod M) ∧ ε|α ∧ δ|β ⇒ (α/ε ≡ β/δ mod M)

(α ≡ β mod M) ∧ (n|M) ⇒ (α ≡ β mod n)

if c is an odd integer, then (c² ≡ 1 mod 4) and (c² ≡ 1 mod 8)

(c ∈ Z) ∧ (α ≡ β mod M) ⇒ (cα ≡ cβ mod cM)

α ≡ β mod M ⇒ (α/d ≡ β/d mod M/d) if d divides them

(εα ≡ εβ mod M) ⟺ (α ≡ β mod M/(ε, M))

(α ≡ β mod M) ⇒ (β, M) = (α, M)

if n is a positve integer and (n ≡ 3 mod 4), then n cannot be written as a sum of two square integers

if (α ≡ β mod M) and (α ≡ β mod N) then (α ≡ β mod [M, N])

if gcd(M, N) = 1, then (α ≡ β mod M) ∧ (α ≡ β mod N) ⟺ α ≡ β mod MN

if n is odd and (3 ∤ n), then (n² ≡ 1 mod 24)

if (α, m) = 1 and if {r₁, ..., r_φ(m)} is a reduced residue system (modulo m), then {αr₁, ..., αr_φ(m)} is also a reduced residue system

Euler's theorem

Fermat's little theorem

Freshman's dream

ax ≡ b mod m has a solution if and only if gcd(a, m)|b

solution of ax ≡ b mod m (if gcd(a, m)|b)

existence and uniqueness of modular inverse if gcd(a, m) = 1

if p is prime ∧ (a² ≡ b² mod p) ⇒ a ≡ ±b mod p

if p is prime ∧ (a² ≡ a mod p^k) ⇒ (a ≡ 0) or (a ≡ 1)

if p is an odd prime ∧ (a² ≡ 1 mod p^k) ⇒ a ≡ ±1 mod p^k

[α ≡ ±1 mod p where p is prime] ⟺ [α is its own inverse] (assume α is positive)

if p is prime ∧ (a^p ≡ b^p mod p) ∧ (p ∤ a) ∧ (p ∤ b) ⇒ a^p ≡ b^p mod p²

If (α, n) = 1 then {β, α+β, 2α+β, ..., (n-1)α+β} forms a complete system of residues modulo n

divisibility rules

an integer is divisible by 3 or 9 if the sum of its digits is divisible by 3 or 9 respectively

an integer is divisible by 7, 11 or 13 if the alternating sum of blocks of three digits is divisible by 7, 11 or 13 respectively

an integer is divisible by 11 if the integer obtained by alternately adding and substracting the digits is divisible by 11

if d|b, then (a_k ... a₁a₀)_b is divisible by d^j if and only if (a_j-1 ... a₁a₀)_b is divisible by d^j

if d|(b-1), then d|(a_k ... a₁a₀)_b if and only if d|(a_k + ... + a₁ + a₀)

if d|(b+1), then d|(a_k ... a₁a₀)_b if and only if d|((-1)^ka_k + ... + a₂ - a₁ + a₀)

more congruence

1 + 2 + 3 + ... + (n-1) ≡ 0 mod n if and only if n is odd

1² + 2² + 3² + ... + (n-1)² ≡ 0 mod n ⇒ n ≡ ±1 mod 6

1³ + 2³ + 3³ + ... + (n-1)³ ≡ 0 mod n ⇒ n is not congruent to 2 mod 4

least positive residue of 2^a-1 mod 2^b-1 is 2^r-1 where r is the least positive residue of a mod b

(2^a-1, 2^b-1) = 2^(a,b)-1

(2^a-1, 2^b-1) = 1 ⟺ (a, b) = 1

Wilson's theorem

converse of Wilson's theorem

Let p be prime, then 2(p-3)! ≡ -1 mod p

solution to x² ≡ -1 mod p (incomplete)

if p ≡ 3 mod 4, then ((p-1)/2)! ≡ ±1 mod p

Chinese remainder theorem

[x ≡ a₁ mod m₁ ∧ x ≡ a₂ mod m₂] has a solution iff (m₁, m₂)|(a₁-a₂)

General Chinese remainder theorem

Hensel's lemma (incomplete)

arithmetic functions

If f is a multiplicative function, then [F(n) = ∑_{d|n, d>0} f(d)] is also a multiplicative function

The Euler phi function is multiplicative

The formula for φ(p^a)

The formula for φ(n)

φ(n) ≥ √(n/2)

if n is composite, φ(n) ≤ n - √n

if n is even, then φ(2n) = 2φ(n)

if n is odd, then φ(2n) = φ(n)

φ(n^j) = n^j-1 φ(n)

if m|n, then φ(m)|φ(n)

if m|n, then φ(mn) = m φ(n)

∑_{d|n, d>0} φ(d) = n