Day 25 — Divisibility, Euclidean Algorithm & Modular Arithmetic

Updated

July 30, 2025

Day 25 — Divisibility, Euclidean Algorithm & Modular Arithmetic

Day 71 — Divisibility, primes, and the Fundamental Theorem of Arithmetic

Stage VII · concept day
Goal: Formalize \(a\mid b\); prove standard properties; define primes; state Euclid’s lemma; state FTA with existence + uniqueness sketches; connect gcd/lcm to exponents.

Why this matters

Divisibility is the backbone of modular arithmetic, hashing buckets, cyclic structures, and every crypto-literacy story that follows. If “\(a\) divides \(b\)” is fuzzy, every later congruence proof wobbles. Today we make the language precise and prove the lemmas you will reuse constantly on Days 72–80.

Note

No labs. Theory, short proofs, worked calculations, written exercises. Calculator only to check arithmetic after you finish by hand.

Theory

Divisibility

Definition (divides). Let \(a,b\in\mathbb{Z}\). We say \(a\) divides \(b\), written \(a\mid b\), if there exists an integer \(k\) such that \[ b = a\cdot k. \] When \(a\mid b\) we also say \(a\) is a divisor (or factor) of \(b\), and \(b\) is a multiple of \(a\). If no such \(k\) exists, write \(a\nmid b\).

Examples. \(3\mid 12\) because \(12=3\cdot 4\). \(5\nmid 12\). \(7\mid 0\) because \(0=7\cdot 0\). For any \(a\neq 0\), \(a\mid a\) (\(k=1\)) and \(a\mid 0\).

Convention. Usually we care about \(a\neq 0\). The statement \(0\mid b\) holds only when \(b=0\) (because \(b=0\cdot k\) forces \(b=0\)). We rarely use \(0\) as a divisor in applications.

Immediate consequences

Proposition 1 (basic properties). For all \(a,b,c\in\mathbb{Z}\):

  1. Reflexive (nonzero): if \(a\neq 0\) then \(a\mid a\).
  2. Transitive: if \(a\mid b\) and \(b\mid c\) then \(a\mid c\).
  3. Linear combination: if \(a\mid b\) and \(a\mid c\) then \(a\mid (bx+cy)\) for all \(x,y\in\mathbb{Z}\).
  4. Units: \(1\mid n\) and \((-1)\mid n\) for every \(n\); if \(a\mid b\) and \(b\mid a\) then \(a=\pm b\).
  5. Bound for positives: if \(a,b>0\) and \(a\mid b\) then \(a\le b\).
  6. Multiplicative: if \(a\mid b\) then \(a\mid bc\) for every \(c\); if \(a\mid b\) and \(c\mid d\) then \(ac\mid bd\).

Proof of (2). \(b=ak\), \(c=b\ell=ak\ell\), so \(a\mid c\).

Proof of (3). Write \(b=ak\), \(c=a\ell\). Then \(bx+cy = a(kx+\ell y)\), so \(a\mid(bx+cy)\).

Proof of (4) second part. \(b=ak\), \(a=b\ell\) implies \(b=b(k\ell)\), so \(b(k\ell-1)=0\). If \(b\neq 0\) then \(k\ell=1\), so \(k,\ell\in\{\pm 1\}\) and \(a=\pm b\). If \(b=0\) then \(a=0\) as well from \(a=b\ell\).

Proof of (5). \(b=ak\) with \(k\ge 1\) integer (since \(b>0,a>0\)), so \(b\ge a\).

Proof of (6). First claim: \(b=ak\) ⇒ \(bc=a(kc)\). Second: \(b=ak\), \(d=c\ell\) ⇒ \(bd=ac(k\ell)\).

The division algorithm (reminder)

Theorem (division algorithm). For any \(a\in\mathbb{Z}\) and \(d\in\mathbb{Z}\) with \(d>0\), there exist unique integers \(q\) (quotient) and \(r\) (remainder) such that \[ a = dq + r \quad\text{and}\quad 0\le r < d. \] We write \(a = dq+r\) and sometimes \(r = a\bmod d\) (mathematical nonnegative remainder).

Existence sketch. Consider the set \(S=\{a-dq:q\in\mathbb{Z},\, a-dq\ge 0\}\). It is nonempty (take \(q\) large negative if needed). Let \(r\) be its least element; then \(r<d\) else \(r-d\) would be a smaller nonnegative element of \(S\).

