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)

d|α ∧ d|β ∧ d|M ∧ α ≡ β mod M ⇒ (α/d ≡ β/d mod M/d)

(εα ≡ εβ 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 (α ≡ β mod M), (α ≡ β mod N) and gcd(M, N) = 1, then (α ≡ β 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)

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

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 divisble by 3 if the sum of its digits is divisible by 3

an integer is divisble by 7 if the alternating sum of blocks of three from is divisible by 7

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

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

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 if p = 2 or p ≡ 1 mod 4

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

Chinese remainder theorem

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