Day 26 — Modular Inverses, Fermat/Euler & Hashing

Updated

July 30, 2025

Day 26 — Modular Inverses, Fermat/Euler & Hashing

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

Stage VII · concept day
Goal: Characterize when \(a^{-1}\) exists mod \(n\); compute inverses via extended Euclid; preview \(\varphi(n)\); understand the group of units; state and sketch Wilson’s theorem.

Why this matters

Inverses turn “multiply by \(a\)” into a reversible operation modulo \(n\). They unlock unique solutions of \(ax\equiv b\), the Chinese Remainder construction, and RSA’s decryption exponent. Wilson’s theorem is a classic primality characterization — a clean proof exercise and a culture marker for modular thinking.

Note

No labs. Hand computation of inverses and Wilson checks on small primes only.

Theory

Definition of inverse

Definition. An integer \(x\) is a multiplicative inverse of \(a\) modulo \(n\) if \[ ax\equiv 1\pmod n. \] We write \(x\equiv a^{-1}\pmod n\) (when it exists). Inverses are unique modulo \(n\) when they exist: if \(ax\equiv 1\) and \(ay\equiv 1\) then \(x\equiv x(ay)\equiv (xa)y\equiv y\pmod n\).

Existence criterion

Theorem. Let \(n>1\). The integer \(a\) has an inverse modulo \(n\) if and only if \(\gcd(a,n)=1\).

Proof.
(\(\Rightarrow\)) If \(ax\equiv 1\pmod n\) then \(ax-ny=1\) for some \(y\), so any common divisor of \(a\) and \(n\) divides \(1\), hence \(\gcd(a,n)=1\).
(\(\Leftarrow\)) If \(\gcd(a,n)=1\), Bézout gives \(ax+ny=1\), so \(ax\equiv 1\pmod n\).

Corollary. Every nonzero residue mod \(p\) (prime) is invertible: \(\mathbb{Z}/p\mathbb{Z}\) is a field.

Corollary. \(a\) is invertible mod \(n\) iff \([a]\) is a unit in the ring \(\mathbb{Z}/n\mathbb{Z}\).

Computing inverses

Method 1 — Extended Euclid. Run extended Euclid on \((a,n)\); if \(d=1\), the coefficient of \(a\) reduced mod \(n\) is \(a^{-1}\).

Method 2 — Trial for small \(n\): test \(x=1,2,\ldots,n-1\) until \(ax\equiv 1\pmod n\).

Method 3 — Euler (preview Day 75). If \(\gcd(a,n)=1\) then \(a^{\varphi(n)}\equiv 1\pmod n\), so \(a^{-1}\equiv a^{\varphi(n)-1}\pmod n\). Useful theoretically; extended Euclid is usually better by hand for small cases.

Units group and \(\varphi(n)\) preview

Definition. The set of invertible classes \[ (\mathbb{Z}/n\mathbb{Z})^\times = \{[a]:\gcd(a,n)=1\} \] forms a group under multiplication mod \(n\) (associative, identity \([1]\), inverses exist, closed: product of coprimes to \(n\) is coprime to \(n\)).

Definition (Euler’s totient, preview). \(\varphi(n)=|(\mathbb{Z}/n\mathbb{Z})^\times|\) = number of integers in \(\{1,\ldots,n-1\}\) coprime to \(n\) (for \(n>1\); \(\varphi(1)=1\)).

Examples. \(\varphi(p)=p-1\) for prime \(p\). \(\varphi(8)=4\) (units \(1,3,5,7\)). \(\varphi(15)=8\).

Product of invertibles. If \(a,b\) are invertible mod \(n\) then so is \(ab\), and \((ab)^{-1}\equiv b^{-1}a^{-1}\pmod n\).

Zero divisors (contrast)

If \(\gcd(a,n)=d>1\), then \(a\) is not invertible. Moreover if \(n\) is composite, zero divisors appear: e.g. \(2\cdot 3\equiv 0\pmod 6\) with neither factor \(0\) mod \(6\). In \(\mathbb{Z}/p\mathbb{Z}\) there are no zero divisors.

Solving \(ax\equiv b\) when invertible

If \(\gcd(a,n)=1\), multiply both sides by \(a^{-1}\): \[ x\equiv a^{-1}b\pmod n. \] Unique solution.

Wilson’s theorem

Theorem (Wilson). An integer \(p>1\) is prime if and only if \[ (p-1)!\equiv -1\pmod p. \]

Proof sketch (\(p\) prime ⇒ congruence).
If \(p=2\): \(1!\equiv 1\equiv -1\pmod 2\). If \(p=3\): \(2!\equiv 2\equiv -1\pmod 3\).
Assume \(p\ge 5\). In \(\{1,2,\ldots,p-1\}\), each \(a\) has a unique inverse mod \(p\). Pair \(a\) with \(a^{-1}\) when \(a\not\equiv a^{-1}\). The fixed points of inversion satisfy \(a^2\equiv 1\pmod p\) ⇒ \((a-1)(a+1)\equiv 0\) ⇒ \(a\equiv\pm 1\pmod p\) (field, no zero-divisor issues). So only \(1\) and \(p-1\) are their own inverses. The product \((p-1)!\) pairs into pairs \(\equiv 1\), times \(1\cdot(p-1)\equiv -1\pmod p\).

Converse sketch. If \(n>1\) is composite and \(n\neq 4\), then \((n-1)!\equiv 0\pmod n\) (because two distinct factors of \(n\) appear among \(1,\ldots,n-1\), or a square factor with multiplicity). For \(n=4\): \(3!=6\equiv 2\not\equiv -1\pmod 4\). So if \((n-1)!\equiv -1\pmod n\) then \(n\) is prime.

Use. Beautiful characterization; not a practical primality test for large \(p\) (\(p!\) is huge).

Worked examples

Example 1 — Inverse via trial.
Inverse of \(3\) mod \(7\): \(3\cdot 5=15\equiv 1\), so \(3^{-1}\equiv 5\pmod 7\).

Example 2 — Extended Euclid.
Inverse of \(17\) mod \(100\): \(\gcd(17,100)=1\). Euclid: \[ \begin{align*} 100&=5\cdot 17+15,\\ 17&=1\cdot 15+2,\\ 15&=7\cdot 2+1,\\ 2&=2\cdot 1+0. \end{align*} \] Back-sub: \(1=15-7\cdot 2=15-7(17-15)=8\cdot 15-7\cdot 17=8(100-5\cdot 17)-7\cdot 17=8\cdot 100-47\cdot 17\).
So \(-47\cdot 17\equiv 1\pmod{100}\), inverse \(\equiv -47\equiv 53\). Check: \(17\cdot 53=901=9\cdot 100+1\).

Example 3 — No inverse.
\(6\) mod \(15\): \(\gcd(6,15)=3\neq 1\). No inverse. Indeed \(6x\) is always a multiple of \(3\), never \(\equiv 1\pmod{15}\).

Example 4 — Solve \(7x\equiv 3\pmod{26}\).
From Day 72, \(7^{-1}\equiv 15\pmod{26}\). Then \(x\equiv 45\equiv 19\pmod{26}\). Check: \(7\cdot 19=133=5\cdot 26+3\).

Example 5 — Units mod \(10\).
\((\mathbb{Z}/10\mathbb{Z})^\times=\{1,3,7,9\}\). Products: \(3\cdot 7=21\equiv 1\), so they are inverses. \(9\cdot 9=81\equiv 1\).

Example 6 — Wilson small primes.
\(p=5\): \(4!=24\equiv 4\equiv -1\pmod 5\).
\(p=7\): \(6!=720\). \(720/7=102\cdot 7=714\), remainder \(6\equiv -1\).
\(p=4\) composite: \(6\equiv 2\not\equiv -1\pmod 4\).

Example 7 — Wilson pairing for \(p=11\).
\(10!\); pairs \((2,6)\) because \(2\cdot 6=12\equiv 1\); \((3,4)\); \((5,9)\); \((7,8)\); singles \(1\) and \(10\equiv -1\). Product of pairs \(\equiv 1^4\), times \(-1\).

Example 8 — Inverse of product.
Mod \(13\): \(3^{-1}\equiv 9\) (\(27\equiv 1\)), \(4^{-1}\equiv 10\) (\(40\equiv 1\)). Then \((12)^{-1}=(3\cdot 4)^{-1}\equiv 9\cdot 10=90\equiv 12\pmod{13}\). Check \(12\cdot 12=144\equiv 1\) because \(144-11\cdot 13=144-143=1\). And \(12\equiv -1\), \((-1)^{-1}\equiv -1\equiv 12\).