Uniqueness sketch. If \(a=dq+r=dq'+r'\) with \(0\le r,r'<d\), then \(d(q-q')=r'-r\), so \(d\) divides a difference strictly between \(-d\) and \(d\), forcing \(r=r'\) and \(q=q'\).

This is the formal home of “integer division.” Programming languages may return negative remainders for negative dividends; always state the mathematical convention when proving.

Primes and composites

Definition (prime). An integer \(p>1\) is prime if its only positive divisors are \(1\) and \(p\). Equivalently: if \(p=ab\) with \(a,b\in\mathbb{Z}_{>0}\), then one of \(a,b\) is \(1\) and the other is \(p\).

Definition (composite). An integer \(n>1\) that is not prime is composite: it factors as \(n=ab\) with integers \(a,b\) both \(>1\).

Definition (unit). \(\pm 1\) are units in \(\mathbb{Z}\); they are neither prime nor composite. \(0\) is neither.

Small primes. \(2,3,5,7,11,13,17,19,23,\ldots\). Note \(2\) is the only even prime.

Lemma (every \(n>1\) has a prime divisor). Let \(n>1\). Among all divisors of \(n\) that are \(>1\), let \(p\) be a minimal one. Then \(p\) is prime: if \(p=ab\) with \(1<a,b\), then \(a\) would be a smaller divisor \(>1\) of \(n\).

Euclid’s lemma

Lemma (Euclid’s lemma). If \(p\) is prime and \(p\mid ab\), then \(p\mid a\) or \(p\mid b\).

Proof (via Bézout — full proof after Day 72). If \(p\nmid a\) then \(\gcd(p,a)=1\) (the only positive divisors of \(p\) are \(1,p\)). By Bézout there exist \(x,y\) with \(px+ay=1\). Multiply by \(b\): \(pxb + ayb = b\). Now \(p\mid ab\) so \(p\mid ayb\), and \(p\mid pxb\), hence \(p\mid b\) by linear combinations.

Corollary (to products). If \(p\) is prime and \(p\mid a_1 a_2\cdots a_k\), then \(p\mid a_i\) for some \(i\). (Induction on \(k\).)

Warning. The conclusion fails if \(p\) is replaced by a composite: e.g. \(4\mid 6\cdot 6\) but \(4\nmid 6\).

Fundamental Theorem of Arithmetic (FTA)

Theorem (FTA). Every integer \(n>1\) can be written as a product of primes \[ n = p_1 p_2 \cdots p_k \] (with \(k\ge 1\), each \(p_i\) prime), and this factorization is unique up to order: if also \(n=q_1\cdots q_\ell\) with primes \(q_j\), then \(k=\ell\) and the lists \(\{p_i\}\) and \(\{q_j\}\) are rearrangements of each other.

Canonical form. We often group equals: \[ n = p_1^{e_1} p_2^{e_2}\cdots p_r^{e_r},\qquad p_1<p_2<\cdots<p_r,\quad e_i\ge 1. \] This representation is unique.

Existence (strong induction). Base: smallest \(n=2\) is prime. Assume every integer in \(\{2,\ldots,n-1\}\) factors into primes. If \(n\) is prime, done. If composite, \(n=ab\) with \(1<a,b<n\); by IH each of \(a,b\) is a prime product, hence so is \(n\).

Uniqueness sketch. Suppose \[ p_1\cdots p_k = q_1\cdots q_\ell \] with primes. By Euclid’s lemma, \(p_1\) divides some \(q_j\), hence \(p_1=q_j\) (both prime). Cancel \(p_1\) and induct on the number of factors (or on \(n\)).

Consequences used constantly

Fact How FTA gives it
\(\gcd\) via min exponents If \(a=\prod p_i^{\alpha_i}\), \(b=\prod p_i^{\beta_i}\), then \(\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}\)
\(\mathrm{lcm}\) via max \(\mathrm{lcm}(a,b)=\prod p_i^{\max(\alpha_i,\beta_i)}\)
Identity \(\gcd(a,b)\cdot\mathrm{lcm}(a,b)=ab\) for \(a,b>0\)
Squares \(n\) is a perfect square iff all \(e_i\) even
Squarefree \(n\) squarefree iff all \(e_i=1\)

gcd properties (preview of Day 72)

Definition. For integers \(a,b\) not both zero, \(\gcd(a,b)\) is the largest positive integer \(d\) with \(d\mid a\) and \(d\mid b\). Convention: \(\gcd(a,b)=\gcd(|a|,|b|)\).

Proposition 2 (gcd facts).

  1. \(\gcd(a,0)=|a|\) for \(a\neq 0\).
  2. If \(d=\gcd(a,b)\) then \(\gcd(a/d,b/d)=1\).
  3. Common divisors of \(a,b\) are exactly the divisors of \(\gcd(a,b)\) (once Bézout is known: every common divisor divides every integer combination, hence divides the gcd).
  4. \(\gcd(a,b)=\gcd(b,a-qb)\) for any integer \(q\) (sets of common divisors match).

Item (4) is the engine of the Euclidean algorithm tomorrow.

Coprimality

Definition. Integers \(a,b\) are coprime (or relatively prime) if \(\gcd(a,b)=1\).

Lemma (Gauss). If \(a\mid bc\) and \(\gcd(a,b)=1\), then \(a\mid c\). (Proof after Day 72 via Bézout, or via FTA: every prime of \(a\) cannot divide \(b\), so all divide \(c\).)

Infinitely many primes (Euclid)

Theorem. There are infinitely many primes.

Proof. Suppose only finitely many primes \(p_1,\ldots,p_m\). Let \(N=p_1\cdots p_m + 1\). Then \(N>1\), so \(N\) has a prime factor \(q\). But \(q\) cannot equal any \(p_i\) (else \(p_i\mid N\) and \(p_i\mid p_1\cdots p_m\) imply \(p_i\mid 1\)). Contradiction. ∎

This proves existence of more primes, not an efficient way to find large primes.

Counting positive divisors

If \(n=\prod p_i^{e_i}\), every positive divisor has the form \(\prod p_i^{a_i}\) with \(0\le a_i\le e_i\). Number of positive divisors: \[ \tau(n)=(e_1+1)(e_2+1)\cdots(e_r+1). \] The sum of positive divisors is \(\sigma(n)=\prod_i (1+p_i+\cdots+p_i^{e_i})=\prod_i\frac{p_i^{e_i+1}-1}{p_i-1}\).

Worked examples

