Number Theory

The study of integers and their properties.

• Divisibility — a | b
• Division Algorithm — a = bq + r
• Greatest Common Divisor — gcd(a,b)
• Least Common Multiple — lcm(a,b)
• Euclidean Algorithm — Compute gcd
• Bézout's Identity — ax + by = gcd(a,b)
• Prime Number — p > 1, only 1 and p divide
• Composite Number — Not prime, not 1
• Sieve of Eratosthenes — Find primes
• Infinitude of Primes — Euclid's proof
• Prime Factorization — Product of primes
• Fundamental Theorem of Arithmetic — Unique factorization
• Congruence — a ≡ b (mod n)
• Modular Arithmetic — Arithmetic mod n
• Residue Class — [a] = {a + kn}
• Multiplicative Inverse (Mod) — ax ≡ 1 (mod n)
• Fermat's Little Theorem — a^(p-1) ≡ 1 (mod p)
• Euler's Theorem — a^φ(n) ≡ 1 (mod n)
• Euler's Totient Function — φ(n) = count of coprime
• Chinese Remainder Theorem — Solve system of congruences
• Quadratic Residue — Square mod p
• Legendre Symbol — (a/p)
• Quadratic Reciprocity — (p/q)(q/p) = (-1)^...