discrete mathematics

divisibility

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

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

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

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

ε|αβ and gcd(ε, α) = 1, ⇒ ε|β

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

m|n ⇒ (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) ∧ (ε ≡ δ mod M) ⇒ (α + ε ≡ β + δ mod M)

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

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

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

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), (α ≡ β 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)

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

If p is prime ∧ (a² ≡ a mod p) ⇒ (a ≡ 0) or (a ≡ 1)

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

divisibility rules

an integer is divisible by 2 if its last digit is divisible by 2

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

factorials, permutations and combinations

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

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