Example 1 — Linear combinations.
Prove: if \(a\mid b\) and \(a\mid c\) then \(a\mid(b+c)\) and \(a\mid(b-c)\).
Write \(b=ak\), \(c=a\ell\). Then \(b+c=a(k+\ell)\) and \(b-c=a(k-\ell)\).

Example 2 — Extract a summand.
Prove: if \(3\mid n\) and \(3\mid(n+m)\) then \(3\mid m\).
\(3\mid n\) and \(3\mid(n+m)\) imply \(3\mid\bigl((n+m)-n\bigr)\), so \(3\mid m\).

Example 3 — Factorization.
\(360=36\cdot 10=(2^2 3^2)\cdot(2\cdot 5)=2^3\cdot 3^2\cdot 5\). Any other prime factorization is a reordering of three \(2\)s, two \(3\)s, and one \(5\).

Example 4 — gcd/lcm via FTA.
\(a=84=2^2\cdot 3\cdot 7\), \(b=90=2\cdot 3^2\cdot 5\). Then \[ \gcd(84,90)=2\cdot 3=6,\qquad \mathrm{lcm}(84,90)=2^2\cdot 3^2\cdot 5\cdot 7=1260, \] and \(6\cdot 1260=7560=84\cdot 90\).

Example 5 — Euclid’s lemma needs primality.
If \(p\) is prime and \(p\mid n^2\) then \(p\mid n\cdot n\) ⇒ \(p\mid n\). Contrast: \(4\mid 6^2\) but \(4\nmid 6\).

Example 6 — Squares and exponents.
If \(n=m^2\) and \(m=\prod p_i^{f_i}\), then \(n=\prod p_i^{2f_i}\) — all exponents even. Conversely if all \(e_i=2f_i\), set \(m=\prod p_i^{f_i}\).

Example 7 — Divisor count.
For \(360=2^3 3^2 5\): \(\tau(360)=(3+1)(2+1)(1+1)=24\).

Example 8 — Prove \(2\mid n\) and \(3\mid n\) ⇒ \(6\mid n\).
\(n=2k\) and \(3\mid 2k\). Since \(\gcd(3,2)=1\), Gauss’s lemma ⇒ \(3\mid k\), so \(k=3\ell\), \(n=6\ell\). (Alternatively use FTA: \(2\) and \(3\) both appear in \(n\).)

Example 9 — Irrationality of \(\sqrt{2}\) (FTA style).
Suppose \(\sqrt{2}=a/b\) in lowest terms, \(a,b>0\). Then \(a^2=2b^2\). The exponent of \(2\) in \(a^2\) is even; in \(2b^2\) it is odd — contradiction to uniqueness of exponents.

Example 10 — Division algorithm.
\(a=-17\), \(d=5\): \(-17=5\cdot(-4)+3\) because \(-20+3=-17\) and \(0\le 3<5\). Not “remainder \(-2\).”

Exercises

Solve by hand. Show definitions and reasons.

A. Definitions and quick facts

  1. Write the definition of \(a\mid b\) without looking. Give three examples and two non-examples.
  2. True or false? Justify: (a) \(0\mid 0\); (b) \(0\mid 5\); (c) \(5\mid 0\); (d) \((-3)\mid 12\); (e) \(4\mid 2\).
  3. Prove: if \(a\mid b\) then \(a\mid bc\) for every integer \(c\).
  4. Prove: if \(a\mid b\) and \(c\mid d\) then \(ac\mid bd\).
  5. Find all integers \(d\) with \(d\mid 12\). Separate positive and negative.
  6. Apply the division algorithm to \(a=100\), \(d=7\) and to \(a=-100\), \(d=7\).

B. Proofs with linear combinations

  1. Prove: if \(a\mid b\) and \(a\mid c\) then \(a\mid(3b-5c)\).
  2. Prove: if \(6\mid n\) then \(2\mid n\) and \(3\mid n\). Is the converse true? Prove or counterexample.
  3. Prove: if \(2\mid n\) and \(3\mid n\) then \(6\mid n\).
  4. Prove: if \(a\mid b\) and \(b\mid c\) and \(c\mid a\) then \(|a|=|b|=|c|\).
  5. Show that the set of common divisors of \(a\) and \(b\) equals the set of divisors of \(\gcd(a,b)\) assuming the FTA formula for gcd.

C. Primes and FTA

  1. Prove that every integer \(n>1\) has a prime divisor.
  2. List the complete prime factorization of \(504\) and of \(1001\).
  3. Using FTA, compute \(\gcd(504,1001)\) and \(\mathrm{lcm}(504,1001)\); verify the product identity.
  4. Prove: if \(p\) is prime and \(p\nmid a\), then \(\gcd(p,a)=1\).
  5. Give a counterexample showing Euclid’s lemma fails if \(p\) is replaced by a composite \(m>1\).
  6. Prove using FTA: if \(a^2\mid b^2\) then \(a\mid b\) (for \(a,b>0\)).
  7. Prove the corollary: if \(p\) prime and \(p\mid a_1\cdots a_k\) then \(p\mid a_i\) for some \(i\).
  8. Factor \(2^{10}-1=1023\) and \(2^{10}+1=1025\) completely (or as far as small primes allow by hand).