Exercises

A. Existence and nonexistence

  1. Which of \(1,2,3,4,5,6\) are invertible mod \(7\)? mod \(8\)? mod \(9\)?
  2. Prove uniqueness of inverses mod \(n\) when they exist.
  3. Prove: if \(ab\equiv 1\pmod n\) then \(\gcd(a,n)=\gcd(b,n)=1\).
  4. Show that if \(a\equiv b\pmod n\) and \(a\) is invertible then \(b\) is invertible and \(a^{-1}\equiv b^{-1}\pmod n\).
  5. Prove \((\mathbb{Z}/n\mathbb{Z})^\times\) is closed under multiplication.

B. Computing inverses

  1. Find \(5^{-1}\bmod 12\) if it exists.
  2. Find \(11^{-1}\bmod 26\) by extended Euclid.
  3. Find \(7^{-1}\bmod 15\) by trial and by extended Euclid.
  4. Find inverses of all units mod \(14\).
  5. Solve \(11x\equiv 5\pmod{26}\).
  6. Solve \(9x\equiv 6\pmod{15}\) (note \(\gcd\neq 1\) — use Day 73 method).

C. Units and \(\varphi\)

  1. List \((\mathbb{Z}/15\mathbb{Z})^\times\) and compute \(\varphi(15)\).
  2. Verify that every element of \((\mathbb{Z}/15\mathbb{Z})^\times\) has an inverse in the set (table or pairs).
  3. Prove: if \(\gcd(a,n)=1\) and \(\gcd(b,n)=1\) then \(\gcd(ab,n)=1\).
  4. For \(n=p\) prime, show \(|(\mathbb{Z}/p\mathbb{Z})^\times|=p-1\).
  5. Find an element of order… (preview) smallest \(k>0\) with \(3^k\equiv 1\pmod 7\).

D. Wilson’s theorem

  1. Verify Wilson for \(p=13\) by computing \(12!\bmod 13\) using pairing (do not expand \(12!\) fully if you can pair).
  2. Show \((n-1)!\equiv 0\pmod n\) for composite \(n=15\).
  3. Explain why \(n=4\) is the exceptional composite in the converse argument.
  4. Using Wilson, prove: if \(p\) is an odd prime then \(\binom{p-1}{k}\equiv (-1)^k\pmod p\) for \(0\le k\le p-1\) (optional stretch outline: relate factorials).
  5. Prove the ⇒ direction of Wilson carefully for general prime \(p\), writing the pairing argument in full sentences.

E. Stretch and literacy

  1. Prove: \(a\) has an inverse mod \(n\) iff the map \(x\mapsto ax\bmod n\) is bijective on a complete residue system.
  2. For RSA literacy (Day 77): if \(\gcd(e,\varphi(n))=1\), why does \(e\) have an inverse \(d\) mod \(\varphi(n)\)? (One paragraph.)
  3. Show that \(a^{p-2}\equiv a^{-1}\pmod p\) for prime \(p\nmid a\) (Fermat preview).
  4. Compute \(100!\bmod 101\) using Wilson (\(101\) is prime).

Deep dive — units group structure (culture)

\((\mathbb{Z}/n\mathbb{Z})^\times\) is always a finite abelian group under multiplication. Structure theorems (cyclic vs product of cyclics) matter for primitive roots and crypto group choice — awareness only. What you must own:

  • Closure, identity, inverses.
  • Order of the group is \(\varphi(n)\).
  • Lagrange literacy preview: order of an element divides \(\varphi(n)\) (Day 75 makes this precise via Euler).

Deep dive — Wilson pairing fully written (\(p=13\))

Residues \(1,\ldots,12\). Self-inverse: \(1\) and \(12\equiv -1\).
Pairs with product \(\equiv 1\pmod{13}\):
\((2,7)\) because \(14\equiv 1\); \((3,9)\) (\(27\equiv 1\)); \((4,10)\); \((5,8)\); \((6,11)\).
Product \(12!\equiv 1\cdot(12)\cdot 1^{5}\equiv -1\pmod{13}\).

Deep dive — zero divisors vs units partition

For each \(a\bmod n\):

Condition Status
\(\gcd(a,n)=1\) Unit (invertible)
\(\gcd(a,n)>1\) Not invertible; if \(n\) composite, often a zero divisor

Example mod \(12\): units \(\{1,5,7,11\}\); \(2\cdot 6\equiv 0\), \(3\cdot 4\equiv 0\), \(8\cdot 3\equiv 0\).

Additional worked examples

Example 9 — Inverse table mod \(9\).
Units: \(1,2,4,5,7,8\). Inverses: \(1^{-1}=1\), \(2^{-1}=5\), \(4^{-1}=7\), \(5^{-1}=2\), \(7^{-1}=4\), \(8^{-1}=8\) (since \(8\equiv -1\)).

Example 10 — Solve \(13x\equiv 7\pmod{31}\).
\(31\) prime, inv of \(13\) mod \(31\) via extended Euclid: \(31=2\cdot 13+5\), \(13=2\cdot 5+3\), \(5=1\cdot 3+2\), \(3=1\cdot 2+1\). Back-sub carefully → verify final \(x\) by multiplication.

Example 11 — Wilson fails composite.
\(n=9\): \(8!=40320\). \(40320/9=4480\) exactly ⇒ \(8!\equiv 0\not\equiv -1\pmod 9\).

Example 12 — Product of units.
Mod \(15\): \(4\) not a unit; \(2\cdot 8=16\equiv 1\) so \(2\) and \(8\) are units and inverses.

More exercises

  1. Build the full multiplication table of \((\mathbb{Z}/7\mathbb{Z})^\times\).
  2. Find \(19^{-1}\bmod 100\).
  3. Prove: if \(a^2\equiv 1\pmod p\) for prime \(p\) then \(a\equiv\pm 1\pmod p\).
  4. For which \(n\) is \(-1\) a square mod \(n\)? (Exploration; not full theory.)
  5. CS: why “multiply by modular inverse” appears when solving linear congruences in hash arithmetic ideas.
  6. Compute \((p-1)!\bmod p\) for \(p=17\) using Wilson (answer \(-1\)).
  7. Show there is no inverse of \(10\) mod \(25\); describe the image of \(x\mapsto 10x\bmod 25\).

Selected mini-solutions

  1. \(\gcd(5,12)=1\); trial: \(5\cdot 5=25\equiv 1\) so inv \(5\).
  2. \(\gcd(7,15)=1\); \(7\cdot 13=91\equiv 1\pmod{15}\).
  3. Units mod \(15\): \(1,2,4,7,8,11,13,14\); \(\varphi(15)=8\).
  4. Wilson: \(100!\equiv -1\pmod{101}\).

Common pitfalls

Pitfall Fix
Claiming every nonzero has inverse mod composite \(n\) Need coprime to \(n\)
Inverse of \(a\) is \(1/a\) in rationals Must be integer solution to \(ax\equiv 1\)
Sign error after extended Euclid Reduce mod \(n\) to \(\{0,\ldots,n-1\}\) and verify
Wilson as primality test for large \(p\) Impractical; use as theorem only
Forgetting \(p=2,3\) base cases in Wilson Handle small primes separately
Cancelling in Wilson product incorrectly Only cancel invertibles

Study notes — inverses at a glance

Task Tool
Does \(a^{-1}\) exist mod \(n\)? \(\gcd(a,n)=1\)
Compute inverse Extended Euclid
Solve \(ax\equiv b\) (coprime case) \(x\equiv a^{-1}b\)
Count units \(\varphi(n)\)
Primality identity Wilson \((p-1)!\equiv -1\pmod p\)

Memory hook: invertible ⇔ coprime ⇔ Bézout gives \(1\) ⇔ multiplication-by-\(a\) is bijective mod \(n\).

Synthesis — inverse & Wilson workout

S1. Prove: \(a\) invertible mod \(n\) iff the map \(x\mapsto ax\bmod n\) is bijective on \(\{0,\ldots,n-1\}\).

S2. Compute \(29^{-1}\bmod 100\) by extended Euclid; verify by multiplication.

S3. List \((\mathbb{Z}/16\mathbb{Z})^\times\) and pair each unit with its inverse.

S4. Solve \(11x\equiv 9\pmod{26}\) using an inverse.

S5. Write the Wilson pairing proof for general prime \(p\ge 5\) in full sentences (no “etc.”).

S6. Show \((n-1)!\equiv 0\pmod n\) for composite \(n=25\).

