Day 73 — Modular arithmetic

Day 73 — Modular arithmetic

Stage VII · concept day
Goal: Master \(a\equiv b\pmod n\); prove ring operations are well-defined; cancel when coprime; use complete residue systems; solve linear congruences \(ax\equiv b\pmod n\).

Why this matters

Congruences are the mathematics of clocks, hash buckets, cyclic buffers, checksums, and every crypto-literacy story that uses “work modulo \(n\).” Fluent modular arithmetic is the language Days 74–78 refine (inverses, Fermat/Euler, CRT).

Note

No labs. Pure arithmetic and proofs. Programming % is a reminder, not the lesson — and languages disagree on negative remainders.

---

Theory

Congruence

Definition. Fix an integer \(n>0\) (the modulus). Integers \(a,b\) are congruent modulo \(n\), written \[ a\equiv b\pmod{n}, \] if \(n\mid(a-b)\), i.e. \(a-b=nk\) for some \(k\in\mathbb{Z}\).

Equivalent characterizations.

1. \(n\mid(a-b)\).
   
2. \(a\) and \(b\) leave the same remainder on division by \(n\).
   
3. \(a=b+nk\) for some \(k\in\mathbb{Z}\).

Proposition (equivalence relation). \(\equiv\pmod n\) is reflexive, symmetric, and transitive on \(\mathbb{Z}\).

Proof. Reflexive: \(n\mid 0\). Symmetric: if \(n\mid(a-b)\) then \(n\mid(b-a)\). Transitive: if \(n\mid(a-b)\) and \(n\mid(b-c)\) then \(n\mid(a-c)\) by linear combinations.

Residue classes and complete residue systems

The residue class of \(a\) modulo \(n\) is \[ [a]_n = \{a+nk:k\in\mathbb{Z}\}. \] Often written \(\overline{a}\) or \(a+n\mathbb{Z}\). There are exactly \(n\) distinct classes, represented by \(\{0,1,\ldots,n-1\}\).

Definition. A complete residue system modulo \(n\) is any set of \(n\) integers pairwise incongruent mod \(n\) (hence one from each class). Examples: \(\{0,1,\ldots,n-1\}\), \(\{1,2,\ldots,n\}\), \(\{-n/2,\ldots\}\) for even \(n\), etc.

Definition. A reduced residue system modulo \(n\) is a set of \(\varphi(n)\) integers pairwise incongruent mod \(n\) and all coprime to \(n\) (preview Day 75). Example mod \(8\): \(\{1,3,5,7\}\).

Well-defined ring operations

Theorem (compatibility). If \(a\equiv a'\pmod n\) and \(b\equiv b'\pmod n\), then \[ a+b\equiv a'+b'\pmod n,\qquad a-b\equiv a'-b'\pmod n,\qquad ab\equiv a'b'\pmod n. \]