D. Divisor counting and structure

  1. How many positive divisors does \(2^4\cdot 3^2\cdot 5\) have? Justify without listing if you prefer, then list to check.
  2. For which \(n\) is \(\tau(n)\) odd? Prove your characterization. (Hint: perfect squares.)
  3. Prove there are infinitely many composite numbers.
  4. Euclid’s construction: with primes \(2,3,5\) only (imagine), form \(N=2\cdot3\cdot5+1\). Factor \(N\) in the real integers — what new prime appears?
  5. Compute \(\sigma(12)\) and \(\sigma(28)\). (Note \(28\) is perfect: \(\sigma(28)-28=28\).)
  6. CS literacy (no code): explain in 3–5 sentences why unique factorization makes “cancel primes” valid when reasoning about buffer sizes that are powers of two, reducing fractions in exact rational arithmetic, or periods of modular counters.

E. Stretch

  1. Prove: among any \(n+1\) integers, two differ by a multiple of \(n\). (Pigeonhole on residues — modular preview.)
  2. Prove that \(\sqrt{3}\) is irrational using FTA (or Euclid’s classic argument).
  3. If \(n=\prod p_i^{e_i}\), count ordered pairs \((a,b)\) of positive integers with \(ab=n\). Then count unordered pairs \(\{a,b\}\).
  4. Prove: if \(a\mid b\) and \(a\mid c\) and \(\gcd(b/a,c/a)=1\), then \(\mathrm{lcm}(b,c)=bc/a\).
  5. Show that the product of any \(k\) consecutive integers is divisible by \(k!\).

Deep dive — gcd properties catalogue

Collect these for constant reuse (some proved today via FTA; others finished with Bézout on Day 72):

Property Statement
Symmetry \(\gcd(a,b)=\gcd(b,a)=\gcd(|a|,|b|)\)
Zero \(\gcd(a,0)=|a|\) (\(a\neq 0\))
Idempotent \(\gcd(a,a)=|a|\)
Scaling \(\gcd(ca,cb)=|c|\gcd(a,b)\)
Coprime reduction \(\gcd(a/d,b/d)=1\) if \(d=\gcd(a,b)\)
Product identity \(\gcd(a,b)\cdot\mathrm{lcm}(a,b)=|ab|\)
Coprime factors if \(\gcd(a,b)=1\) and \(a\mid bc\) then \(a\mid c\)
Pairwise if \(\gcd(a,b)=\gcd(a,c)=1\) then \(\gcd(a,bc)=1\)

Proof of pairwise coprimality via FTA. Primes of \(a\) appear in neither \(b\) nor \(c\), hence not in \(bc\).

Proof of product identity via FTA. With \(a=\prod p^{\alpha}\), \(b=\prod p^{\beta}\), \[ \min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta, \] so multiplying gcd and lcm multiplies to \(ab\).

Deep dive — why Euclid’s lemma is the “prime atom” law

Compare three statements:

  1. Prime definition: only positive divisors \(1,p\).
  2. Euclid’s lemma: \(p\mid ab\Rightarrow p\mid a\) or \(p\mid b\).
  3. FTA uniqueness: prime factorizations unique up to order.

In \(\mathbb{Z}\), (1) implies (2) once Bézout is available, and (2) implies (3). In more exotic rings, “irreducible” (cannot factor nontrivially) and “prime” (satisfies Euclid’s lemma) can diverge — awareness that \(\mathbb{Z}\) is special. For CS, the moral is: cancellation of primes in integer equations is licensed by Euclid’s lemma / FTA, not by wishful thinking.

Worked contrast. From \(2a=2b\) we cancel \(2\) to get \(a=b\) in \(\mathbb{Z}\). From \(4a=4b\) we may also cancel, but from \(4\mid ab\) we cannot conclude \(4\mid a\) or \(4\mid b\) (\(a=b=2\)).

Additional worked examples

Example 11 — Prove: if \(a\mid b\) and \(b\neq 0\) then \(|a|\le|b|\).
\(b=ak\) with \(k\neq 0\), so \(|b|=|a||k|\ge|a|\).

Example 12 — Common multiple structure.
Every common multiple of \(a,b>0\) is a multiple of \(\mathrm{lcm}(a,b)\). Via FTA: exponents in a common multiple are \(\ge\max(\alpha,\beta)\), so divisible by the lcm’s exponents.

Example 13 — Squarefree kernel.
If \(n=\prod p_i^{e_i}\), the radical \(\mathrm{rad}(n)=\prod p_i\) is the largest squarefree divisor. Example: \(\mathrm{rad}(360)=2\cdot 3\cdot 5=30\).

Example 14 — Prove \(n\) and \(n+1\) are always coprime.
Any common divisor divides \((n+1)-n=1\).

Example 15 — Division algorithm for \(a=-100\), \(d=7\).
\(-100=7\cdot(-15)+5\) because \(-105+5=-100\) and \(0\le 5<7\). Check: languages that return remainder \(-2\) for \(-100\%7\) are using a different convention.

Selected mini-solutions (check after attempting)

  1. \(b=ak\) ⇒ \(bc=a(kc)\).
  2. \(b=ak\), \(c=a\ell\) ⇒ \(3b-5c=a(3k-5\ell)\).
  3. Minimal \(d>1\) dividing \(n\) is prime (else smaller divisor \(>1\)).
  4. \(504=2^3\cdot 3^2\cdot 7\), \(1001=7\cdot 11\cdot 13\), \(\gcd=7\), \(\mathrm{lcm}=2^3\cdot 3^2\cdot 7\cdot 11\cdot 13\).
  5. Even exponents in \(a^2\) ≤ even exponents in \(b^2\) ⇒ half-exponents give \(a\mid b\).
  6. \(\tau(n)\) odd iff \(n\) is a square (divisors pair \(d\leftrightarrow n/d\) except when \(d=\sqrt{n}\)).