S7. If \(ab\equiv 1\pmod n\) and \(ac\equiv 1\pmod n\), prove \(b\equiv c\pmod n\).

S8. CS literacy: “division mod \(n\)” means multiply by inverse — when is division legal?

Checkpoint

  • Can state and prove existence criterion \(\gcd(a,n)=1\)
  • Can compute inverses by extended Euclid and by trial
  • Can solve \(ax\equiv b\) by multiplying by \(a^{-1}\) when coprime
  • Know units \((\mathbb{Z}/n\mathbb{Z})^\times\) and \(\varphi(n)\) as their count
  • Can state Wilson and sketch the pairing proof
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — uniqueness of inverses (full write-up)

Theorem. If \(ax\equiv 1\pmod n\) and \(ay\equiv 1\pmod n\), then \(x\equiv y\pmod n\).

Proof. \(x\equiv x\cdot 1\equiv x(ay)=(xa)y\equiv 1\cdot y\equiv y\pmod n\).

Corollary. The inverse map on \((\mathbb{Z}/n\mathbb{Z})^\times\) is a well-defined function: each unit has exactly one inverse class.

Deeper theory — Wilson converse for composite \(n\neq 4\)

Claim. If \(n>1\) is composite and \(n\neq 4\), then \((n-1)!\equiv 0\pmod n\), hence \(\not\equiv -1\pmod n\) (since \(n>1\) ⇒ \(0\not\equiv -1\)).

Case 1. \(n\) has two distinct prime factors, or more generally \(n=ab\) with \(1<a\le b<n\) and \(a\neq b\). Then both \(a\) and \(b\) appear as factors in \((n-1)!\), so \(n\mid(n-1)!\).

Case 2. \(n=p^k\) with \(k\ge 2\) and \(n\neq 4\). If \(p^k>4\), then either \(p\) and \(2p\) both appear in \(1,\ldots,n-1\) (when \(2p<n\), true for \(p^k\ge 9\)), or for \(p=2\), \(k\ge 3\) (\(n\ge 8\)): \(2,4,6\) all appear and supply enough factors of \(2\) to make \(n\mid(n-1)!\). (Standard number-theory write-ups spell each subcase; the moral is composite \(n\neq 4\) forces \(n\) to divide \((n-1)!\).)

Exception \(n=4\): \(3!=6\equiv 2\not\equiv 0\pmod 4\) and \(2\not\equiv -1\pmod 4\).

Worked example — full extended Euclid inverse

Example 13 — Inverse of \(29\) mod \(100\).
\[ \begin{align*} 100&=3\cdot 29+13,\\ 29&=2\cdot 13+3,\\ 13&=4\cdot 3+1,\\ 3&=3\cdot 1+0. \end{align*} \] Back-sub: \(1=13-4\cdot 3=13-4(29-2\cdot 13)=9\cdot 13-4\cdot 29=9(100-3\cdot 29)-4\cdot 29=9\cdot 100-31\cdot 29\).
So \(-31\cdot 29\equiv 1\pmod{100}\), inverse \(\equiv 69\). Check: \(29\cdot 69=2001=20\cdot 100+1\). ✓

Example 14 — Solve \(29x\equiv 7\pmod{100}\).
\(x\equiv 7\cdot 69=483\equiv 83\pmod{100}\). Check: \(29\cdot 83=2407=24\cdot 100+7\). ✓

Example 15 — Units mod \(16\).
Odd residues: \(1,3,5,7,9,11,13,15\). All invertible (odd = coprime to \(2^4\)). Pair inverses: \(1\cdot 1\), \(15\cdot 15\) (\(225\equiv 1\)), \(7\cdot 7=49\equiv 1\), \(9\cdot 9=81\equiv 1\), \(3\cdot 11=33\equiv 1\), \(5\cdot 13=65\equiv 1\).

Extra exercises — inverse mastery

  1. Find \(41^{-1}\bmod 100\) by extended Euclid; verify.
  2. Build the inverse table for \((\mathbb{Z}/11\mathbb{Z})^\times\).
  3. Prove: if \(a^{-1}\equiv a\pmod n\) then \(a^2\equiv 1\pmod n\).
  4. For prime \(p\), show \((p-2)!\equiv 1\pmod p\) using Wilson.
  5. Solve \(15x\equiv 4\pmod{28}\) (first check invertibility of \(15\)).
  6. Prove that \([a]\) is a unit in \(\mathbb{Z}/n\mathbb{Z}\) iff multiplication-by-\(a\) is injective on \(\mathbb{Z}/n\mathbb{Z}\).
  7. Wilson: verify \(p=17\) by pairing (list pairs product \(\equiv 1\)).
  8. CS: “division by \(7\) mod \(10^9+7\)” in contest programming means multiply by \(7^{-1}\) — when does that inverse exist?

Mini-solutions (selected)

  1. \((p-1)!\equiv -1\) ⇒ \((p-1)(p-2)!\equiv -1\) ⇒ \((-1)(p-2)!\equiv -1\) ⇒ \((p-2)!\equiv 1\pmod p\).
  2. \(\gcd(15,28)=1\); inv of \(15\) mod \(28\) via Euclid; then multiply by \(4\).
  3. Exists iff \(\gcd(7,10^9+7)=1\); often \(10^9+7\) is prime, so yes for \(7\not\equiv 0\).

Closing synthesis card

Skill Check
Existence ⇔ \(\gcd=1\) □
Extended Euclid inverse □
Units group + \(\varphi\) count □
Wilson pairing sketch □
Solve \(ax\equiv b\) via inverse □

Tomorrow

Day 75 — Fermat’s little theorem, Euler’s theorem, totient, order.

Day 75 — Fermat’s little theorem, Euler’s theorem, totient, and order

Stage VII · concept day
Goal: Prove/sketch Fermat; state Euler; compute \(\varphi(n)\) for \(p\), \(p^k\), and coprime products; reduce huge exponents; define the multiplicative order of \(a\) mod \(n\).

Why this matters

Exponent reduction is the workhorse of modular powering: RSA literacy, Diffie–Hellman, and simple “last digit / cycle” problems all need Fermat or Euler. Totient arithmetic explains why key exponents live mod \(\varphi(n)\). Order measures the period of powering — the discrete seed of cyclic-group thinking.

Note

No labs. Hand modular exponentiation only. Toy moduli.

Theory

Fermat’s little theorem

Theorem (Fermat). If \(p\) is prime and \(p\nmid a\), then \[ a^{p-1}\equiv 1\pmod p. \] Equivalently (for all integers \(a\)): \(a^p\equiv a\pmod p\).

Proof sketch (multiplication of units).
If \(p\nmid a\), the residues \(a,2a,\ldots,(p-1)a\) are a permutation of \(1,2,\ldots,p-1\) modulo \(p\) (all nonzero, pairwise distinct because \(p\) prime). Multiply: \[ a^{p-1}(p-1)!\equiv (p-1)!\pmod p. \] Cancel \((p-1)!\) (invertible mod \(p\) by Wilson or because \(p\) prime doesn’t divide it): \(a^{p-1}\equiv 1\pmod p\).

Alternate form. \(a^p\equiv a\pmod p\) holds even if \(p\mid a\) (both sides \(0\)).

Consequence. If \(p\nmid a\) then \(a^{-1}\equiv a^{p-2}\pmod p\).

Euler’s totient function

Definition. \(\varphi(n)=\#\{k:1\le k\le n,\ \gcd(k,n)=1\}\) for \(n\ge 1\) (with \(\varphi(1)=1\)).

Formulas.

  1. Prime: \(\varphi(p)=p-1\).
  2. Prime power: \(\varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)\).
    (Count: total \(p^k\) residues \(0,\ldots,p^k-1\); subtract multiples of \(p\): there are \(p^{k-1}\) of them.)
  3. Multiplicative: if \(\gcd(m,n)=1\) then \(\varphi(mn)=\varphi(m)\varphi(n)\).
  4. General FTA: if \(n=\prod p_i^{e_i}\) then \[ \varphi(n)=n\prod_{p\mid n}\Bigl(1-\frac{1}{p}\Bigr)=\prod_i p_i^{e_i-1}(p_i-1). \]

Examples. \(\varphi(12)=\varphi(2^2\cdot 3)=12(1-1/2)(1-1/3)=4\). Units: \(1,5,7,11\).
\(\varphi(100)=\varphi(2^2 5^2)=100(1/2)(4/5)=40\).

Euler’s theorem

Theorem (Euler). If \(\gcd(a,n)=1\) then \[ a^{\varphi(n)}\equiv 1\pmod n. \]

