Day 74 — Modular inverses & Wilson

Updated

July 30, 2026

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.