Common pitfalls

Pitfall Fix
Treating \(1\) as prime Primes are \(>1\) with exactly two positive divisors
“Unique factorization” including order or units Uniqueness is up to order; units \(\pm 1\) are not primes
Applying Euclid’s lemma to composites Needs primality (or coprimality variants)
Forgetting negative divisors when asked for “all divisors” \(\pm\) pairs unless positivity is specified
Confusing \(a\mid b\) with \(a/b\) as a rational Divisibility is an integer statement
Negative remainders Use \(0\le r<d\) mathematical convention
Cancelling composites as if primes Use Gauss only when coprime

Checkpoint

  • Can write \(a\mid b\) formally and prove the linear-combination property
  • Can state FTA in canonical exponent form and compute gcd/lcm from it
  • Can state Euclid’s lemma and give a composite counterexample to the naive version
  • Can prove infinitude of primes (Euclid) from memory
  • Can count \(\tau(n)\) from prime factorization
  • Exercises A–D essentially done; E optional stretch

Two personal takeaways:

  1. …
  2. …

Tomorrow

Day 72 — Euclidean algorithm and extended Euclid (Bézout).

Day 72 — Euclidean algorithm and the extended Euclidean algorithm

Stage VII · concept day
Goal: Compute \(\gcd\) by Euclid’s algorithm; prove correctness via the remainder invariant; understand \(O(\log n)\) complexity and Fibonacci worst case; run extended Euclid; prove Bézout; prepare modular inverses.

Why this matters

The Euclidean algorithm is one of the oldest and most important algorithms in mathematics. In CS literacy it underpins modular inverses (Day 74), fraction reduction, and the algebra behind RSA’s key equations (Day 77). Extended Euclid turns “\(\gcd=1\)” into an explicit integer combination — the constructive heart of Bézout’s identity.

Note

No labs. Hand-trace every table. Optional calculator only to verify multiplications after the fact.

Theory

gcd definition

Definition. For integers \(a,b\) not both zero, \(\gcd(a,b)\) is the largest positive integer \(d\) such that \(d\mid a\) and \(d\mid b\). Convention: \(\gcd(a,b)=\gcd(|a|,|b|)\). We avoid \(\gcd(0,0)\) (undefined or \(0\) depending on system).

Symmetry. \(\gcd(a,b)=\gcd(b,a)\).

Key identity (the invariant)

Lemma (gcd recurrence). For any integers \(a,b\) with \(b\neq 0\), and any integer \(q\), \[ \gcd(a,b)=\gcd(b,\, a-qb). \] In particular, if \(a=bq+r\) (division algorithm), then \[ \gcd(a,b)=\gcd(b,r)=\gcd(b,\, a\bmod b). \]

Proof. Any common divisor of \(a\) and \(b\) divides \(a-qb\), hence divides \(r\). Conversely any common divisor of \(b\) and \(r\) divides \(bq+r=a\). So the sets of common divisors coincide; the greatest positives match.

This identity is the loop invariant of Euclid: each replacement preserves the gcd of the current pair.

Euclidean algorithm

Algorithm (Euclid). Input: integers \(a,b\ge 0\), not both zero. (WLOG start with any order.)

  1. While \(b\neq 0\): replace \((a,b)\) by \((b,\, a\bmod b)\).
  2. Return \(a\).

Theorem (correctness). The algorithm terminates and returns \(\gcd(a,b)\).

Proof.
- Termination: each remainder satisfies \(0\le r < b\), so the second coordinate is a strictly decreasing sequence of nonnegative integers. It cannot descend forever.
- Correctness: by the gcd recurrence, \(\gcd\) is invariant under each replacement. When \(b=0\), \(\gcd(a,0)=a\) (for \(a>0\); if both start zero we excluded). By induction on the number of steps, the return value is the original gcd.

Complexity: \(O(\log n)\) and Fibonacci worst case

Lamé’s theorem (statement). If \(a>b\ge 1\) and Euclid takes \(k\) division steps (nonzero remainders), then \(b\ge F_{k+1}\) (Fibonacci, with \(F_1=1,F_2=1,F_3=2,\ldots\)). Consequently the number of steps is \(O(\log b)\).

Worst-case intuition. Consecutive Fibonacci numbers force remainders to drop as slowly as possible: Euclid on \((F_{n+1},F_n)\) produces the previous Fibonacci pair at each step. Since \(F_n\sim \varphi^n/\sqrt{5}\) with \(\varphi=(1+\sqrt{5})/2\), we need \(n=\Theta(\log F_n)\) steps.

Bit-complexity literacy. Each division on numbers of size \(O(\log n)\) bits is itself not free in a multi-tape model, but for this volume the takeaway is: Euclid is logarithmic in the magnitude, vastly faster than trial division up to \(\min(|a|,|b|)\).

Bézout’s identity

Theorem (Bézout). For any \(a,b\in\mathbb{Z}\) not both zero, there exist integers \(x,y\) (Bézout coefficients) such that \[ ax + by = \gcd(a,b). \] Moreover, the set of all integer linear combinations \(\{ax+by:x,y\in\mathbb{Z}\}\) equals exactly the set of multiples of \(d=\gcd(a,b)\).

