Fermat, Euler and Wilson

Study Sheet

Fermat, Euler and Wilson

The three theorems behind every big power

Fermat's Little Theorem

Concept
ap−1≡1a^{p-1} \equiv 1
112233445566x3x3, 6, 2, 5, 1, 4: the same six residues, reshuffled
Multiplying 1, …, 6 by 3 mod 7 permutes them — the heart of the proof.

If pp is prime and p∤ap \nmid a, then ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p; equivalently ap≡aa^p \equiv a for every aa. So exponents can be reduced mod p−1p - 1: an≡an mod (p−1)(modp)a^n \equiv a^{n \bmod (p-1)} \pmod p when p∤ap \nmid a.

The exponent p−1p - 1 is the number of nonzero residues mod pp, and the theorem says multiplying by aa permutes them: a,2a,…,(p−1)aa, 2a, \ldots, (p-1)a are the same residues in a different order, so their products agree, ap−1(p−1)!≡(p−1)!a^{p-1}(p-1)! \equiv (p-1)!, and (p−1)!(p-1)! cancels. This is a group-theory fact in disguise (Lagrange's theorem), and Euler's theorem is the same argument with the coprime residues mod mm.

Example
Reduce the exponent

Find 31000 mod 73^{1000} \bmod 7. Since 7∤37 \nmid 3, Fermat gives 36≡13^6 \equiv 1, so whole blocks of 66 in the exponent contribute nothing: 1000=6⋅166+41000 = 6\cdot166 + 4 and 31000=(36)166⋅34≡34=81=11⋅7+43^{1000} = (3^6)^{166}\cdot3^4 \equiv 3^4 = 81 = 11\cdot7 + 4. Answer 44.

Example
42∣n7−n42 \mid n^7 - n

Show that n7−nn^7 - n is divisible by 42=2⋅3⋅742 = 2\cdot3\cdot7 for every integer nn. The three primes are coprime, so treat them one at a time. Mod 77: Fermat in the form n7≡nn^7 \equiv n holds for every nn. Mod 33: n3≡nn^3 \equiv n, so n7=n3⋅n3⋅n≡n⋅n⋅n=n3≡nn^7 = n^3\cdot n^3\cdot n \equiv n\cdot n\cdot n = n^3 \equiv n. Mod 22: n2≡nn^2 \equiv n, so every power of nn is ≡n\equiv n. Hence 22, 33 and 77 all divide n7−nn^7 - n.

Example
A test that finds composites

Is 1515 prime? If it were, Fermat would force 214≡1(mod15)2^{14} \equiv 1 \pmod{15}. Compute: 24=16≡12^4 = 16 \equiv 1, so 214=(24)3⋅22≡42^{14} = (2^4)^3\cdot2^2 \equiv 4. Since 4≠14 \ne 1, 1515 is composite — proved without finding a factor. For large numbers this "Fermat test" is how computers screen for primes, since fast exponentiation is cheap and factoring is not.

Side note
Where it goes wrong

Reducing the exponent mod pp instead of mod p−1p - 1. For 3100 mod 73^{100} \bmod 7, "100≡2(mod7)100 \equiv 2 \pmod 7, so 32=9≡23^2 = 9 \equiv 2" is wrong; the cycle has length 66, 100≡4(mod6)100 \equiv 4 \pmod 6, and 3100≡34≡43^{100} \equiv 3^4 \equiv 4. And the theorem needs p∤ap \nmid a: 76≡0(mod7)7^6 \equiv 0 \pmod 7, not 11.

Try it
Try it: Fermat

Find 22025 mod 132^{2025} \bmod 13.

Show the answer

By Fermat 212≡1(mod13)2^{12} \equiv 1 \pmod{13}. Since 2025=12⋅168+92025 = 12\cdot168 + 9, 22025≡29=512=39⋅13+5≡52^{2025} \equiv 2^9 = 512 = 39\cdot13 + 5 \equiv \mathbf{5}.

Euler's Theorem and φ\varphi

Concept
Euler's totient

φ(m)\varphi(m) counts the integers in 1,…,m1, \ldots, m coprime to mm. For m=p1e1⋯pkekm = p_1^{e_1}\cdots p_k^{e_k}: φ(m)=m∏(1−1pi)\varphi(m) = m\prod\left(1 - \dfrac{1}{p_i}\right). Euler: if gcd⁡(a,m)=1\gcd(a, m) = 1 then aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod m.

The product formula is a sieve: of the numbers 1,…,m1, \ldots, m, a fraction 1/p11/p_1 are multiples of p1p_1, and removing them leaves the fraction 1−1/p11 - 1/p_1; among what remains, the multiples of p2p_2 are again a fraction 1/p21/p_2, because p1p_1 and p2p_2 are independent (a fact made precise by the Chinese remainder theorem). Euler's theorem generalizes Fermat — for prime m=pm = p, φ(p)=p−1\varphi(p) = p - 1 — and lets you reduce exponents mod φ(m)\varphi(m) for any modulus, as long as the base is coprime to it.

Example
φ(36)\varphi(36)
12345678910111213141516171819202122232425262728293031323334353612 of the 36 are coprime to 36
Rows of 6: only the columns 1 and 5 (mod 6) avoid both 2 and 3.

36=22⋅3236 = 2^2\cdot3^2, so φ(36)=36⋅12⋅23=12\varphi(36) = 36\cdot\tfrac12\cdot\tfrac23 = 12. Laid out in rows of 66, the coprime numbers are exactly those ≡1\equiv 1 or 5(mod6)5 \pmod 6: half the columns are even, and of the odd columns one is a multiple of 33. Two columns of six rows: 1212.

Example
Last two digits

Find 7222 mod 1007^{222} \bmod 100. gcd⁡(7,100)=1\gcd(7, 100) = 1 and φ(100)=100⋅12⋅45=40\varphi(100) = 100\cdot\tfrac12\cdot\tfrac45 = 40, so 7222=(740)5⋅722≡7227^{222} = (7^{40})^5\cdot7^{22} \equiv 7^{22}. Here the order is even shorter: 72=497^2 = 49, 74=2401≡1(mod100)7^4 = 2401 \equiv 1 \pmod{100}. So 722=(74)5⋅72≡497^{22} = (7^4)^5\cdot7^2 \equiv 49. The last two digits are 4949.

Example
A tower

Find the last digit of 7777^{7^7}. Mod 1010, φ(10)=4\varphi(10) = 4, so the exponent 777^7 matters only mod 44. And 7≡−1(mod4)7 \equiv -1 \pmod 4, so 77≡(−1)7≡3(mod4)7^7 \equiv (-1)^7 \equiv 3 \pmod 4. Hence 777≡73=343(mod10)7^{7^7} \equiv 7^3 = 343 \pmod{10}: the last digit is 33. Towers are handled from the top down, each level mod the totient of the level below.

Side note
Where it goes wrong

Using Euler when gcd⁡(a,m)≠1\gcd(a, m) \ne 1 — 2φ(8)=24=16≡0(mod8)2^{\varphi(8)} = 2^4 = 16 \equiv 0 \pmod 8, not 11. Split the modulus into prime powers and treat the non-coprime part directly (the CRT topic shows how).

Try it
Try it: totient

Compute φ(360)\varphi(360), then find 796 mod 3607^{96} \bmod 360.

Show the answer

360=23⋅32⋅5360 = 2^3\cdot3^2\cdot5: φ=360⋅12⋅23⋅45=96\varphi = 360\cdot\tfrac12\cdot\tfrac23\cdot\tfrac45 = \mathbf{96}. Since gcd⁡(7,360)=1\gcd(7, 360) = 1, Euler gives 796≡1(mod360)7^{96} \equiv \mathbf{1} \pmod{360}.

Wilson's Theorem

Concept
(p−1)!≡−1(p - 1)! \equiv -1

Wilson: for a prime pp, (p−1)!≡−1(modp)(p - 1)! \equiv -1 \pmod p. For composite m>4m > 4, (m−1)!≡0(modm)(m - 1)! \equiv 0 \pmod m (and 3!=6≡2(mod4)3! = 6 \equiv 2 \pmod 4). So Wilson's congruence holds exactly for the primes.

Each of 1,2,…,p−11, 2, \ldots, p - 1 has an inverse mod pp, and the numbers pair off with their inverses, each pair multiplying to 11. The only numbers equal to their own inverse solve x2≡1x^2 \equiv 1, i.e. p∣(x−1)(x+1)p \mid (x - 1)(x + 1), so x≡±1x \equiv \pm1. The product of everything is therefore 1⋅(−1)⋅1⋯1=−11\cdot(-1)\cdot1\cdots1 = -1. For composite mm, some factor of mm appears among 1,…,m−11, \ldots, m - 1 and the product shares that factor with mm.

Example
10! mod 1110! \bmod 11
12345678910pairs multiply to 1; only 1 and 10 are their own inverses
Each chord joins a residue to its inverse mod 11; the product of all ten is 1 · 10 ≡ −1.

Pair each of 2,…,92, \ldots, 9 with its inverse mod 1111: 2⋅6=122\cdot6 = 12, 3⋅4=123\cdot4 = 12, 5⋅9=455\cdot9 = 45, 7⋅8=567\cdot8 = 56, and each of these is ≡1(mod11)\equiv 1 \pmod{11}. What is left is 1⋅10≡−11\cdot10 \equiv -1. So 10!≡−1≡10(mod11)10! \equiv -1 \equiv 10 \pmod{11}, as a direct check confirms: 10!=3628800=11⋅329890+1010! = 3628800 = 11\cdot329890 + 10.

Example
15! mod 1715! \bmod 17

Wilson gives 16!≡−1(mod17)16! \equiv -1 \pmod{17}. And 16!=16⋅15!16! = 16\cdot15! with 16≡−116 \equiv -1, so −15!≡−1-15! \equiv -1 and 15!≡1(mod17)15! \equiv 1 \pmod{17}. Peeling factors off the top of (p−1)!(p-1)! like this turns Wilson into a tool for nearby factorials.

Example
97! mod 10197! \bmod 101

101101 is prime, so 100!≡−1100! \equiv -1. Peel off three factors: 100⋅99⋅98≡(−1)(−2)(−3)=−6100\cdot99\cdot98 \equiv (-1)(-2)(-3) = -6, so 97!⋅(−6)≡−197!\cdot(-6) \equiv -1, i.e. 6⋅97!≡16\cdot97! \equiv 1. Thus 97!≡6−1(mod101)97! \equiv 6^{-1} \pmod{101}, and 6⋅17=102≡16\cdot17 = 102 \equiv 1 gives 6−1≡176^{-1} \equiv 17. So 97!≡17(mod101)97! \equiv 17 \pmod{101}.

Side note
Where it goes wrong

Using Wilson with a composite modulus. 5!=120≡0(mod6)5! = 120 \equiv 0 \pmod 6, not −1-1: the factors 22 and 33 of 66 both appear in 5!5!. The pairing argument breaks because 22 and 33 have no inverses mod 66.

Try it
Try it: Wilson

Find 17! mod 1917! \bmod 19.

Show the answer

Wilson: 18!≡−1(mod19)18! \equiv -1 \pmod{19}. Since 18≡−118 \equiv -1, 18!=18⋅17!≡−17!18! = 18\cdot17! \equiv -17!. So −17!≡−1-17! \equiv -1, and 17!≡1(mod19)17! \equiv \mathbf{1} \pmod{19}.

Why It Works

Let p∤ap \nmid a. The residues a,2a,…,(p−1)aa, 2a, \ldots, (p-1)a are pairwise distinct mod pp: if ia≡jaia \equiv ja then p∣(i−j)ap \mid (i - j)a, and since p∤ap \nmid a, p∣i−jp \mid i - j, forcing i=ji = j (both lie in 1,…,p−11, \ldots, p - 1). None is 00. So they are the residues 1,…,p−11, \ldots, p - 1 in some order, and multiplying them together gives ap−1(p−1)!≡(p−1)!(modp)a^{p-1}(p-1)! \equiv (p-1)! \pmod p. Since p∤(p−1)!p \nmid (p-1)! (all its factors are smaller than pp), cancel it: ap−1≡1a^{p-1} \equiv 1. Replace "1,…,p−11, \ldots, p - 1" by "the φ(m)\varphi(m) residues coprime to mm" and the identical argument proves Euler's theorem.

For p=2p = 2 and p=3p = 3 check directly: 1!=1≡−1(mod2)1! = 1 \equiv -1 \pmod 2 and 2!=2≡−1(mod3)2! = 2 \equiv -1 \pmod 3. For larger pp, every xx in 2,…,p−22, \ldots, p - 2 has a unique inverse in 1,…,p−11, \ldots, p - 1, and the inverse is neither 11 nor p−1p - 1 (those are their own inverses) nor xx itself (that would need x2≡1x^2 \equiv 1, so x≡±1x \equiv \pm1). So 2,…,p−22, \ldots, p - 2 split into pairs with product 11, and (p−1)!≡1⋅(p−1)≡−1(p-1)! \equiv 1\cdot(p - 1) \equiv -1. Conversely, if m>4m > 4 is composite with m=abm = ab, 1<a≤b<m1 < a \le b < m, then aa and bb (or aa and 2a2a when a=ba = b) appear separately in (m−1)!(m-1)!, so m∣(m−1)!m \mid (m-1)!.