Topic 07 — CS 70 Discrete Mathematics
Modular Arithmetic &
Inverses
Clock arithmetic, the GCD condition for inverses, Euclid’s lightning‑fast algorithm, and why (n‑1) is its own inverse. Plus party‑trick last digits.
⏰ Clock math — congruence
x ≡ y (mod m) ⇔ m | (x−y) ⇔ x = y + k·m for some integer k.
On a 12‑hour clock, 16:00 is the same as 4:00 because 16−4 = 12.
Feb 11, 2025 is Tuesday. What day is Feb 11, 2105?
80 years = 60 regular + 20 leap. 365≡1 (mod7), 366≡2 (mod7).
Offset = 2 + 60·1 + 20·2 = 102 ≡ 4 (mod7) → Tuesday + 4 = Saturday.
(We reduced intermediate numbers: 60≡4, 20≡6 → 2 + 1·4 + 2·6 = 18 ≡4)
➕ Modular operations
If a≡c (mod m) and b≡d (mod m) then
a+b ≡ c+d (mod m), a·b ≡ c·d (mod m), aᵏ ≡ cᵏ (mod m).
a = c + km, b = d + jm ⇒ ab = cd + m(…). ∎
🔄 Inverses & gcd
y is an inverse of x modulo m if x·y ≡ 1 (mod m).
Example: 2·4 = 8 ≡ 1 (mod7) ⇒ 2 is inverse of 4 (mod7).
x has an inverse modulo m iff gcd(x, m) = 1.
Consider S = {0·x, 1·x, …, (m−1)·x} mod m. If all distinct, one must be 1 (since m elements among m classes). Distinctness: assume a·x ≡ b·x ⇒ (a−b)x = multiple of m. Because gcd(x,m)=1, m | (a−b). But 0 ≤ a,b < m ⇒ a=b. So distinct → 1 appears. ∎
• 2 mod 5: 2·3=6≡1 → inverse is 3.
• 4 mod 6: S = {0,4,2,0,4,2} → no 1 → no inverse (gcd(4,6)=2).
• 5 mod 6: S = {0,5,4,3,2,1} → 5 is its own inverse (gcd=1).
True: (A) 2⁻¹≡3 mod5; (B) (n−1) is its own inverse mod n; (F) 4⁻¹≡4 mod5 (since 4·4=16≡1). False: (C) 0.5 meaningless; (D) 4 ≡ -1 mod5, but (-1)·(-1)=1 ⇒ 4 is its own inverse (true fact, but (D) misworded).
🔁 Bijection viewpoint
If gcd(a,m)=1, then f(x) = a·x mod m is a bijection on {0,…,m−1}.
(one‑to‑one because of the distinctness argument, same size → onto)
| a | m | image | bijection? |
|---|---|---|---|
| 3 | 4 | {0,3,2,1} | ✅ |
| 2 | 4 | {0,2,0,2} | ❌ |
Poll: bijection only when gcd(a,n)=1. (C) is true; (B) gcd=2 ⇒ image only even residues.
🚫 Only if (gcd > 1 ⇒ no inverse)
Let d = gcd(x,m) > 1. Assume x·y ≡ 1 (mod m) ⇒ x·y = 1 + k·m.
Write x = d·n, m = d·ℓ ⇒ d·n·y = 1 + k·d·ℓ ⇒ d(n·y − k·ℓ) = 1.
Left side multiple of d>1, right side 1 ⇒ impossible. ∎
⚡ Euclid’s GCD algorithm
gcd(x, y) = gcd(y, x mod y).
Let r = x mod y = x − ⌊x/y⌋·y. Any divisor of x and y also divides r; any divisor of y and r also divides x. So the set of common divisors is identical → gcd same. ∎
gcd(700,568) → gcd(568,132) → gcd(132,40) → gcd(40,12) → gcd(12,4) → gcd(4,0) = 4.
(each step: second argument becomes remainder)
📈 Runtime & number size
Value vs size
1,000,000 has value 10⁶, size ≈ 20 bits. (Poll: (A),(C) correct)
Brute force gcd
test up to y/2 → exponential in bit length: 2ⁿ⁻¹ steps.
Euclid
O(n) divisions where n = #bits. Reason: first arg halves every two calls.
Case 1: y < x/2 → next first arg = y < x/2.
Case 2: y ≥ x/2 → then mod(x,y) = x−y ≤ x−x/2 = x/2, and this becomes first arg after two steps. ∎
So for 100‑bit numbers, Euclid uses ~200 divisions vs. 2¹⁰⁰ brute force.
gcd(700,568) = gcd(568,132) ✅ (Lemma)
gcd(8,3) = gcd(3,2) ✅ (3 = 8 mod 5? 8 mod 3 =2) yes.
gcd(8,3)=1 ✅, gcd(4,0)=4 ✅.
🎉 Party tricks – last digits
11 ≡ 1 (mod10) ⇒ 11ᵏ ≡ 1 ⇒ last digit 1.
9 ≡ −1 (mod10) ⇒ (−1)⁹⁹⁹⁹ = −1 ≡ 9 ⇒ last digit 9.
Cycle of 3 mod10: 3,9,7,1 repeats every 4. 641 mod4 = 1 ⇒ 3¹ ≡ 3 ⇒ last digit 3.
🧩 Modular potpourri (DIS 3a)
∃ x s.t. x≡3 (mod16) and x≡4 (mod6)?
x=3+16k ⇒ mod6: 3+16k ≡ 3+4k ≡4 ⇒ 4k≡1 mod6. gcd(4,6)=2 does not divide 1 → no solution.
2x≡4 ⇒ 2x−4 = 12k ⇒ x−2 = 6k ⇒ x≡2 (mod6). But (mod12) is stronger: e.g. x=8 gives 16≡4 (mod12) but 8≠2 (mod12). So first ⇔ false; correct is x≡2 (mod6).
Inverses – concrete checks
| a,m | inverse? | check |
|---|---|---|
| 3 inverse of 5 mod14 ? | ✅ | 5·3=15≡1 mod14 |
| 3 inverse of 5 mod10 ? | ❌ | 5·3=15≡5 ≠1 |
| 3+14n inverse of 5 mod14 ? | ✅ | 5(3+14n)=15+70n≡1+0≡1 |
🌀 Fibonacci gcd = 1
Base: F₁=1, F₀=0 → gcd=1.
Step: gcd(Fₙ, Fₙ₋₁) = gcd(Fₙ₋₁, Fₙ mod Fₙ₋₁) = gcd(Fₙ₋₁, Fₙ₋₂) because Fₙ = Fₙ₋₁+Fₙ₋₂.
By IH gcd(Fₙ₋₁, Fₙ₋₂)=1. ∎
📌 Summary
• aᵏ mod m: reduce base mod m, exponent separately (not mod m)
• Inverse exists ⇔ gcd(a,m)=1.
• Euclid’s algorithm: O(log m) divisions, proof via size halving.
• Extended Euclid (Thursday) actually computes the inverse.