Proof that combinations = \(d\mathbb{Z}\).
Let \(I=\{ax+by:x,y\in\mathbb{Z}\}\). \(I\) is nonempty and closed under addition and subtraction. Let \(d^*\) be the least positive element of \(I\) (well-ordering of positive integers). Division: any \(z\in I\) is a multiple of \(d^*\) (else remainder would be a smaller positive element of \(I\)). In particular \(d^*\mid a\) and \(d^*\mid b\) (take \(x=1,y=0\) and \(x=0,y=1\)), so \(d^*\le d=\gcd(a,b)\). But \(d\) divides every combination, so \(d\mid d^*\) and \(d^*\ge d\). Thus \(d^*=d\), and \(I=d\mathbb{Z}\). In particular \(d\in I\), giving Bézout coefficients.

Corollary. \(\gcd(a,b)=1\) iff there exist \(x,y\) with \(ax+by=1\).

Corollary (Euclid’s lemma via Bézout). If \(p\) prime, \(p\mid ab\), \(p\nmid a\), then \(p\mid b\). (Day 71 sketch now fully justified.)

Extended Euclidean algorithm

Run Euclid while recording quotients, then express the gcd as a combination of the original \(a,b\).

Method 1 — back-substitution. Write each remainder as a combination of previous two lines until the gcd is a combination of \(a\) and \(b\).

Method 2 — tabular (recommended). Maintain coefficients so each remainder \(r_i = a s_i + b t_i\).

Initialize:

\(i\) \(r_i\) \(q_i\) \(s_i\) \(t_i\)
\(-1\) \(a\) — \(1\) \(0\)
\(0\) \(b\) — \(0\) \(1\)

While \(r_i\neq 0\): \(q_{i+1}=\lfloor r_{i-1}/r_i\rfloor\), \(r_{i+1}=r_{i-1}-q_{i+1}r_i\), and \[ s_{i+1}=s_{i-1}-q_{i+1}s_i,\qquad t_{i+1}=t_{i-1}-q_{i+1}t_i. \] When \(r_{k+1}=0\), we have \(r_k=\gcd\) and \(r_k=a s_k + b t_k\).

Linear Diophantine equations

Theorem. The equation \(ax+by=c\) has integer solutions \((x,y)\) iff \(\gcd(a,b)\mid c\).

If \(d=\gcd(a,b)\) and \(x_0,y_0\) satisfy \(ax_0+by_0=d\), then one particular solution of \(ax+by=c\) is \[ x^*=x_0\cdot\frac{c}{d},\qquad y^*=y_0\cdot\frac{c}{d}. \] The general solution (for \(ab\neq 0\)) is \[ x=x^* + \frac{b}{d}k,\qquad y=y^* - \frac{a}{d}k,\qquad k\in\mathbb{Z}. \]

Verification. The homogeneous equation \(ax+by=0\) has solutions \(x=(b/d)k\), \(y=-(a/d)k\); adding a particular solution yields the full lattice of solutions.

Connection to modular inverses (preview Day 74)

If \(\gcd(a,m)=1\), Bézout gives \(ax+my=1\), so \(ax\equiv 1\pmod m\): \(x\bmod m\) is an inverse of \(a\) modulo \(m\). Extended Euclid is the standard constructive method.

Worked examples

Example 1 — Euclid on \((252,198)\). \[ \begin{align*} 252 &= 1\cdot 198 + 54,\\ 198 &= 3\cdot 54 + 36,\\ 54 &= 1\cdot 36 + 18,\\ 36 &= 2\cdot 18 + 0. \end{align*} \] So \(\gcd(252,198)=18\). Invariant: \(\gcd(252,198)=\gcd(198,54)=\gcd(54,36)=\gcd(36,18)=\gcd(18,0)=18\).

Example 2 — Extended: \(252x+198y=18\). \[ \begin{align*} 18 &= 54 - 1\cdot 36,\\ 36 &= 198 - 3\cdot 54 \implies 18 = 4\cdot 54 - 1\cdot 198,\\ 54 &= 252 - 1\cdot 198 \implies 18 = 4\cdot 252 - 5\cdot 198. \end{align*} \] Check: \(252\cdot 4 + 198\cdot(-5)=1008-990=18\).

Example 3 — Tabular extended Euclid for \(\gcd(240,46)\).

\(r\) \(q\) \(s\) \(t\)
\(240\) \(1\) \(0\)
\(46\) \(0\) \(1\)
\(10\) \(5\) \(1\) \(-5\)
\(6\) \(4\) \(-4\) \(21\)
\(4\) \(1\) \(5\) \(-26\)
\(2\) \(1\) \(-9\) \(47\)
\(0\) \(2\) stop

\(\gcd=2=240\cdot(-9)+46\cdot 47\). Check: \(-2160+2162=2\).

Example 4 — Diophantine equation.
Solve \(240x+46y=10\). \(\gcd=2\mid 10\). From \(240(-9)+46(47)=2\), multiply by \(5\): \(240(-45)+46(235)=10\). General: \[ x=-45+23k,\qquad y=235-120k,\quad k\in\mathbb{Z}. \]

Example 5 — No solution.
\(15x+25y=7\): \(\gcd=5\nmid 7\), impossible.