Proof (addition). \(a-a'=nk\), \(b-b'=n\ell\) ⇒ \((a+b)-(a'+b')=n(k+\ell)\).
Proof (multiplication). \(ab-a'b'=a(b-b')+b'(a-a')=n(\cdots)\).

Thus addition and multiplication of residue classes are well-defined: \[ [a]+[b]=[a+b],\qquad [a]\cdot[b]=[ab]. \] The set \(\mathbb{Z}/n\mathbb{Z}\) of classes forms a commutative ring with identity \([1]\) (ring axioms inherited from \(\mathbb{Z}\)).

Exponentiation. If \(a\equiv a'\pmod n\) then \(a^k\equiv (a')^k\pmod n\) for \(k\ge 0\) (induction using the product rule).

Cancellation laws

Caution. You may not always cancel: \(2\cdot 3\equiv 2\cdot 7\pmod 8\) but \(3\not\equiv 7\pmod 8\).

Theorem (cancellation when coprime). If \(ca\equiv cb\pmod n\) and \(\gcd(c,n)=1\), then \(a\equiv b\pmod n\).

Proof. \(n\mid c(a-b)\) and \(\gcd(c,n)=1\) ⇒ \(n\mid(a-b)\) by Gauss’s lemma (Day 71/72).

Corollary. If \(p\) is prime and \(p\nmid c\), then cancellation of \(c\) is valid modulo \(p\). Equivalently \(\mathbb{Z}/p\mathbb{Z}\) is a field.

General cancellation. If \(ca\equiv cb\pmod n\) and \(d=\gcd(c,n)\), then \(a\equiv b\pmod{n/d}\) — but only after dividing the modulus carefully. More precisely: \(n\mid c(a-b)\) ⇒ \((n/d)\mid (c/d)(a-b)\) and \(\gcd(c/d,n/d)=1\), so \(n/d\mid(a-b)\).

Linear congruences

Problem. Solve \(ax\equiv b\pmod n\) for \(x\in\mathbb{Z}\).

Theorem (solvability). Let \(d=\gcd(a,n)\). The congruence \(ax\equiv b\pmod n\) has solutions iff \(d\mid b\). If solutions exist, there are exactly \(d\) incongruent solutions modulo \(n\).

Constructive method when \(d\mid b\).

1. Divide the entire congruence by \(d\): solve \((a/d)x\equiv b/d\pmod{n/d}\).
   
2. Now \(\gcd(a/d,n/d)=1\), so \(a/d\) has an inverse modulo \(n/d\) (Day 74); multiply both sides.
   
3. One solution \(x_0\) mod \(n/d\) lifts to \(d\) solutions mod \(n\): \[ x = x_0 + \frac{n}{d}k,\qquad k=0,1,\ldots,d-1. \]

Special case \(\gcd(a,n)=1\). Unique solution mod \(n\): \(x\equiv a^{-1}b\pmod n\).

Computing powers by reduction

To compute \(a^k\bmod n\): reduce \(a\) mod \(n\) first; use binary exponentiation (square-and-multiply) or look for a cycle in powers. Full Euler reduction of exponents needs Day 75.

Arithmetic of negatives and representatives

Always prefer a standard representative in \(\{0,1,\ldots,n-1\}\) unless a symmetric system is convenient. \(-1\equiv n-1\pmod n\).

---

Worked examples

Example 1 — Basic checks.
\(17\equiv 5\pmod 6\) because \(17-5=12=2\cdot 6\). \(100\equiv 1\pmod 9\) (digit sum \(1\)).

Example 2 — Operations.
\(7\equiv -1\pmod 8\), so \(7^2\equiv 1\), \(7^3\equiv -1\), \(7^{100}\equiv 1\pmod 8\).

Example 3 — Well-defined mult.
\(15\equiv 3\pmod{12}\), \(10\equiv -2\pmod{12}\), product \(150\equiv -6\equiv 6\pmod{12}\); also \(3\cdot(-2)=-6\equiv 6\).

Example 4 — Failed cancellation.
\(6\cdot 2\equiv 6\cdot 5\pmod 9\) (\(12\equiv 30\equiv 3\)) but \(2\not\equiv 5\pmod 9\). Note \(\gcd(6,9)=3\neq 1\). After general rule: \(2\equiv 5\pmod{9/3}\)? \(2\not\equiv 5\pmod 3\) either — wait: \(12-30=-18\), and \(9\mid 18\), \(6(2-5)=-18\). Divide by \(d=3\): need \(2\equiv 5\pmod 3\)? False. Check: \(6\cdot 2=12\), \(6\cdot 5=30\), \(12-30=-18\), yes \(9\mid 18\). The general cancellation says \(2\equiv 5\pmod{3}\) only if the congruence held after proper division… Actually \(ca\equiv cb\pmod n\) with \(d=\gcd(c,n)\) implies \(a\equiv b\pmod{n/d}\). Here \(c=6\), \(n=9\), \(d=3\), \(n/d=3\): is \(2\equiv 5\pmod 3\)? \(2\equiv 2\), \(5\equiv 2\), yes \(2\equiv 5\pmod 3\). Good.

Example 5 — Solve \(3x\equiv 6\pmod{12}\).
\(\gcd(3,12)=3\mid 6\). Divide by \(3\): \(x\equiv 2\pmod 4\). Solutions mod \(12\): \(x\equiv 2,6,10\pmod{12}\). Check: \(3\cdot 2=6\), \(3\cdot 6=18\equiv 6\), \(3\cdot 10=30\equiv 6\).

Example 6 — Solve \(4x\equiv 6\pmod{10}\).
\(\gcd(4,10)=2\mid 6\). Divide: \(2x\equiv 3\pmod 5\). Inverse of \(2\) mod \(5\) is \(3\) because \(2\cdot 3=6\equiv 1\). So \(x\equiv 9\equiv 4\pmod 5\). Lift: \(x\equiv 4,9\pmod{10}\).

Example 7 — No solution.
\(4x\equiv 3\pmod{10}\): \(\gcd(4,10)=2\nmid 3\). Impossible.

Example 8 — Complete residue system.
\(\{0,1,2,3,4\}\) and \(\{5,6,7,8,9\}\) and \(\{-2,-1,0,1,2\}\) are all complete systems mod \(5\).

Example 9 — Casting out nines.
\(a\equiv\) sum of decimal digits mod \(9\), because \(10\equiv 1\pmod 9\) ⇒ \(10^k\equiv 1\). Check: \(378: 3+7+8=18\), \(1+8=9\equiv 0\), and \(378/9=42\).

Example 10 — Clock.
Add \(10\) hours to \(7\): \(7+10=17\equiv 5\pmod{12}\) (if \(12\) labels as \(0\)).

---

Exercises

A. Definitions and relations

1. Prove carefully that \(\equiv\pmod n\) is an equivalence relation.
2. Show \(a\equiv b\pmod n\) iff \(a\) and \(b\) have the same remainder on division by \(n\).
3. List a complete residue system mod \(7\) consisting only of multiples of \(3\) if possible — or prove impossible.
4. How many residue classes mod \(n\) are represented by even integers when \(n\) is odd? When \(n\) is even?
5. Prove: if \(a\equiv b\pmod n\) and \(m\mid n\) then \(a\equiv b\pmod m\).

B. Well-defined operations

6. Prove the product rule: \(a\equiv a'\), \(b\equiv b'\) ⇒ \(ab\equiv a'b'\pmod n\) with full algebra.
7. Prove by induction: \(a\equiv b\pmod n\) ⇒ \(a^k\equiv b^k\pmod n\) for \(k\ge 0\).
8. Compute \(2^{10}\bmod 7\) by reducing powers of \(2\) mod \(7\).
9. Compute \(9^{100}\bmod 10\) (last digit).
10. Show that if \(a\equiv b\pmod n\) then \(\gcd(a,n)=\gcd(b,n)\).

C. Cancellation

11. Give your own example of failed cancellation mod \(15\).
12. Prove: if \(ca\equiv cb\pmod n\) and \(\gcd(c,n)=1\) then \(a\equiv b\pmod n\).
13. Solve using general cancellation: from \(6x\equiv 6y\pmod{15}\), what can you conclude about \(x-y\)?
14. True or false: \(\mathbb{Z}/8\mathbb{Z}\) is a field. Justify.

D. Linear congruences

15. Solve \(5x\equiv 3\pmod{7}\) (unique?).
16. Solve \(6x\equiv 9\pmod{15}\). List all incongruent solutions.
17. Solve \(8x\equiv 12\pmod{20}\).
18. Determine all \(b\) for which \(10x\equiv b\pmod{25}\) is solvable.
19. Solve the system idea (preview CRT): \(x\equiv 2\pmod 3\) and \(x\equiv 3\pmod 5\) by testing residues mod \(15\).
20. Prove the “exactly \(d\) solutions” statement when \(d\mid b\) (outline is enough if constructive method is clear).

E. Stretch and CS literacy

21. Prove: \(a\equiv b\pmod m\) and \(a\equiv b\pmod n\) ⇒ \(a\equiv b\pmod{\mathrm{lcm}(m,n)}\).
22. Show that the map \(\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/n\mathbb{Z}\), \(x\mapsto cx\) is bijective iff \(\gcd(c,n)=1\).
23. CS: explain why hash = key % m places keys into \(m\) buckets and when consecutive keys collide systematically.
24. CS: checksums mod \(9\) or mod \(11\) — what errors do they catch? (Prose.)
25. Find the order of \(2\) in the multiplicative sense mod \(7\): smallest \(k>0\) with \(2^k\equiv 1\pmod 7\). (Preview Day 75.)

---

Deep dive — \(\mathbb{Z}/n\mathbb{Z}\) as a ring (checklist)

Verify once for mental fluency:

Axiom	Why it holds
Associativity \(+\) / \(\cdot\)	Inherited from \(\mathbb{Z}\)
Commutativity \(+\) / \(\cdot\)	Inherited
Distributivity	Inherited
Identity \([0]\), \([1]\)	Clear
Additive inverses	\([-a]\)
Multiplicative inverses	Only for units (\(\gcd(a,n)=1\))

When \(n=p\) prime, every nonzero class is a unit → field \(\mathbb{F}_p\).

---

Deep dive — solving \(ax\equiv b\) algorithm card

Input: a, b, n > 0
d ← gcd(a, n)          // Euclid
if d does not divide b:
    return NO SOLUTION
// Reduce:
a' ← a/d; b' ← b/d; n' ← n/d
// Now gcd(a', n') = 1; find inverse of a' mod n'
u ← (a')^{-1} mod n'   // extended Euclid
x0 ← (b' * u) mod n'
// d solutions mod n:
return { x0 + k*n' : k = 0,1,...,d-1 }

Always verify one solution by substitution; then the arithmetic progression of solutions is forced by theory.

---

Additional worked examples

Example 11 — Powers of \(10\) mod \(9\) and \(11\).
\(10\equiv 1\pmod 9\) ⇒ digit sum rule. \(10\equiv -1\pmod{11}\) ⇒ alternating digit sum rule for divisibility by \(11\).

Example 12 — Solve \(15x\equiv 10\pmod{25}\).
\(d=\gcd(15,25)=5\mid 10\). Divide: \(3x\equiv 2\pmod 5\). Inverse of \(3\) mod \(5\) is \(2\) (\(6\equiv 1\)). \(x\equiv 4\pmod 5\). Lift: \(x\equiv 4,9,14,19,24\pmod{25}\).

Example 13 — Complete residue system of odds mod \(8\)?
Odds: \(1,3,5,7\) — only \(4\) classes, not complete (need \(8\)). Evens mod \(8\) also only \(4\) classes.

Example 14 — Prove if \(a\equiv b\pmod n\) then \(a^2\equiv b^2\pmod n\).
Special case of product rule: \(a\cdot a\equiv b\cdot b\).

Example 15 — Failed field.
In \(\mathbb{Z}/8\mathbb{Z}\), \([2]\cdot[4]=[0]\) with neither zero — zero divisors. No inverse for \([2]\).

---

More exercises

26. Prove: \(a\equiv b\pmod n\) and \(c\equiv d\pmod n\) ⇒ \(ac+bd\equiv \ldots\) expand carefully.
    
27. Solve \(9x\equiv 12\pmod{21}\).
    
28. Find all \(x\) with \(x^2\equiv 1\pmod 8\).
    
29. Show \(\{2,4,6,8,10\}\) is a complete residue system mod \(5\).
    
30. CS: cyclic buffer of length \(m\) — explain indices \((i+k)\bmod m\) as congruence arithmetic.
    
31. Prove there are exactly \(n\) residue classes mod \(n\) by division algorithm.
    
32. Reduce \(2^{20}\bmod 15\) by computing a power table (no Euler required).

---

Selected mini-solutions

8. \(2^1\equiv 2\), \(2^2\equiv 4\), \(2^3\equiv 1\pmod 7\) cycle \(3\); \(2^{10}=2^{9+1}\equiv 2\pmod 7\).
   
9. Inverse of \(5\) mod \(7\) is \(3\) (\(15\equiv 1\)); \(x\equiv 9\equiv 2\pmod 7\).
   
10. \(d=3\mid 9\); \(2x\equiv 3\pmod 5\); \(x\equiv 4\pmod 5\) after inv of \(2\) is \(3\); lift \(x\equiv 4,9,14\pmod{15}\).
    
11. \(m,n\mid(a-b)\) ⇒ \(\mathrm{lcm}(m,n)\mid(a-b)\).

---

Common pitfalls

Pitfall	Fix
Cancelling without coprimality	Check \(\gcd(c,n)=1\)
Reducing modulus incorrectly when dividing congruences	Divide modulus by \(\gcd\)
Mixing \(\mathrm{mod}\) as operator with \(\equiv\) relation	\(a\bmod n\) is a representative; \(\equiv\) is a relation
Negative remainders	Prefer \(\{0,\ldots,n-1\}\)
Claiming \(ax\equiv b\) always has a unique solution	Need \(\gcd(a,n)\mid b\); uniqueness only if \(\gcd=1\)
Treating \(\mathbb{Z}/n\mathbb{Z}\) as a field for composite \(n\)	Only when \(n\) prime

---

Synthesis — mixed modular workout (do closed-book)

S1. Prove carefully that if \(a\equiv b\pmod n\) then \(\gcd(a,n)=\gcd(b,n)\).

S2. Solve \(14x\equiv 18\pmod{21}\). List all incongruent solutions or prove none.

S3. Compute \(5^{13}\bmod 12\) by finding the cycle of powers of \(5\) mod \(12\).

S4. Is \(\{0,3,6,9,12,15\}\) a complete residue system mod \(6\)? Justify.

S5. Prove cancellation: if \(\gcd(c,n)=1\) and \(ca\equiv cb\pmod n\) then \(a\equiv b\pmod n\), citing Gauss.

S6. Explain in 4 sentences how hash index \(k\bmod m\) is a complete residue map \(\mathbb{Z}\to\{0,\ldots,m-1\}\).

S7. Find all \(b\) such that \(8x\equiv b\pmod{12}\) is solvable; for one such \(b\), list solutions.

S8. True/false with proof or counterexample: if \(a^2\equiv b^2\pmod n\) then \(a\equiv b\) or \(a\equiv -b\pmod n\). (Hint: false for composite \(n\) often.)

---

Checkpoint

• Can define \(a\equiv b\pmod n\) three ways
  
• Can prove sum/product well-defined
  
• Can cancel correctly when coprime
  
• Can solve \(ax\equiv b\pmod n\) including the \(d\) solutions case
  
• Can use complete residue systems
  
• Exercises A–D done; synthesis attempted

Two personal takeaways:

1. …
   
2. …

---

Deeper theory — residue classes form a ring (proof outline)

Theorem. With well-defined \(+\) and \(\cdot\), \(\mathbb{Z}/n\mathbb{Z}\) is a commutative ring with identity.

Outline. Associativity, commutativity, and distributivity of \(+\) and \(\cdot\) hold for representatives because they hold in \(\mathbb{Z}\), and the compatibility theorem shows the operations do not depend on the choice of representative. Additive identity is \([0]\); additive inverse of \([a]\) is \([-a]\). Multiplicative identity is \([1]\). (Multiplicative inverses exist only for units — Day 74.)

Corollary. The map \(\mathbb{Z}\to\mathbb{Z}/n\mathbb{Z}\), \(a\mapsto[a]\), is a surjective ring homomorphism with kernel \(n\mathbb{Z}\).

---

Deeper theory — why cancellation needs Gauss

Recall Gauss (Day 71/72): if \(a\mid bc\) and \(\gcd(a,b)=1\) then \(a\mid c\).

Full cancellation proof. Assume \(ca\equiv cb\pmod n\) and \(\gcd(c,n)=1\). Then \(n\mid c(a-b)\). Set \(a_{\mathrm{div}}=n\), \(b_{\mathrm{div}}=c\), \(c_{\mathrm{div}}=a-b\) in Gauss’s statement: \(n\mid c(a-b)\) and \(\gcd(n,c)=1\) ⇒ \(n\mid(a-b)\), i.e. \(a\equiv b\pmod n\).

Without Gauss. If you only know Bézout, write \(1=cx+ny\); multiply by \((a-b)\): \(a-b=c(a-b)x+n(a-b)y\). The first term is a multiple of \(n\) because \(n\mid c(a-b)\), so \(n\mid(a-b)\).

---

Worked example — complete solve walkthrough

Example 16 — \(15x\equiv 25\pmod{35}\).
\(d=\gcd(15,35)=5\). Does \(5\mid 25\)? Yes. Divide: \(3x\equiv 5\pmod 7\). Inverse of \(3\) mod \(7\): \(3\cdot 5=15\equiv 1\), so inv \(=5\). Thus \(x\equiv 25\equiv 4\pmod 7\). Lift to mod \(35\): \(x=4+7k\) for \(k=0,1,2,3,4\), i.e. \(x\equiv 4,11,18,25,32\pmod{35}\).
Check one: \(15\cdot 4=60\equiv 25\pmod{35}\) (\(60-35=25\)). Check another: \(15\cdot 11=165\), \(165/35=4\cdot 35=140\), remainder \(25\). ✓

Example 17 — Powers mod \(9\).
\(2^1\equiv 2\), \(2^2\equiv 4\), \(2^3\equiv 8\equiv -1\), \(2^6\equiv 1\pmod 9\). Cycle length \(6\). So \(2^{100}=2^{16\cdot 6+4}\equiv 2^4\equiv 7\pmod 9\).

Example 18 — Same remainder characterization.
If \(a=nq_1+r\) and \(b=nq_2+r\) with \(0\le r<n\), then \(a-b=n(q_1-q_2)\), so \(a\equiv b\pmod n\). Conversely if \(a\equiv b\) and \(a=nq+r\) is the division of \(a\), then \(b=a-nk=n(q-k)+r\) with same \(r\).

---

Extra exercises — modular fluency

33. Prove: if \(a\equiv b\pmod n\) then \(a^2+a\equiv b^2+b\pmod n\).
    
34. Solve \(21x\equiv 14\pmod{35}\).
    
35. Find all complete residue systems mod \(4\) contained in \(\{0,1,\ldots,10\}\).
    
36. Compute \(3^{20}\bmod 14\) by successive squaring (no Euler required).
    
37. Show that \(10^k\equiv 1\pmod 9\) for all \(k\ge 0\); deduce the digit-sum rule.
    
38. Prove: the set of multiples of \(d\) among \(\{0,1,\ldots,n-1\}\) forms a complete residue system mod \(n/d\) after dividing by \(d\), when \(d\mid n\).
    
39. CS literacy: explain wrap-around of a 32-bit unsigned counter as arithmetic mod \(2^{32}\).
    
40. True/false: if \(ab\equiv 0\pmod n\) then \(a\equiv 0\) or \(b\equiv 0\pmod n\). Prove or give counterexample.

---

Mini-solutions (selected)

16 walkthrough already checked.
34. \(d=\gcd(21,35)=7\mid 14\); divide: \(3x\equiv 2\pmod 5\); inv of \(3\) mod \(5\) is \(2\); \(x\equiv 4\pmod 5\); lift \(x\equiv 4,9,14,19,24,29,34\pmod{35}\).
40. False: \(2\cdot 3\equiv 0\pmod 6\) but neither factor \(\equiv 0\pmod 6\).

---

Closing synthesis card

Skill	Check
Define \(\equiv\) three ways	□
Prove \(+\)/\(\cdot\) well-defined	□
Cancel only when coprime	□
Solve \(ax\equiv b\) with \(d\) solutions	□
Reduce powers by cycles	□

If any box fails, redo Examples 5–6 and exercises 15–17 before Day 74.

Tomorrow

Day 74 — Modular inverses, units, Wilson’s theorem.