Proof sketch. Let \(r_1,\ldots,r_{\varphi(n)}\) be a reduced residue system mod \(n\). Then \(ar_1,\ldots,ar_{\varphi(n)}\) is also a reduced residue system (multiplication by unit permutes units). Product: \[ a^{\varphi(n)}\prod r_i\equiv \prod r_i\pmod n. \] Cancel \(\prod r_i\) (product of units is a unit). Done.

Fermat is the special case \(n=p\), \(\varphi(p)=p-1\).

Caution. Need \(\gcd(a,n)=1\). Counterexample: \(2^{\varphi(8)}=2^4=16\equiv 0\not\equiv 1\pmod 8\).

Reducing huge exponents

If \(\gcd(a,n)=1\): \(a^k=a^{q\cdot\varphi(n)+r}=(a^{\varphi(n)})^q\cdot a^r\equiv 1^q\cdot a^r\equiv a^r\pmod n\) where \(r=k\bmod\varphi(n)\).

If \(n=p\) prime: reduce exponent mod \(p-1\) when \(p\nmid a\).

Chinese Remainder style (literacy): for composite \(n\), sometimes compute \(a^k\bmod p_i^{e_i}\) separately and recombine (Day 78).

When \(\gcd(a,n)\neq 1\): Euler does not apply; use CRT, factorization, or direct patterns.

Order of \(a\) modulo \(n\)

Definition. Let \(\gcd(a,n)=1\). The multiplicative order of \(a\) modulo \(n\), written \(\mathrm{ord}_n(a)\) or \(\mathrm{order}(a\bmod n)\), is the smallest positive integer \(k\) such that \[ a^k\equiv 1\pmod n. \]

Theorem (order divides \(\varphi(n)\)). \(\mathrm{ord}_n(a)\) exists (by Euler, some positive power is \(1\)) and divides \(\varphi(n)\). More generally: \(a^m\equiv 1\pmod n\) iff \(\mathrm{ord}_n(a)\mid m\).

Proof of “divides”. Write \(m=q\cdot\mathrm{ord}+r\) with \(0\le r<\mathrm{ord}\). Then \(a^m=(a^{\mathrm{ord}})^q a^r\equiv a^r\equiv 1\) forces \(r=0\) by minimality of order.

Corollary. Possible orders of units mod \(n\) are the positive divisors of \(\varphi(n)\).

Primitive roots (awareness). If there exists \(g\) with \(\mathrm{ord}_n(g)=\varphi(n)\), then \(g\) is a primitive root mod \(n\). Exist for \(n=2,4,p^k,2p^k\) (odd prime \(p\)) — statement only; not required to prove.

Worked examples

Example 1 — Fermat.
\(3^{6}\equiv 1\pmod 7\) since \(7-1=6\). Check: \(3^1=3\), \(3^2=2\), \(3^3=6\equiv -1\), \(3^6\equiv 1\pmod 7\).

Example 2 — Reduce \(3^{100}\bmod 7\).
\(100=16\cdot 6+4\), so \(3^{100}\equiv 3^4\equiv 81\equiv 4\pmod 7\) (since \(3^6\equiv 1\)). Or \(3^4=(3^2)^2\equiv 2^2=4\).

Example 3 — \(2^{100}\bmod 17\).
\(17\) prime, \(2^{16}\equiv 1\pmod{17}\). \(100=6\cdot 16+4\), so \(2^{100}\equiv 2^4=16\equiv -1\pmod{17}\).

Example 4 — Totient.
\(\varphi(36)=\varphi(2^2 3^2)=36(1-1/2)(1-1/3)=12\).
\(\varphi(p^3)=p^2(p-1)\) for prime \(p\).

Example 5 — Euler.
\(\gcd(7,10)=1\), \(\varphi(10)=4\), so \(7^4\equiv 1\pmod{10}\). Indeed last digit of powers of \(7\): \(7,9,3,1\) cycle length \(4\). Thus \(7^{402}=7^{4\cdot 100+2}\equiv 7^2\equiv 9\pmod{10}\).

Example 6 — Inverse via Euler.
\(7^{-1}\bmod 10\): \(7^{3}\equiv 343\equiv 3\pmod{10}\)? Better: \(7^{\varphi(10)-1}=7^3=343\equiv 3\), and \(7\cdot 3=21\equiv 1\). Yes.

Example 7 — Order of \(2\) mod \(7\).
\(2^1=2\), \(2^2=4\), \(2^3=1\pmod 7\). Order \(3\), and \(3\mid 6=\varphi(7)\).

Example 8 — Order of \(3\) mod \(10\).
\(3^1=3\), \(3^2=9\), \(3^3=7\), \(3^4=1\pmod{10}\). Order \(4=\varphi(10)\).

Example 9 — Failure without coprimality.
\(2^{\varphi(12)}=2^4=16\equiv 4\not\equiv 1\pmod{12}\). \(\gcd(2,12)\neq 1\).

Example 10 — \(a^p\equiv a\pmod p\) for \(a=14\), \(p=5\).
\(14\equiv 4\), \(4^5=1024\), \(1024\bmod 5\): \(4\equiv -1\), \((-1)^5=-1\equiv 4\pmod 5\). Also \(14\equiv 4\).

Exercises

A. Fermat

  1. Compute \(2^{10}\bmod 11\) two ways (direct and Fermat).
  2. Compute \(5^{30}\bmod 13\).
  3. Prove: if \(p\) prime and \(p\nmid a\) then \(a^{p-2}\equiv a^{-1}\pmod p\).
  4. Show \(a^p\equiv a\pmod p\) for \(p\mid a\) and for \(p\nmid a\) (combine cases).
  5. Find \(2^{1000}\bmod 13\).

B. Totient

  1. Compute \(\varphi(n)\) for \(n=1,2,3,4,5,6,7,8,9,10,12,15,16,100\).
  2. Prove \(\varphi(p^k)=p^k-p^{k-1}\) by counting.
  3. Using multiplicativity, prove the product formula \(\varphi(n)=n\prod_{p\mid n}(1-1/p)\).
  4. For which \(n\) is \(\varphi(n)\) odd? (Almost never — characterize.)
  5. Show \(\sum_{d\mid n}\varphi(d)=n\) (hint: cycle lengths / fractions \(k/n\) in lowest terms) — stretch proof or accept as fact and verify for \(n=12\).

C. Euler and reduction

  1. Compute \(3^{100}\bmod 10\).
  2. Compute \(7^{123}\bmod 10\).
  3. Compute \(2^{20}\bmod 21\) carefully — note \(\gcd(2,21)=1\) and \(\varphi(21)=\varphi(3)\varphi(7)=2\cdot 6=12\), so reduce exp mod \(12\).
  4. Why can’t you reduce the exponent of \(2\) mod \(\varphi(8)=4\) to get \(2^k\bmod 8\) for large \(k\)? What is the actual pattern of \(2^k\bmod 8\) for \(k\ge 3\)?
  5. Find \(10^{75}\bmod 21\) using \(\varphi\) if valid; if not, use CRT (optional) or another method.

D. Order

  1. Compute \(\mathrm{ord}_7(a)\) for \(a=1,2,3,4,5,6\).
  2. Compute \(\mathrm{ord}_{13}(2)\) and verify it divides \(12\).
  3. Prove: if \(a^m\equiv 1\pmod n\) and \(k=\mathrm{ord}_n(a)\) then \(k\mid m\).
  4. Prove: \(\mathrm{ord}_n(a^j)=k/\gcd(j,k)\) where \(k=\mathrm{ord}_n(a)\) (standard order lemma — sketch).
  5. Is there a primitive root mod \(8\)? List orders of all units mod \(8\).

E. Stretch and CS literacy

  1. RSA setup preview: if \(n=pq\), explain why working exponents mod \(\varphi(n)=(p-1)(q-1)\) is the right place for \(ed\equiv 1\).
  2. Diffie–Hellman preview: if \(g\) has large order mod \(p\), why does “order large” matter for the discrete log story (prose)?
  3. Prove Euler’s theorem carefully with full sentences (permutation of reduced residues).
  4. Compute \(3^{1000000}\bmod 7\) and mod \(13\), then combine with CRT if you know Day 78 early.
  5. Show that if \(\mathrm{ord}_n(a)=k\) and \(\mathrm{ord}_n(b)=\ell\) with \(\gcd(k,\ell)=1\) and \(ab\equiv ba\), it is not always true that \(\mathrm{ord}_n(ab)=k\ell\) — find conditions or a counterexample (stretch).

