discrete mathematics

divisibility

if α|β and α|ε, then α|(mβ + nε)

if α|β and ε|δ, then αε|βδ

3|n³-n

5|n⁵-n

4n²+4n is divisible by 8 for all n

smallest positive linear combination of α and β = gcd(α, β)

every linear combination of α and β is a multiple of gcd(α, β), and vice versa

gcd(α, β) = gcd(β, α mod β); why the euclidean algorithm works

if α₁|b, α₂|b and gcd(α₁, α₂) = 1 ⇒ α₁α₂|b

if ε|αβ and gcd(ε, α) = 1, then ε|β

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

if m|n, then (a^m-b^m)|(aⁿ-bⁿ)

prime numbers

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

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

there are infinite number of primes

all primes are of the form 4k+1 or 4k+3

there are infinite primes of the form 4k+3

there are infinite primes of the form 3k+2

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

Legendre's formula

lower bound for Legendre's formula

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

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

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

more gcd

if gcd(α, ε) = 1 and gcd(β, ε) = 1, then gcd(αβ, ε) = 1

if gcd(α, β) = 1, then gcd(αβ, ε) = gcd(α, ε) * gcd(β, ε)

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

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

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

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

if gcd(α, β) = 1, then gcd(α+β, α-β) is either 1 or 2

if gcd(α, β) = δ and gcd(α, ε) = δ, then gcd(α, β, ε) = δ

if gcd(α, β) = 1 then gcd(α^m, βⁿ) = 1

if gcd(α, β) = 1 then gcd(α + β, αβ) = 1

lcm

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

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

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

modular arithmetic

(α ≡ β mod M and ε ≡ δ mod M) ⇒ α + ε ≡ β + δ mod Μ

(α ≡ β mod M and ε ≡ δ mod M) ⇒ αε ≡ βδ mod Μ

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

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

Euler's theorem

Fermat's little theorem

Freshman's dream

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

Wilson's theorem

x² ≡ 1 mod p ⇒ x ≡ +1 or -1 mod p

x² ≡ -1 mod p is solvable if and only if p = 2 or p ≡ 1 mod 4

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

Chinese remainder theorem

factorials, permutations and combinations

0! = 1

the formula of permutations

the formula of combinations

using combinations to find a number in the Pascal's triangle

number of ways of arranging n objects with k identical objects

sequence and series

finding a term in an arithmetic sequence

finding a term in a geometric sequence

the sum of an arithmetic series

the sum of a geometric series with finite terms

the sum to infinity of a geometric series

sum of the first n positive integers

sum of the squares of the first n positive integers

sum of the cubes of the first n positive integers

showing that the harmonic series diverges