14.1 Congruences

a ≡ b (mod m) iff m | (a − b), equivalently a and b leave the same remainder on division by m. Congruence mod m is an equivalence relation on Z (Unit 1) whose classes are the residues {0, 1, ..., m − 1} = Z_m.

Arithmetic rules. If a ≡ b and c ≡ d (mod m), then:

The reduce-early trick: (38 × 41) mod 7 = (3 × 6) mod 7 = 18 mod 7 = 4 — never carry big numbers when their residues suffice.

14.2 Worked Example 1 — Fast Modular Exponentiation

Compute 3^13 mod 7 by repeated squaring (13 = 8 + 4 + 1 = 1101 in binary):

3^1 ≡ 3          (mod 7)
3^2 ≡ 9  ≡ 2     (mod 7)
3^4 ≡ 2^2 ≡ 4    (mod 7)
3^8 ≡ 4^2 ≡ 16 ≡ 2 (mod 7)
3^13 = 3^8 · 3^4 · 3^1 ≡ 2 · 4 · 3 = 24 ≡ 3 (mod 7)

Only 5 multiplications instead of 12, and intermediate values never exceed m^2. This O(log k) algorithm is the computational heart of RSA and Diffie–Hellman, where exponents have hundreds of digits.

14.3 Linear Congruences and Modular Inverses

a·x ≡ b (mod m) has a solution iff gcd(a, m) | b; if g = gcd(a, m) divides b there are exactly g solutions mod m. When gcd(a, m) = 1, the number a has a unique inverse a⁻¹ with a·a⁻¹ ≡ 1 (mod m), found by extended Euclid (Lesson 13).

Worked Example 2 — solve 7x ≡ 3 (mod 26).

1. gcd(7, 26) = 1, so a unique solution exists. Find 7⁻¹ mod 26 by extended Euclid:

26 = 3·7 + 5; 7 = 1·5 + 2; 5 = 2·2 + 1.

2. Back-substitute: 1 = 5 − 2·2 = 5 − 2(7 − 5) = 3·5 − 2·7 = 3(26 − 3·7) − 2·7 = 3·26 − 11·7.
3. So −11·7 ≡ 1 (mod 26), i.e., 7⁻¹ ≡ −11 ≡ 15 (mod 26). Check: 7·15 = 105 = 4·26 + 1 ✔.
4. x ≡ 15·3 = 45 ≡ 19 (mod 26). Check: 7·19 = 133 = 5·26 + 3 ✔.

(Mod 26 is no accident — this is exactly how the decryption key of an affine cipher c = (7p + k) mod 26 is derived.)

Why division is dangerous: 6 ≡ 36 (mod 10), but dividing by 2 gives 3 ≡ 18 (mod 10), which is false. Cancelling a factor c is legal only when gcd(c, m) = 1 — otherwise the modulus must be divided too: 3 ≡ 18 (mod 5) is true.

14.4 Fermat's Little Theorem

If p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p). (Equivalently a^p ≡ a (mod p) for all a.)

Worked use — collapse a huge exponent: compute 7^222 mod 11. Since 11 is prime and 11 ∤ 7, we know 7^10 ≡ 1 (mod 11). Write 222 = 22·10 + 2:

7^222 = (7^10)^22 · 7^2 ≡ 1^22 · 49 ≡ 49 ≡ 5 (mod 11).

FLT also gives inverses instantly: a⁻¹ ≡ a^(p−2) (mod p). It underlies the Fermat primality test (pick random a, check a^(n−1) ≡ 1 mod n) and its industrial-strength refinement Miller–Rabin, which is how OpenSSL finds the large primes for your TLS connections.

14.5 Applications: Hashing, Check Digits, and RSA

1. Hashing: h(k) = k mod m; choosing m prime and far from powers of 2 spreads structured keys (Lesson 13). Congruence classes are the buckets.
2. Check digits: ISBN-10 requires Σ (i · x_i) ≡ 0 (mod 11) over positions i = 1..10 — it catches every single-digit error and every transposition, because 11 is prime.
3. Linear congruential generators: x(n+1) = (a·x(n) + c) mod m produce pseudo-random streams; period analysis is pure congruence theory.
4. RSA sketch: choose primes p, q; n = p·q; pick e coprime to (p−1)(q−1); compute d = e⁻¹ mod (p−1)(q−1) by extended Euclid. Encryption c = m^e mod n, decryption m = c^d mod n — correctness is Fermat/Euler, feasibility is fast exponentiation, and security is the difficulty of factoring n.

14.6 Common Mistakes

• Cancelling a common factor without checking gcd with the modulus (14.3).
• Applying Fermat with a composite modulus, or to a when p | a.
• Reporting negative residues: −11 mod 26 should be normalized to 15.

🎯 Exam Focus

1. Define congruence modulo m and prove it is an equivalence relation on Z.
2. Compute 5^117 mod 19 using Fermat's little theorem, showing each reduction.
3. Solve 9x ≡ 6 (mod 21). How many incongruent solutions exist mod 21? (Hint: gcd = 3.)
4. Find 11⁻¹ (mod 26) by the extended Euclidean algorithm and verify it.
5. Compute 2^90 mod 13 by repeated squaring, listing every intermediate square.
6. Explain why hash tables prefer prime moduli, using congruence classes of keys of the form k = 4j.