Deep dive — exponent reduction recipe card

Goal: compute a^k mod n
1. Reduce a ← a mod n
2. If gcd(a,n)=1:
      e ← φ(n)           // or p-1 if n=p prime
      r ← k mod e
      compute a^r mod n  // binary exponentiation by hand for small
3. If gcd(a,n)>1:
      do NOT use Euler blindly
      options: CRT if n factors; direct pattern; raise carefully

Binary exponentiation (hand). Write \(k\) in binary; successive square \(a, a^2, a^4, \ldots\); multiply factors where bits are \(1\).

Deep dive — order divides \(\varphi(n)\) fully

Let \(k=\mathrm{ord}_n(a)\). By Euler, \(a^{\varphi(n)}\equiv 1\), so the set \(S=\{m\ge 1:a^m\equiv 1\pmod n\}\) is nonempty. \(k=\min S\).
Write \(\varphi(n)=qk+r\), \(0\le r<k\). Then \(1\equiv a^{\varphi(n)}\equiv (a^k)^q a^r\equiv a^r\). Minimality ⇒ \(r=0\). Hence \(k\mid\varphi(n)\).

Corollary. Orders are among the divisors of \(\varphi(n)\) — search only those candidates when computing order by hand.

Additional worked examples

Example 11 — \(\varphi\) multiplicative check.
\(\varphi(36)=\varphi(4\cdot 9)=\varphi(4)\varphi(9)=2\cdot 6=12\) since \(\gcd(4,9)=1\). Direct: units mod \(36\) among \(1..35\) coprime to \(2\) and \(3\).

Example 12 — Last two digits of \(7^{100}\).
Need \(7^{100}\bmod 100\). \(\gcd(7,100)=1\), \(\varphi(100)=40\), \(100\equiv 20\pmod{40}\), so \(7^{100}\equiv 7^{20}\bmod 100\). Compute \(7^2=49\), \(7^4=2401\equiv 01\) wait \(01\)? \(2401\) yes \(\equiv 01\pmod{100}\)? \(2401-24\cdot 100=2401-2400=1\). So \(7^4\equiv 1\pmod{100}\)? Check \(7^4=2401\) yes. Then order divides \(4\), and \(7^{20}=(7^4)^5\equiv 1\). So last two digits \(01\).

Example 13 — Order of \(2\) mod \(17\).
\(2^8=256\equiv 1\pmod{17}\)? \(17\cdot 15=255\), yes \(256\equiv 1\). Is smaller? Divisors of \(8\): \(2^4=16\equiv -1\neq 1\), \(2^2=4\neq 1\). Order \(8\), and \(8\mid 16=\varphi(17)\).

Example 14 — Fermat for inverse.
\(5^{-1}\bmod 17\equiv 5^{15}\bmod 17\). Or \(5^{p-2}=5^{15}\). Easier trial: \(5\cdot 7=35\equiv 1\), inv \(7\).

Example 15 — Euler failure.
\(4^{\varphi(6)}=4^2=16\equiv 4\not\equiv 1\pmod 6\).

More exercises

  1. Compute \(2^{100}\bmod 101\) (\(101\) prime).
  2. Compute \(\varphi(720)\) using FTA.
  3. Find all orders of units mod \(9\).
  4. Prove: if \(\mathrm{ord}_n(a)=k\) then \(a^j\equiv a^i\pmod n\) iff \(k\mid(j-i)\) (for the cyclic powers).
  5. RSA literacy: why \(m^{k\varphi(n)+1}\equiv m\pmod n\) under coprimality.
  6. Reduce \(3^{1000}\bmod 14\) carefully (note \(\gcd(3,14)=1\), \(\varphi(14)=6\)).
  7. Show \(a^{n}\equiv a\pmod n\) is not always true (unlike Fermat’s \(a^p\equiv a\pmod p\)) — find composite counterexample (Carmichael numbers culture optional).

Selected mini-solutions

  1. \(5^{12}\equiv 1\pmod{13}\), \(30=2\cdot 12+6\), \(5^{30}\equiv 5^6\pmod{13}\).
  2. \(\varphi(100)=40\), \(\varphi(16)=8\), \(\varphi(15)=8\).
  3. Orders mod \(7\): \(1\) has order \(1\); \(2\) has order \(3\); \(3\) has order \(6\) (primitive root), etc.
  4. Units mod \(8\): \(1,3,5,7\) all square to \(1\); no element order \(4=\varphi(8)\); no primitive root.

Common pitfalls

Pitfall Fix
Applying Euler when \(\gcd(a,n)>1\) Check coprimality first
Reducing exponent mod \(n\) instead of mod \(\varphi(n)\) Exponents live mod \(\varphi(n)\) (when coprime)
\(\varphi(p^k)=p^k-1\) Wrong: \(p^k-p^{k-1}\)
Confusing order with discrete log Order is min \(k\) with \(a^k\equiv 1\); dlog solves \(g^x\equiv h\)
Using Fermat mod composite Need Euler or CRT
Stopping order search at \(\varphi(n)\) without checking divisors Order divides \(\varphi(n)\); check divisors

Study notes — exponent reduction at a glance

Setting Reduce exponent mod Hypothesis
Fermat \(p-1\) \(p\) prime, \(p\nmid a\)
Euler \(\varphi(n)\) \(\gcd(a,n)=1\)
Order — \(\mathrm{ord}_n(a)\mid m\) iff \(a^m\equiv 1\)

\(\varphi\) formulas: \(p-1\); \(p^{k-1}(p-1)\); multiplicative on coprime factors; \(n\prod_{p\mid n}(1-1/p)\).

Quick check: after reducing \(a^k\bmod n\), always verify a small related power by hand when \(n\) is tiny.

Synthesis — Fermat / Euler / order workout

S1. Compute \(2^{50}\bmod 13\) two ways (Fermat; successive square).

S2. Compute \(\varphi(360)\) via FTA.

S3. Reduce \(9^{100}\bmod 10\) (last digit) using Euler or cycles.

S4. Find \(\mathrm{ord}_{11}(2)\) by testing divisors of \(10\).

S5. Prove: if \(\mathrm{ord}_n(a)=k\) and \(a^m\equiv 1\pmod n\) then \(k\mid m\).

S6. Explain why \(2^{7}\equiv 2\pmod 8\) does not contradict Euler (hypotheses).

S7. Use \(a^{p-2}\equiv a^{-1}\pmod p\) to find \(6^{-1}\bmod 13\).

S8. RSA literacy paragraph: role of \(\varphi(n)\) in choosing \(d\).

Checkpoint

  • Can state Fermat (both forms) and Euler with hypotheses
  • Can compute \(\varphi(n)\) for prime powers and products
  • Can reduce large exponents correctly
  • Can obtain inverses as \(a^{\varphi(n)-1}\) when coprime
  • Can define order and prove it divides \(\varphi(n)\)
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — Fermat via binomial (optional alternate)

Alternate proof idea of \(a^p\equiv a\pmod p\) for prime \(p\).
For \(0<k<p\), \(p\mid\binom{p}{k}\). By induction on \(a\ge 0\): base \(0,1\) clear; if true for \(a\), then \[ (a+1)^p=\sum_{k=0}^p\binom{p}{k}a^k\equiv a^p+1\equiv a+1\pmod p \] using the induction hypothesis and \(p\mid\binom{p}{k}\) for middle terms. Extend to negative \(a\) by sign. This proves the “always” form \(a^p\equiv a\pmod p\); the unit form \(a^{p-1}\equiv 1\) follows when \(p\nmid a\) by cancelling one \(a\) (valid in the field \(\mathbb{Z}/p\mathbb{Z}\)).

Deeper theory — order lemma fully

Lemma. Let \(\gcd(a,n)=1\), \(k=\mathrm{ord}_n(a)\). Then \(a^j\equiv a^i\pmod n\) iff \(k\mid(j-i)\).

Proof. \(a^j\equiv a^i\) iff \(a^{j-i}\equiv 1\) (multiply by inverse of \(a^i\)). And \(a^m\equiv 1\) iff \(k\mid m\) (standard division argument from Day 75 main text).

Corollary. The powers \(a^0,a^1,\ldots,a^{k-1}\) are pairwise incongruent mod \(n\) — a cyclic subgroup of size \(k\) inside \((\mathbb{Z}/n\mathbb{Z})^\times\).

Worked example — large exponent reductions

