Number Theory

The integers up close: divisibility and primes, gcd via the Euclidean algorithm, modular arithmetic and congruences, and the classical proofs.

Foundations

Divisibility & Primes — The division algorithm, primality, and counting divisors.
Euclidean Algorithm — gcd by repeated division; coprimality and the gcd·lcm identity.
Bézout's Identity — (a,b) = ax + by — the gcd as an integer combination.
Fundamental Theorem of Arithmetic — Every integer > 1 has a unique prime factorization.

Modular Arithmetic — Clock arithmetic — a n keeps only the remainder.
Linear Congruences — Solve ax b n with inverses and the gcd condition.
Fermat's Little Theorem — a^p-1 1 p for prime p — modular arithmetic's most useful identity.

√2 is Irrational — Square it, factor it, contradict yourself — the classic proof by descent.
Infinitely Many Primes — Euclid's trick: N = p_1 p_2 p_n + 1 is coprime to every p_i.

Euler's Totient Function φ(n) — Count the units modulo n with the prime-power product formula.
Euler's Totient Theorem — Compute huge powers mod n by reducing exponents modulo (n).
Wilson's Theorem — (p-1)! -1 p characterizes the primes.
Order of an Element & Primitive Roots — Multiplicative order, its divisibility of (n), and generators of the units.
Quadratic Residues & Legendre Symbol — Which residues are squares mod p, via the Legendre symbol.
Quadratic Reciprocity — Legendre symbols, Euler's criterion, and Gauss's reciprocity law.
Divisor Functions τ(n) and σ(n) — Counting and summing divisors from the prime factorization.
Möbius Function & Inversion — The Möbius function and recovering f from its divisor sums.
Perfect Numbers & Mersenne Primes — The condition (n) = 2n and the Euclid–Euler theorem.