Example 6 — Inverse preview.
\(\gcd(7,26)=1\). Euclid: \(26=3\cdot7+5\), \(7=1\cdot5+2\), \(5=2\cdot2+1\), \(2=2\cdot1+0\). Back-sub: \[ 1=5-2\cdot2,\quad 2=7-5\Rightarrow 1=3\cdot5-2\cdot7,\quad 5=26-3\cdot7\Rightarrow 1=3\cdot26-11\cdot7. \] Inverse of \(7\) mod \(26\) is \(-11\equiv 15\). Check: \(7\cdot 15=105=4\cdot26+1\).

Example 7 — Fibonacci worst case.
\(F_8=21\), \(F_7=13\): \(21=1\cdot13+8\), \(13=1\cdot8+5\), \(8=1\cdot5+3\), \(5=1\cdot3+2\), \(3=1\cdot2+1\), \(2=2\cdot1+0\). Many steps for small inputs — the pattern of all quotients \(1\) is the slow case.

Example 8 — Prove \(\gcd(ca,cb)=|c|\gcd(a,b)\) for \(c\neq 0\).
By FTA, or: if \(d=\gcd(a,b)\) and \(ax+by=d\), then \(cax+cby=cd\), so \(\gcd(ca,cb)\mid |c|d\) wait — more carefully: common divisors of \(ca,cb\) are \(|c|\) times common divisors of \(a,b\) when carefully tracking signs. Using FTA is cleanest for this volume after Day 71.

Exercises

A. Plain Euclid

  1. Compute \(\gcd(1071,462)\) by Euclid; show every remainder step.
  2. Compute \(\gcd(12345,678)\).
  3. Compute \(\gcd(91,0)\) and \(\gcd(0,91)\).
  4. Prove carefully: \(\gcd(a,b)=\gcd(b,a-b)\) when \(a\ge b\ge 0\).
  5. Trace Euclid on \((F_{10},F_9)\). Count division steps.
  6. Run Euclid on \((100,35)\) and list the invariant gcd at each line.

B. Extended Euclid

  1. Find integers \(x,y\) with \(1071x+462y=\gcd(1071,462)\).
  2. Find Bézout coefficients for \((240,46)\) by back-substitution and confirm the table.
  3. Find \(x,y\) with \(17x+13y=1\). Then find the inverse of \(17\) modulo \(13\) and of \(13\) modulo \(17\).
  4. For \(a=99\), \(b=78\), compute \(d=\gcd\) and \(x,y\) with \(ax+by=d\).
  5. Show two different Bézout pairs for \(\gcd(15,25)=5\).
  6. Tabular extended Euclid for \((123,45)\).

C. Diophantine equations

  1. Determine whether \(14x+35y=21\) has integer solutions; if so, find the general solution.
  2. Same for \(14x+35y=20\).
  3. Find all positive integer solutions (if any) to \(6x+9y=21\) with \(x,y>0\).
  4. Prove: if \(ax+by=c\) is solvable and \(ab\neq 0\), then it has infinitely many solutions.
  5. Freight problem: “apples cost 6, oranges 10; total cost 44.” Cast as Diophantine; solve nonnegatively if possible.

D. Theory and proofs

  1. Prove that every common divisor of \(a\) and \(b\) divides \(\gcd(a,b)\), using Bézout.
  2. Prove Euclid’s lemma using Bézout: if \(p\) prime, \(p\mid ab\), \(p\nmid a\), then \(p\mid b\).
  3. Prove: \(\gcd(ca,cb)=|c|\gcd(a,b)\) for \(c\neq 0\).
  4. Prove that \(I=\{ax+by\}\) has least positive element equal to \(\gcd(a,b)\) (fill every gap in the proof above).
  5. CS literacy: explain why extended Euclid is the right tool to solve \(ax\equiv 1\pmod m\) when \(\gcd(a,m)=1\) (prose, no code).

E. Stretch

  1. Binary GCD idea (Stein): both even ⇒ factor \(2\); one even ⇒ drop \(2\) from that one; both odd ⇒ replace larger by \(|a-b|\). Hand-compute \(\gcd(48,18)\).
  2. How many steps does Euclid take on \((F_{12},F_{11})\)? Estimate via Lamé.
  3. Prove: the number of steps of Euclid on \((a,b)\) with \(a>b\ge 1\) is at most \(1+\log_\varphi(\sqrt{5}b)\) roughly — write a clean inequality from \(b\ge F_{k+1}\).
  4. Solve \(17x\equiv 1\pmod{100}\) by extended Euclid.

Deep dive — invariant as a correctness template

Think of Euclid as a loop with state \((a,b)\):

// mathematical pseudocode — not a lab
assert not both zero
while b ≠ 0:
    // invariant: gcd(a,b) equals original gcd
    (a,b) ← (b, a mod b)
return a

Loop invariant proof pattern (reusable in CS literacy):

  1. Initialization: invariant holds on entry.
  2. Maintenance: gcd recurrence preserves it.
  3. Termination: second coordinate is a strictly decreasing nonnegative integer.
  4. Exit: \(b=0\) ⇒ return \(a=\gcd(a,0)\).

Deep dive — complexity more carefully

Lamé (quantitative). If Euclid takes \(N\) divisions on \(a>b\ge 1\), then \(b\ge F_{N+1}\). Step count is \(O(\log b)\).

Why Fibonacci is worst. Quotients all equal to \(1\) minimize the drop: remainders follow a Fibonacci-like recurrence. Any quotient \(\ge 2\) shrinks faster.

Bit cost literacy. Schoolbook division of \(O(\log n)\)-bit integers is not \(O(1)\); total classical bit complexity of gcd is still far better than trial division up to \(b\). For this volume, \(O(\log n)\) steps is the required takeaway.