Example 16 — \(2^{100}\bmod 13\).
\(2^{12}\equiv 1\pmod{13}\) by Fermat. \(100=8\cdot 12+4\), so \(2^{100}\equiv 2^4=16\equiv 3\pmod{13}\).
Successive square check: \(2^2=4\), \(2^4=3\), \(2^8=9\), \(2^{16}\equiv 3\), … or use binary: \(100=64+32+4\), multiply \(2^{64}2^{32}2^4\) reduced mod \(13\).

Example 17 — \(\varphi(720)\).
\(720=2^4\cdot 3^2\cdot 5\). \(\varphi(720)=720(1-1/2)(1-1/3)(1-1/5)=720\cdot\frac12\cdot\frac23\cdot\frac45=192\).

Example 18 — Order of \(2\) mod \(11\).
Divisors of \(\varphi(11)=10\): check \(2^1=2\), \(2^2=4\), \(2^5=32\equiv -1\neq 1\), \(2^{10}\equiv 1\). Order is \(10\) (primitive root mod \(11\)).

Example 19 — Reduce \(5^{100}\bmod 12\).
\(\gcd(5,12)=1\), \(\varphi(12)=4\), \(100\equiv 0\pmod 4\), so \(5^{100}\equiv (5^4)^{25}\equiv 1^{25}=1\pmod{12}\). Check: \(5^2=25\equiv 1\pmod{12}\) actually, so order divides \(2\); \(5^{100}=(5^2)^{50}\equiv 1\).

Extra exercises — exponent mastery

  1. Compute \(2^{50}\bmod 17\) by Fermat.
  2. Compute \(\varphi(84)\) via FTA.
  3. Find \(\mathrm{ord}_9(2)\) if defined; if not, explain.
  4. Prove: if \(\mathrm{ord}_n(a)=k\) and \(\ell\mid k\) then \(\mathrm{ord}_n(a^{k/\ell})=\ell\).
  5. Last two digits of \(3^{100}\): compute \(3^{100}\bmod 100\) using \(\varphi(100)=40\) (note \(100=2\cdot 40+20\), so need \(3^{20}\bmod 100\)).
  6. Show \(a^{n-1}\equiv 1\pmod n\) for all \(a\) coprime to \(n\) does not characterize primes (Carmichael culture: \(n=561\) awareness only).
  7. RSA literacy: if \(ed=1+t\varphi(n)\), show \(m^{ed}\equiv m\pmod n\) when \(\gcd(m,n)=1\).
  8. Compute \(7^{100}\bmod 13\) and \(7^{100}\bmod 11\), state the system for CRT recombination (Day 78).

Mini-solutions (selected)

  1. \(2^{16}\equiv 1\pmod{17}\), \(50=3\cdot 16+2\) ⇒ \(2^{50}\equiv 2^2=4\).
  2. \(84=2^2\cdot 3\cdot 7\), \(\varphi=84\cdot\frac12\cdot\frac23\cdot\frac67=24\).
  3. \(\gcd(2,9)=1\); \(2^1=2\), \(2^2=4\), \(2^3=8\equiv -1\), \(2^6\equiv 1\pmod 9\); order \(6\), and \(6\mid\varphi(9)=6\).

Closing synthesis card

Skill Check
Fermat both forms □
\(\varphi\) formulas □
Euler reduction of exponents □
Order divides \(\varphi(n)\) □
Avoid Euler when not coprime □

Tomorrow

Day 76 — Hashing mathematics and collisions.

Day 76 — Hashing mathematics and collisions

Stage VII · concept day
Goal: Model hash maps into \(m\) buckets; use uniformity assumptions; analyze collisions and the birthday bound \(\approx\sqrt{\pi m/2}\); relate load factor to chaining vs open addressing as math; state a simple universal hash idea.

Why this matters

Hashing is where modular arithmetic meets counting and probability. Engineers say “mod table size”; mathematicians say “map into \(\mathbb{Z}/m\mathbb{Z}\).” Collision bounds (birthday paradox lite) explain why cryptographic hash outputs need many bits and why load factors matter — as quantitative literacy, not as a coding lab.

Note

No labs / no hash-table projects. Definitions, counting arguments, worked probability, written exercises only.

Theory

Hash functions as maps

Definition (hash function, mathematical). A hash function from a universe \(U\) of keys to \(m\) buckets is a function \[ h:U\to \{0,1,\ldots,m-1\}. \] Often \(U\) is huge and \(m\) is modest (table size).

Modular hash (simple model). For integer keys and table size \(m\), \[ h(k)=k\bmod m. \] Then \(h(k)=h(k+tm)\) for every integer \(t\) — structured collisions along arithmetic progressions. Good when keys are “random-ish”; bad when keys share a common difference multiple of a factor of \(m\).

Division method literacy. Same as modular hash. Multiplication method (idea): use fractional parts of \(kA\) for irrational-ish \(A\); still lands in \(m\) buckets. We will not drill floating-point.

Collisions

Definition. A collision for \(h\) is a pair of distinct keys \(k_1\neq k_2\) with \(h(k_1)=h(k_2)\).

Pigeonhole (absolute). If \(|U|>m\), every function \(h:U\to\{0,\ldots,m-1\}\) has a collision. Perfect hashing of a static set \(S\) requires \(|S|\le m\) at minimum for injectivity into \(m\) buckets.

Load factor

If \(n\) keys are placed into \(m\) buckets, the load factor is \[ \alpha = \frac{n}{m}. \] Under idealized simple uniform hashing — each key independently uniformly random in \(\{0,\ldots,m-1\}\) — the expected number of keys in a fixed bucket is \(\alpha\).

Collision probability for one pair

Under uniform independent hashing into \(m\) buckets, for a fixed pair of distinct keys, \[ P(h(k_1)=h(k_2)) = \frac{1}{m}. \] Among \(n\) keys there are \(\binom{n}{2}\) pairs. Linearity of expectation (Day 87) gives expected number of colliding pairs \[ \mathbb{E}[X]=\binom{n}{2}\frac{1}{m}=\frac{n(n-1)}{2m}. \] This is not the probability that at least one collision occurs, but it is the right first estimate: when \(\mathbb{E}[X]\) is order \(1\), collisions become likely.

Birthday bound

Problem. Throw \(n\) balls independently uniformly into \(m\) bins. What \(n\) makes a collision probable?

Exact probability of no collision: \[ P(\text{all distinct})=\frac{m(m-1)\cdots(m-n+1)}{m^n}=\prod_{i=1}^{n-1}\Bigl(1-\frac{i}{m}\Bigr) \] for \(n\le m\).

Approximation. Using \(1-x\le e^{-x}\), \[ P(\text{no collision})\le \exp\Bigl(-\frac{n(n-1)}{2m}\Bigr). \] Thus when \(n\approx \sqrt{2m\ln 2}\), the collision probability is about \(1/2\). The classic birthday constant: for \(m=365\), \(n\approx 23\) already yields \(>50\%\) chance two share a birthday.

Asymptotic rule of thumb. Collisions become likely around \[ n \approx \sqrt{\frac{\pi m}{2}} \] for the expected waiting time form of the birthday problem (mean number of samples until first collision is asymptotic to that). For order-of-magnitude literacy: \[ n = \Theta(\sqrt{m}) \] suffices to force collisions with constant probability. Cryptographic moral: a hash with \(b\)-bit output (\(m=2^b\)) needs \(n\sim 2^{b/2}\) work for birthday collision attacks — not \(2^b\).

Chaining vs open addressing (mathematical load)

Chaining (separate chaining). Each bucket holds a list. Under simple uniform hashing, successful search cost is related to \(1+\alpha/2\) expected comparisons in standard analyses (order \(\Theta(1+\alpha)\)). Unsuccessful search \(\Theta(1+\alpha)\). Takeaway: performance degrades smoothly with \(\alpha\); \(\alpha>1\) is allowed.

Open addressing. All keys live in the table array; probe sequences find empty slots. Load factor must satisfy \(\alpha<1\). Expected probes for unsuccessful search under uniform probing idealization behave like \(1/(1-\alpha)\) — blows up as \(\alpha\to 1^-\). Takeaway: keep \(\alpha\) bounded away from \(1\) (e.g. \(0.5\)–\(0.7\) in practice — culture, not a theorem you must re-derive).

Simple universal hashing

Idea. Adversarial keys can defeat a fixed \(h\) (e.g. all keys \(\equiv r\pmod m\)). A family \(\mathcal{H}\) of hash functions is universal if for all distinct \(k_1,k_2\in U\), \[ P_{h\sim\mathcal{H}}(h(k_1)=h(k_2))\le \frac{1}{m}, \] when \(h\) is drawn uniformly from \(\mathcal{H}\).

