Congruences

Builds on

Required prerequisites, all the way down: 13

You will learn to

• Prove that congruence modulo n is an equivalence relation compatible with + and ×.
• Solve linear congruences ax ≡ b (mod n) and systems of congruences using the Chinese remainder theorem.
• Prove Fermat's little theorem and Euler's theorem and use them to compute large powers modulo n.

Definition

• a ≡ b (mod n) means that n divides a − b.
• Euler's totient φ(n) is the number of integers in {1, …, n} that are coprime to n.
• An inverse of a modulo n is an integer b with ab ≡ 1 (mod n).

Theorem

• a has an inverse modulo n if and only if gcd(a, n) = 1.
• Chinese remainder theorem: if m and n are coprime, the system x ≡ a (mod m), x ≡ b (mod n) has a solution, unique modulo mn.
• Fermat: if p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p).
• Euler: if gcd(a, n) = 1 then a^φ(n) ≡ 1 (mod n).
• Wilson: (p − 1)! ≡ −1 (mod p) for every prime p.

Common misconceptions

• Cancelling a factor that is not coprime to n: 2 · 3 ≡ 2 · 9 (mod 12), but 3 ≢ 9 (mod 12).
• Assuming the converse of Fermat's theorem: the Carmichael number 561 = 3 · 11 · 17 satisfies a^560 ≡ 1 (mod 561) for every a coprime to 561.

Leads to

Optional discoveries

• Quotient groups and quotient rings The congruence classes modulo n are the elements of the quotient ring ℤ/nℤ, and reduction mod n is the quotient homomorphism ℤ → ℤ/nℤ.Wonder Trail →
• Groups (ℤ/nℤ, +) is the cyclic group of order n, and the invertible classes form the group of units of order φ(n); Euler's theorem then follows from Lagrange's theorem.Wonder Trail →
• Rings, ideals and fields ℤ/nℤ is a finite commutative ring, and it is a field exactly when n is prime.Wonder Trail →
• Fields and Galois theory For p prime, ℤ/pℤ is the field 𝔽_p; every finite field has prime-power order pⁿ, and there is exactly one of each such order up to isomorphism.Wonder Trail →
• Algebraic number theory In rings of integers of number fields one works modulo ideals rather than numbers; Kummer's ideal numbers and Dedekind's ideals grew out of attempts to restore unique factorisation.Wonder Trail →
• ← Integers
• ← Clock arithmetic: remainders and modular arithmetic

Further reading

• Kenneth Ireland and Michael Rosen, A Classical Introduction to Modern Number Theory
• Carl Friedrich Gauss, Disquisitiones Arithmeticae (1801)