Deep dive — all solutions to \(ax+by=c\)

Once \(ax_0+by_0=d\) and \(d\mid c\), set \(x^*=x_0(c/d)\), \(y^*=y_0(c/d)\).
If \((x,y)\) is another solution, \(a(x-x^*)+b(y-y^*)=0\). Dividing by \(d\) and using \(\gcd(a/d,b/d)=1\) yields \[ x=x^*+(b/d)k,\qquad y=y^*-(a/d)k. \] Nonnegative solutions: restrict \(k\) so \(x,y\ge 0\) when \(a,b>0\) — typically a finite interval of \(k\).

Additional worked examples

Example 9 — \(\gcd(a,b)=\gcd(a,b+ka)\).
Common divisors match because \(b=(b+ka)-ka\).

Example 10 — Inverse of \(43\) mod \(100\).
\(100=2\cdot 43+14\), \(43=3\cdot 14+1\).
\(1=43-3\cdot 14=43-3(100-2\cdot 43)=7\cdot 43-3\cdot 100\).
Inverse \(\equiv 7\). Check: \(43\cdot 7=301\equiv 1\pmod{100}\).

Example 11 — Nonnegative Diophantine.
\(6x+9y=21\): \(d=3\mid 21\). From \(6(-1)+9(1)=3\), scale by \(7\): \(6(-7)+9(7)=21\).
General: \(x=-7+3k\), \(y=7-2k\). Nonnegative forces \(k=3\): \((x,y)=(2,1)\).

Example 12 — Fibonacci pair.
\((F_7,F_6)=(13,8)\): remainders \(5,3,2,1,0\) — many steps for small inputs.

Example 13 — Prove every common divisor divides the gcd via Bézout.
\(d=ax+by\) ⇒ any common divisor divides the right-hand side, hence divides \(d\).

More exercises

  1. Run tabular extended Euclid on \((321,123)\).
  2. Find all nonnegative solutions to \(4x+6y=20\).
  3. Prove: if \(ax+by=1\) then \(\gcd(a,b)=1\).
  4. CS literacy paragraph: why gcd speed matters for RSA keygen hygiene (reject bad primes) as an idea only.
  5. Compare number of steps of Euclid on \((89,55)\) vs \((90,54)\).
  6. Solve \(19x\equiv 1\pmod{100}\) by extended Euclid.

Selected mini-solutions

  1. \(1071=2\cdot 462+147\); \(462=3\cdot 147+21\); \(147=7\cdot 21\) ⇒ \(\gcd=21\).
  2. Inverse of \(43\) mod \(100\) is \(7\) (Example 10).
  3. Bézout: common divisors divide \(d\).
  4. Extended Euclid on \((17,100)\) (Day 74 style) yields inverse \(53\).

Common pitfalls

Pitfall Fix
Sign errors in back-substitution Check \(ax+by=d\) numerically every time
Stopping when remainder is \(1\) without coefficients Extended form needs the full chain
Claiming \(ax+by=c\) always solvable Need \(d\mid c\)
Using \(\gcd\) of negatives inconsistently Reduce to nonnegative inputs
Off-by-one in general solution \(\pm(b/d)k\) Derive once; stick to one convention
Confusing steps with bit operations \(O(\log n)\) steps is the right literacy level here
Forgetting to scale Bézout when \(c\neq d\) Multiply coefficients by \(c/d\)

Checkpoint

  • Can run Euclid and prove \(\gcd(a,b)=\gcd(b,a\bmod b)\)
  • Can explain termination + invariant correctness
  • Can state Fibonacci worst-case intuition and \(O(\log n)\)
  • Can produce Bézout coefficients by back-substitution or table
  • Can decide solvability of \(ax+by=c\) and write the general solution
  • Can prove Euclid’s lemma via Bézout
  • Exercises A–D done

Two personal takeaways:

  1. …
  2. …

Tomorrow

Day 73 — Modular arithmetic (congruences and operations).

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

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

C. Cancellation

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

D. Linear congruences

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

E. Stretch and CS literacy

  1. Prove: \(a\equiv b\pmod m\) and \(a\equiv b\pmod n\) ⇒ \(a\equiv b\pmod{\mathrm{lcm}(m,n)}\).
  2. 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\).
  3. CS: explain why hash = key % m places keys into \(m\) buckets and when consecutive keys collide systematically.
  4. CS: checksums mod \(9\) or mod \(11\) — what errors do they catch? (Prose.)
  5. 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

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

Selected mini-solutions

  1. \(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\).
  2. Inverse of \(5\) mod \(7\) is \(3\) (\(15\equiv 1\)); \(x\equiv 9\equiv 2\pmod 7\).
  3. \(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}\).
  4. \(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

  1. Prove: if \(a\equiv b\pmod n\) then \(a^2+a\equiv b^2+b\pmod n\).
  2. Solve \(21x\equiv 14\pmod{35}\).
  3. Find all complete residue systems mod \(4\) contained in \(\{0,1,\ldots,10\}\).
  4. Compute \(3^{20}\bmod 14\) by successive squaring (no Euler required).
  5. Show that \(10^k\equiv 1\pmod 9\) for all \(k\ge 0\); deduce the digit-sum rule.
  6. 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\).
  7. CS literacy: explain wrap-around of a 32-bit unsigned counter as arithmetic mod \(2^{32}\).
  8. 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.