Classic modular family (Carter–Wegman style, statement). For prime \(p\ge |U|\) and table size \(m\), functions \[ h_{a,b}(x)=((ax+b)\bmod p)\bmod m,\qquad a\in\{1,\ldots,p-1\},\; b\in\{0,\ldots,p-1\} \] form a universal (in fact strongly universal / pairwise independent) family for appropriate statements in textbooks.

Moral. Randomness in the choice of \(h\) restores the \(1/m\) collision probability even for worst-case key pairs — analysis assumes random \(h\), not random keys.

Connection to earlier days

Tool Role in hashing
\(k\bmod m\) Bucket index
Pigeonhole Inevitable collisions if \(n>m\)
\(\binom{n}{2}/m\) Expected colliding pairs
Birthday \(\sqrt{m}\) Collision threshold
Universal family Adversarial-key insurance

Worked examples

Example 1 — Modular clustering.
\(m=10\), keys \(20,30,40,50\): all hash to \(0\). Arithmetic progression with difference \(10\).

Example 2 — Expected colliding pairs.
\(n=50\) keys, \(m=1000\) buckets: \(\mathbb{E}[X]=\frac{50\cdot 49}{2\cdot 1000}=1.225\). About one colliding pair expected — collisions not rare.

Example 3 — Birthday half-probability.
Solve \(n(n-1)/(2m)\approx \ln 2\) ≈ \(0.693\). For \(m=365\): \(n(n-1)\approx 506\), \(n\approx 23\).

Example 4 — Crypto bit length.
For \(m=2^{128}\), birthday at \(\sim 2^{64}\) hashes. “128-bit security against collision” needs roughly \(256\)-bit output in naive birthday terms for collision resistance goals — literacy only.

Example 5 — Load factor chaining.
\(n=300\), \(m=100\), \(\alpha=3\). Expected chain length \(3\). Search is \(O(1+\alpha)\) under ideal assumptions — here order \(4\), not order \(n\).

Example 6 — Open address blow-up.
Ideal unsuccessful probes \(\approx 1/(1-\alpha)\): \(\alpha=0.5\) → \(2\); \(\alpha=0.9\) → \(10\); \(\alpha=0.99\) → \(100\).

Example 7 — Pigeonhole.
\(|U|=10^6\), \(m=10^3\): every \(h\) has collisions. Minimum max-bucket load \(\ge\lceil n/m\rceil\) when placing \(n\) keys (always).

Example 8 — Probability all distinct.
\(m=5\), \(n=3\): \(P=\frac{5\cdot 4\cdot 3}{5^3}=\frac{60}{125}=0.48\). Collision probability \(0.52\).

Example 9 — Universal idea.
Fixed \(h(k)=k\bmod 8\) fails on even keys all mapping into even buckets if structure aligns. Drawing \(h_{a,b}\) randomly makes any fixed pair collide with probability \(\le 1/m\).

Example 10 — Expected empty buckets.
Under uniform independent placement of \(n\) keys in \(m\) buckets, \(P(\text{bucket }i\text{ empty})=(1-1/m)^n\approx e^{-\alpha}\). Expected empty count \(m e^{-\alpha}\) approximately.

Exercises

A. Models and pigeonhole

  1. Define collision and load factor formally.
  2. Why does \(h(k)=k\bmod m\) send \(k\) and \(k+m\) to the same bucket?
  3. Prove: if \(n>m\), some bucket has at least two of \(n\) keys (any \(h\)).
  4. If \(n\) keys go into \(m\) buckets, prove some bucket has at least \(\lceil n/m\rceil\) keys.
  5. Give keys that all collide under \(h(k)=k\bmod 16\) but not under \(h(k)=k\bmod 15\).

B. Pair collisions and expectation

  1. For \(n=100\), \(m=10^4\), compute \(\mathbb{E}[X]\) for number of colliding pairs under uniform independent hashing.
  2. For what \(n\) (approx) is \(\mathbb{E}[X]=1\) when \(m=10^6\)?
  3. Explain the difference between \(\mathbb{E}[X]\ge 1\) and \(P(X\ge 1)\ge 1/2\).
  4. Compute exact \(P(\text{collision})\) for \(n=3\), \(m=10\).
  5. Using \(1-x\le e^{-x}\), show \(P(\text{no collision})\le e^{-n(n-1)/(2m)}\).

C. Birthday bound

  1. Estimate \(n\) for \(50\%\) collision chance with \(m=365\) (show calculation).
  2. Estimate \(n\) for \(m=2^{32}\) (32-bit hash) at constant collision probability.
  3. Explain in prose why collision resistance needs roughly twice the bits of preimage folklore targets (birthday).
  4. Birthdays: if years had \(m=1000\) days, about how many people for \(\sim 50\%\) shared day?

D. Load factor and table math

  1. Chaining: \(m=1000\), \(n=3000\). What is \(\alpha\)? Expected keys per bucket?
  2. Open addressing: why is \(\alpha=1.2\) impossible for a full table of size \(m\)?
  3. Compare expected unsuccessful probes \(1/(1-\alpha)\) at \(\alpha=0.5\) vs \(0.8\).
  4. If rehashing doubles \(m\) when \(\alpha>\frac{3}{4}\), describe the load just before and after a rehash starting from \(m=16\), keys inserted one-by-one until first rehash (count).
  5. Expected empty buckets approx \(m e^{-n/m}\) for \(n=m\): numerical value of fraction empty.

E. Universal hashing and literacy

  1. State the definition of a universal hash family.
  2. Why does a fixed public \(h\) fail against adversarial keys?
  3. CS literacy: separate chaining vs open addressing — two mathematical bullets each (no code).
  4. If cryptographic hash output is \(b\) bits, birthday collision work is order \(2^{b/2}\). Compute for \(b=160\) and \(b=256\).
  5. Stretch: prove that for any fixed distinct \(k_1,k_2\), a uniformly random function \(h:U\to[m]\) satisfies \(P(h(k_1)=h(k_2))=1/m\).
  6. Stretch: show \(\sum_{i=0}^{n-1} i = n(n-1)/2\) appears naturally in the exponent of the birthday product approximation.

Deep dive — birthday approximation derivation

Start from \[ \ln P(\text{no collision})=\sum_{i=1}^{n-1}\ln\Bigl(1-\frac{i}{m}\Bigr). \] For small \(x\), \(\ln(1-x)\approx -x-x^2/2-\cdots\). Leading term: \[ \sum_{i=1}^{n-1}\frac{i}{m}\approx \frac{n^2}{2m}. \] Hence \(P(\text{no collision})\approx e^{-n^2/(2m)}\). Set equal to \(1/2\): \(n^2/(2m)\approx\ln 2\), so \(n\approx\sqrt{2m\ln 2}\approx 1.177\sqrt{m}\).
The mean waiting time until first collision is asymptotic to \(\sqrt{\pi m/2}\approx 1.25\sqrt{m}\). Both are \(\Theta(\sqrt{m})\).

Deep dive — chaining cost model (math only)

Under simple uniform hashing, bucket load \(X\sim\mathrm{Bin}(n,1/m)\) approximately, \(\mathbb{E}[X]=\alpha\).
Successful search cost is often modeled as \(1+\Theta(\alpha)\) comparisons depending on list implementation details — the shape is linear in \(\alpha\), not in \(n\) alone. That is why tables grow with \(n\) (rehash to keep \(\alpha\) bounded).

Open addressing: probe sequences; clustering analysis is deeper; the \(1/(1-\alpha)\) formula is the ideal uniform probing heuristic from textbooks.

Additional worked examples

Example 11 — Expected colliding pairs table.

\(n\) \(m\) \(\mathbb{E}[X]=\binom{n}{2}/m\)
10 100 0.45
50 100 12.25
100 365 ≈ 13.6
23 365 ≈ 0.69

Example 12 — Max load lower bound.
Always some bucket \(\ge\lceil n/m\rceil\). For \(n=m\), some bucket \(\ge 1\) (trivial); with high probability max load is \(\Theta(\log n/\log\log n)\) for balls-and-bins — awareness, not required proof.

Example 13 — Structured keys.
Keys \(0,256,512,768\) with \(m=256\): all map to \(0\) under \(k\bmod 256\). Universal family randomizes the multiplier to break this.

Example 14 — Crypto hash length.
Output \(64\) bits: birthday at \(\sim 2^{32}\) — often too low for collision resistance goals. Output \(256\) bits: birthday \(\sim 2^{128}\).

Example 15 — Load after rehash.
\(m=16\), insert until \(\alpha>0.75\) ⇒ at \(n=13\) rehash to \(m=32\), new \(\alpha=13/32\approx 0.41\).

More exercises

  1. Derive \(n\approx\sqrt{2m\ln 2}\) from \(e^{-n^2/(2m)}=1/2\).
  2. For \(m=2^{20}\), estimate \(n\) for \(50\%\) collision probability.
  3. Compare \(\mathbb{E}[X]\) and union bound \(P(\text{collision})\le\mathbb{E}[X]\).
  4. If each of \(n\) keys independently hashes uniform, expected number of nonempty buckets is \(m(1-(1-1/m)^n)\). Expand for small \(\alpha\).
  5. CS: why power-of-two table sizes interact badly with low-bit structure of some keys.
  6. Prove that a random function collides a fixed pair with prob \(1/m\).
  7. Open addressing: plot (by hand, few points) \(1/(1-\alpha)\) for \(\alpha=0.1,0.5,0.8,0.9\).

Selected mini-solutions

  1. \(\binom{100}{2}/10^4=4950/10000=0.495\).
  2. \(n(n-1)/(2m)\approx 1\) ⇒ \(n\approx\sqrt{2m}\).
  3. \(n(n-1)\approx 2\cdot 365\cdot 0.693\approx 506\) ⇒ \(n\approx 23\).
  4. \(\alpha=3\), expected chain length \(3\).

Common pitfalls

Pitfall Fix
Thinking good hash ⇒ no collisions Pigeonhole forbids when \(n>m\)
Using \(n=m\) as “safe” Birthday collisions much earlier at \(\sqrt{m}\)
Confusing expected pair-collisions with \(P(\ge 1\) collision\()\) Related but not equal
Open addressing with \(\alpha>1\) Impossible for distinct keys in array of size \(m\)
Assuming keys are random when adversary chooses them Need universal / keyed hashing story
Confusing \(2^{b}\) preimage work with \(2^{b/2}\) collision work Birthday

Study notes — hashing quantities

Quantity Formula / scale
Load \(\alpha\) \(n/m\)
Pair collision prob \(1/m\) (uniform model)
\(\mathbb{E}[\#\) colliding pairs\(]\) \(\binom{n}{2}/m\)
Birthday threshold \(\Theta(\sqrt{m})\), \(\sim\sqrt{\pi m/2}\) mean wait
Chaining search \(\Theta(1+\alpha)\) shape
Open address fail probes \(\sim 1/(1-\alpha)\) ideal
Universal \(P(h(k_1)=h(k_2))\le 1/m\)

Synthesis — hashing maths workout

S1. Prove pigeonhole: \(n>m\) keys ⇒ some bucket has \(\ge 2\) keys for any \(h\).

S2. Compute \(\mathbb{E}[\text{colliding pairs}]\) for \(n=40\), \(m=500\).

S3. Estimate \(n\) for \(50\%\) collision chance when \(m=10^6\) using \(\sqrt{2m\ln 2}\).

S4. Chaining: \(\alpha=2.5\) — what does expected bucket load mean operationally?

S5. Open addressing: evaluate \(1/(1-\alpha)\) at \(\alpha=0.5,0.75,0.9\).

S6. State universal hashing definition; give one sentence why fixed \(k\bmod m\) fails adversaries.

S7. Crypto: birthday work for \(b=128\) and \(b=256\) bit outputs.

S8. Expected empty buckets approx \(m e^{-n/m}\) at \(n=m\): numerical fraction empty.

Checkpoint

  • Can define hash, collision, load factor
  • Can compute \(\mathbb{E}[\text{colliding pairs}]\)
  • Can state birthday bound \(\sim\sqrt{m}\) and \(\sqrt{\pi m/2}\) literacy
  • Can compare chaining vs open addressing via \(\alpha\)
  • Can state universal hashing idea
  • Exercises A–D done; synthesis attempted

Two personal takeaways:

  1. …
  2. …

Deeper theory — expected colliding pairs vs collision probability

Let \(X=\sum_{1\le i<j\le n} I_{ij}\) where \(I_{ij}=1\) if keys \(i,j\) collide under uniform independent hashing into \(m\) buckets. Then \(\mathbb{E}[I_{ij}]=1/m\) and by linearity \[ \mathbb{E}[X]=\binom{n}{2}\frac{1}{m}. \] Markov: \(P(X\ge 1)\le\mathbb{E}[X]\). So when \(\mathbb{E}[X]\) is small, collision probability is small. When \(\mathbb{E}[X]\gg 1\), Markov does not force \(P(X\ge 1)\) near \(1\) by itself, but the birthday product approximation does: \(P(\text{no collision})\approx e^{-n(n-1)/(2m)}\).

Moral. Use \(\mathbb{E}[X]\) as a first calculator; use the exponential approximation for the \(50\%\) threshold; use pigeonhole for the absolute \(n>m\) guarantee.

Deeper theory — why universal hashing beats fixed modular hash

Adversarial pattern. If \(h(k)=k\bmod m\) is public and fixed, an adversary feeds keys \(k,k+m,k+2m,\ldots\) — all collide in one bucket. Load becomes \(\Theta(n)\) in that bucket.

Universal family. Drawing \(h\) at random from a universal family ensures that for every fixed pair, \(P(h(k_1)=h(k_2))\le 1/m\), even if the adversary chose the pair knowing the family (but not the random draw). Expected colliding pairs remains \(\le\binom{n}{2}/m\).

Pairwise independence literacy. Strongly universal families make \((h(k_1),h(k_2))\) uniform on \([m]^2\) for \(k_1\neq k_2\) — stronger than universal; the modular \(((ax+b)\bmod p)\bmod m\) family is the standard textbook construction.

Worked examples — numbers you can trust

Example 16 — Birthday for \(m=2^{16}\).
\(n\approx\sqrt{2\cdot 2^{16}\ln 2}\approx\sqrt{2^{17}\cdot 0.693}\approx\sqrt{90800}\approx 301\). About \(300\) random \(16\)-bit hashes already collide with probability \(\sim 1/2\).

Example 17 — Expected pairs table extension.
\(n=100\), \(m=500\): \(\mathbb{E}[X]=4950/500=9.9\) — expect about ten colliding pairs; many collisions almost sure.

Example 18 — Empty buckets at \(\alpha=1\).
\(m e^{-1}\approx 0.37m\) empty expected under independent uniform model — about \(37\%\) empty, so some buckets have more than one key even when \(n=m\).

Example 19 — Open addressing at \(\alpha=0.7\).
Ideal unsuccessful probes \(\approx 1/(1-0.7)\approx 3.33\). At \(\alpha=0.95\): \(\approx 20\). Rehash before the blow-up.

Extra exercises — hashing maths

  1. Derive \(P(\text{no collision})=\prod_{i=1}^{n-1}(1-i/m)\) carefully (ordered insertion).
  2. For \(m=10^9\), estimate \(n\) with \(\mathbb{E}[X]=1\).
  3. Prove: under uniform independent hashing, expected max load is at least \(\lceil n/m\rceil\) (trivial lower bound) — and state the \(\Theta(\log n/\log\log n)\) high-probability culture bound for \(n=m\).
  4. Universal: why does \(h_{a,b}\) need \(a\not\equiv 0\pmod p\)?
  5. Crypto: birthday work for \(b=80\) bit tags (short MACs) — order of magnitude.
  6. Chaining: if \(\alpha=4\), expected successful search shape \(\Theta(1+\alpha)\) — numerical order.
  7. Show union bound \(P(\text{collision})\le\binom{n}{2}/m\) and compare to \(1-e^{-n(n-1)/(2m)}\).
  8. CS prose: power-of-two \(m\) with keys sharing low bits — what goes wrong with \(k\bmod m\)?

Mini-solutions (selected)

  1. \(n(n-1)/(2\cdot 10^9)\approx 1\) ⇒ \(n\approx\sqrt{2\cdot 10^9}\approx 44721\).
  2. \(2^{40}\) order birthday work.
  3. Union bound is linear in \(\binom{n}{2}/m\); exponential approx is tighter near the transition.

Closing synthesis card

Quantity Own it?
\(\alpha=n/m\) □
\(\mathbb{E}[\text{pairs}]=\binom{n}{2}/m\) □
Birthday \(\Theta(\sqrt{m})\) □
Chaining vs open address via \(\alpha\) □
Universal definition □

Tomorrow

Day 77 — Diffie–Hellman and RSA mathematical stories.