21.01.04 · number-theory / elementary

Fermat's little theorem, Euler's theorem, and Wilson's theorem

shipped3 tiersLean: none

Anchor (Master): Fermat 1640 letter to Frénicle de Bessy (originator, no proof); Euler 1736 *Comm. Acad. Sci. Petrop.* 8 (first proof of FLT) and 1763 *Novi Comm. Acad. Sci. Petrop.* 8 (totient version); Lagrange 1771 *Nouv. Mém. Acad. Berlin* 2 (first proof of Wilson); Gauss 1801 *Disquisitiones Arithmeticae* arts. 50-83 (canonical modern formulation); Hardy-Wright 2008 6e §VI; Carmichael 1910 *Bull. AMS* 16; Alford-Granville-Pomerance 1994 *Annals* 140; Agrawal-Kayal-Saxena 2004 *Annals* 160 (PRIMES is in P)

Intuition Beginner

A surprising regularity in modular arithmetic: whenever you raise a number to a carefully chosen power and then read the answer modulo a prime, you always land on $1$ . This is Fermat's little theorem, discovered by Pierre de Fermat in 1640. For a prime $p$ and any integer $a$ that is not a multiple of $p$ , raising $a$ to the power $p - 1$ and reading the answer modulo $p$ gives $1$ — every time, without exception.

The cleanest illustration uses $p = 7$ . Take $a = 3$ . Fermat predicts $3^{6} \equiv 1 (mod 7)$ . Compute: $3^{2} = 9 \equiv 2 (mod 7)$ ; $3^{4} = 81 \equiv 4 (mod 7)$ (since $81 = 11 \times 7 + 4$ ); $3^{6} = 3^{4} \times 3^{2} \equiv 4 \times 2 = 8 \equiv 1 (mod 7)$ . The theorem holds. Try $a = 5$ : $5^{2} = 25 \equiv 4 (mod 7)$ , $5^{4} \equiv 16 \equiv 2 (mod 7)$ , $5^{6} \equiv 2 \times 4 = 8 \equiv 1 (mod 7)$ . Still works. The pattern is universal for every nonzero residue.

Euler's theorem is the generalisation to composite moduli. For an arbitrary positive integer $n$ , write $φ (n)$ for the count of integers in ${1, 2, \dots, n}$ that share no common factor with $n$ . The function $φ$ is the Euler totient introduced in 21.01.03. Then for every integer $a$ coprime to $n$ , $a^{φ (n)} \equiv 1 (mod n)$ . The prime case $n = p$ recovers Fermat: $φ (p) = p - 1$ , so Euler's theorem specialises to $a^{p - 1} \equiv 1 (mod p)$ .

A second surprise, due to John Wilson 1770 and proved by Joseph-Louis Lagrange 1771: the product of all integers from $1$ to $p - 1$ — what is called $(p - 1)!$ — leaves remainder $- 1$ when divided by $p$ , whenever $p$ is prime. For $p = 5$ : $4! = 24 = 5 \times 5 - 1 \equiv - 1 (mod 5)$ . For $p = 7$ : $6! = 720 = 103 \times 7 - 1 \equiv - 1 (mod 7)$ . Wilson's theorem is even more striking because the converse also holds: if $(n - 1)! \equiv - 1 (mod n)$ , then $n$ must be prime. So Wilson gives an exact primality criterion — at least in principle.

The applied importance of these theorems is hard to overstate. Every secure web connection routes through Euler's theorem. The RSA cryptosystem, invented by Rivest-Shamir-Adleman in 1978, encrypts a message $M$ by computing $C = M^{e} mod N$ where $N = pq$ is the product of two large primes. The decryption $M = C^{d} mod N$ works because $e d \equiv 1 (mod φ (N))$ , so $M^{e d} \equiv M (mod N)$ by Euler — without the theorem, RSA would not exist. Primality testing — the Fermat test, Miller-Rabin, AKS — also begins with Fermat's little theorem as the entry point: if $a^{n - 1} \neq \equiv 1 (mod n)$ for some $a$ coprime to $n$ , then $n$ is composite.

Visual Beginner

A picture of a circular clock with $7$ positions, labelled $0$ through $6$ . Six arrows trace the orbit of $3$ under repeated multiplication modulo $7$ : $3^{1} = 3$ at position $3$ ; $3^{2} = 9 \equiv 2$ at position $2$ ; $3^{3} \equiv 6$ at position $6$ ; $3^{4} \equiv 4$ at position $4$ ; $3^{5} \equiv 5$ at position $5$ ; $3^{6} \equiv 1$ at position $1$ . The orbit visits every nonzero position exactly once and returns to $1$ after $6$ steps. The arrow from $3^{5}$ to $3^{6}$ closes the loop.

The picture captures the central fact. The nonzero residues modulo a prime form a cyclic structure under multiplication, and any element raised to the size of that structure returns to the identity $1$ . The visualised orbit of $3$ modulo $7$ has length exactly $6 = p - 1$ , but for some elements the orbit is shorter: $2$ modulo $7$ has orbit length $3$ (since $2^{3} = 8 \equiv 1$ ), and the orbit length always divides $p - 1$ . The theorem is the rigorous statement of this cyclic-return phenomenon.

Worked example Beginner

Compute $2^{10}$ modulo $11$ and verify Fermat's little theorem for $p = 11$ , $a = 2$ .

Step 1. Fermat predicts $2^{10} \equiv 1 (mod 11)$ , because $11$ is prime and $g cd (2, 11) = 1$ .

Step 2. Compute the powers of $2$ modulo $11$ by successive squaring: $2^{2} = 4$ ; $2^{4} = 16 = 11 + 5 \equiv 5 (mod 11)$ ; $2^{8} \equiv 5^{2} = 25 = 2 \times 11 + 3 \equiv 3 (mod 11)$ .

Step 3. Combine: $2^{10} = 2^{8} \times 2^{2} \equiv 3 \times 4 = 12 = 11 + 1 \equiv 1 (mod 11)$ .

Step 4. The prediction is confirmed: $2^{10} = 1024 = 93 \times 11 + 1$ , so $2^{10} \equiv 1 (mod 11)$ as Fermat said.

What this tells us: once we know Fermat's little theorem, we never need to compute $2^{10}$ directly to know its residue modulo $11$ — the answer is $1$ by the theorem alone. The same principle lets us compute $2^{1000}$ modulo $11$ at a glance: $1000 = 100 \times 10$ , so $2^{1000} = (2^{10})^{100} \equiv 1^{100} = 1 (mod 11)$ . Modular exponentiation collapses to almost nothing once the cyclic-return structure is known.

Check your understanding Beginner

Formal definition Intermediate+

The Fermat-Euler-Wilson theorems live inside the unit-group structure of $Z / n Z$ developed in 21.01.03. We restate the definitions in their canonical form and then prove the three signature theorems.

Definition (order of an element). Let $G$ be a finite group with identity $e$ and let $g \in G$ . The order of $g$ , written $ord (g)$ , is the least positive integer $k$ such that $g^{k} = e$ . Such a $k$ exists because $G$ is finite (the powers $g, g^{2}, g^{3}, \dots$ cannot all be distinct, so some $g^{i} = g^{j}$ with $i < j$ gives $g^{j - i} = e$ ). The order divides every $m$ with $g^{m} = e$ .

Definition (Euler totient $φ (n)$ ). For $n \in Z_{> 0}$ , $$ \varphi(n) ;=; # {, a \in {1, 2, \ldots, n} : \gcd(a, n) = 1 ,} ;=; #(\mathbb{Z}/n\mathbb{Z})^\times. $$ By 21.01.03 Theorem 2, $φ$ is multiplicative on coprime arguments ( $φ (mn) = φ (m) φ (n)$ for $g cd (m, n) = 1$ ), satisfies $φ (p^{k}) = p^{k - 1} (p - 1)$ on prime powers, and has the closed form $φ (n) = n \prod_{p ∣ n} (1 - 1/ p)$ .

Definition (Carmichael function $λ (n)$ ). The exponent of the group $(Z / n Z)^{\times}$ — the least positive integer $λ$ such that $a^{λ} \equiv 1 (mod n)$ for every $a$ coprime to $n$ — is denoted $λ (n)$ and called the Carmichael function. It always divides $φ (n)$ , with equality if and only if $(Z / n Z)^{\times}$ is cyclic, which happens precisely for $n \in {1, 2, 4, p^{k}, 2 p^{k}}$ with $p$ an odd prime [Carmichael 1910].

Counterexamples to common slips

"Fermat's little theorem holds for every integer $a$ , including multiples of $p$ ." The statement $a^{p - 1} \equiv 1 (mod p)$ requires $g cd (a, p) = 1$ . The case $a \equiv 0 (mod p)$ gives $a^{p - 1} \equiv 0$ , not $1$ . The unrestricted form $a^{p} \equiv a (mod p)$ (which both forms imply for $a \neq \equiv 0$ ) does cover $a \equiv 0$ ( $0^{p} = 0$ ).
"Euler's theorem applies to every modulus the same way." The exponent $φ (n)$ is the group order, not necessarily the group exponent. For $n = 8$ , $φ (8) = 4$ but $λ (8) = 2$ : every $a$ coprime to $8$ satisfies $a^{2} \equiv 1 (mod 8)$ , a strict refinement of $a^{4} \equiv 1 (mod 8)$ . The tight bound is $λ (n)$ , not $φ (n)$ ; this matters for cryptographic key-strength estimates.
"Wilson's theorem extends to composite moduli as $(n - 1)! \equiv - 1 (mod n)$ ." False — and decisively so. For composite $n > 4$ , $(n - 1)! \equiv 0 (mod n)$ : the factors $1, 2, \dots, n - 1$ contain both factors of any non-degenerate factorisation $n = ab$ with $1 < a, b < n$ (with $a \neq = b$ separable for $n > 4$ ; the $n = 4$ case is the lone exception). The converse — if $(n - 1)! \equiv - 1 (mod n)$ then $n$ is prime — is a genuine primality criterion.

Key theorem with proof Intermediate+

The signature theorem of this unit is Fermat's little theorem in its modern group-theoretic form. We give the proof via Lagrange's theorem applied to $(Z / p Z)^{\times}$ , and then deduce Euler's and Wilson's theorems as direct consequences.

Theorem (Fermat's little theorem). Let $p$ be a prime and $a$ an integer with $g cd (a, p) = 1$ . Then $a^{p - 1} \equiv 1 (mod p)$ . Equivalently, $a^{p} \equiv a (mod p)$ for every integer $a$ .

Proof. The set $(Z / p Z)^{\times}$ of nonzero residues modulo $p$ is a group under multiplication, with identity $[1]_{p}$ and order $p - 1$ (every nonzero residue is a unit because $p$ is prime; this is the field property of $Z / p Z$ from 21.01.03).

Since $g cd (a, p) = 1$ , the residue $[a]_{p}$ lies in $(Z / p Z)^{\times}$ . By Lagrange's theorem on finite groups (proved in 01.02.01), the order of any element divides the order of the group: $$ \mathrm{ord}([a]_p) ;\big|; #(\mathbb{Z}/p\mathbb{Z})^\times = p - 1. $$ Writing $p - 1 = k \cdot ord ([a]_{p})$ for some positive integer $k$ : $$ [a]_p^{p-1} ;=; \left([a]_p^{\mathrm{ord}([a]_p)}\right)^k ;=; [1]_p^k ;=; [1]_p. $$ Hence $a^{p - 1} \equiv 1 (mod p)$ .

To extend to the form $a^{p} \equiv a (mod p)$ for every integer $a$ : if $g cd (a, p) = 1$ , multiply both sides of $a^{p - 1} \equiv 1 (mod p)$ by $a$ to get $a^{p} \equiv a (mod p)$ . If $g cd (a, p) > 1$ , then $p ∣ a$ , so both $a^{p}$ and $a$ are $\equiv 0 (mod p)$ . $□$

Bridge. Fermat's little theorem builds toward 21.01.05 primitive roots, where the cyclic structure of $(Z / p Z)^{\times}$ is sharpened to the existence of an element of order exactly $p - 1$ — the order-divides-group-order fact above promoted to an order-equals-group-order witness. The central insight is exactly that the multiplicative cyclic structure of nonzero residues modulo a prime is the operational content of the field property of $F_{p}$ ; this is the bridge from elementary number theory to 01.02.18 pending finite fields $F_{q}$ and Frobenius. The pattern generalises: replacing $p$ by an arbitrary integer $n$ and $p - 1$ by $φ (n)$ gives Euler's theorem; replacing $φ (n)$ by the group exponent $λ (n)$ gives the tight Carmichael refinement; identifying the orbit of $a$ in $F_{p}^{\times}$ with the action of the Frobenius $Frob_{p}$ on $\overline{F_{p}}$ identifies Fermat's theorem with the splitting structure of finite Galois extensions. The same identification appears again in 01.02.18 pending as the statement that $Frob_{p}$ fixes $F_{p}$ pointwise. Putting these together with Lagrange and the order-divides-group-order pattern, Fermat is the prototype of every "group acting by multiplication has finite orbits of divisor length" theorem in algebra.

Exercises Intermediate+

Exercise 3 (medium, numeric).

A toy RSA setup uses primes $p = 11$ , $q = 13$ , public exponent $e = 7$ . Compute the private exponent $d$ , the integer in the range $1 \leq d < φ (N)$ with $e d \equiv 1 (mod φ (N))$ where $N = pq$ . Then decrypt the ciphertext $C = 5$ , i.e., compute $M = C^{d} mod N$ .

Hint

Compute $φ (N) = (p - 1) (q - 1) = 120$ . Find $d$ with $7 d \equiv 1 (mod 120)$ via the extended Euclidean algorithm. Then use Euler's theorem to simplify $C^{d} mod N$ via CRT-on- $p$ -and- $q$ .

Answer

$d = 103$ , $M = 125 mod 143 = 125$ — wait, recompute carefully. Take $N = 11 \cdot 13 = 143$ and $φ (N) = 10 \cdot 12 = 120$ . Solve $7 d \equiv 1 (mod 120)$ : extended Euclidean on $(7, 120)$ gives $120 = 17 \cdot 7 + 1$ , so $1 = 120 - 17 \cdot 7$ , and $d \equiv - 17 \equiv 103 (mod 120)$ . Check: $7 \cdot 103 = 721 = 6 \cdot 120 + 1 \equiv 1 (mod 120)$ .

Decrypt: $M = 5^{103} mod 143$ . Compute via CRT-on- $p$ -and- $q$ . Modulo $11$ : $5^{103} mod 11$ . By Fermat, $5^{10} \equiv 1 (mod 11)$ , so reduce $103 = 10 \cdot 10 + 3$ , giving $5^{103} \equiv 5^{3} = 125 \equiv 4 (mod 11)$ (since $125 = 11 \cdot 11 + 4$ ). Modulo $13$ : $5^{103} mod 13$ . By Fermat, $5^{12} \equiv 1 (mod 13)$ , so $103 = 8 \cdot 12 + 7$ , giving $5^{103} \equiv 5^{7} (mod 13)$ . Compute $5^{2} = 25 \equiv 12 \equiv - 1 (mod 13)$ , so $5^{7} = 5 \cdot (5^{2})^{3} \equiv 5 \cdot (- 1)^{3} = - 5 \equiv 8 (mod 13)$ . CRT: find $M \in [0, 142]$ with $M \equiv 4 (mod 11)$ and $M \equiv 8 (mod 13)$ . Write $M = 11 k + 4$ ; the second condition gives $11 k + 4 \equiv 8 (mod 13)$ , i.e., $11 k \equiv 4 (mod 13)$ , i.e., $- 2 k \equiv 4 (mod 13)$ , so $k \equiv - 2 \equiv 11 (mod 13)$ . Take $k = 11$ : $M = 11 \cdot 11 + 4 = 125$ . Check: $125 = 11 \cdot 11 + 4 \equiv 4 (mod 11)$ ; $125 = 9 \cdot 13 + 8 \equiv 8 (mod 13)$ . So $M = 125$ . (Indeed $5^{103} mod 143 = 125$ .)

Exercise 4 (medium, symbolic).

Prove Euler's theorem: for $g cd (a, n) = 1$ , $a^{φ (n)} \equiv 1 (mod n)$ .

Hint

The proof is identical in structure to Fermat's, with $(Z / p)^{\times}$ replaced by $(Z / n)^{\times}$ . Apply Lagrange's theorem to the group of order $φ (n)$ .

Answer

The set $(Z / n Z)^{\times}$ of residue classes coprime to $n$ is a finite abelian group of order $φ (n)$ . Since $g cd (a, n) = 1$ , $[a]_{n}$ lies in this group.

By Lagrange's theorem, the order of any element divides the order of the group, so $ord ([a]_{n}) ∣ φ (n)$ . Writing $φ (n) = k \cdot ord ([a]_{n})$ : $$ [a]_n^{\varphi(n)} ;=; \left([a]_n^{\mathrm{ord}([a]_n)}\right)^k ;=; [1]_n^k ;=; [1]_n. $$ Hence $a^{φ (n)} \equiv 1 (mod n)$ .

The specialisation $n = p$ recovers Fermat's little theorem, since $φ (p) = p - 1$ . The further refinement using the Carmichael function $λ (n)$ instead of $φ (n)$ gives the tight statement $a^{λ (n)} \equiv 1 (mod n)$ .

Rubric: full credit for identifying $(Z / n)^{\times}$ as the operative group, applying Lagrange, and naming the order $φ (n)$ .

Exercise 5 (medium, symbolic).

Prove Wilson's theorem: for $p$ prime, $(p - 1)! \equiv - 1 (mod p)$ .

Hint

Pair each element of $(Z / p Z)^{\times}$ with its multiplicative inverse. Most pairs collapse to $1$ in the product. The self-inverse elements are exactly $\pm 1$ , and the field property of $F_{p}$ supplies this.

Answer

In the group $G = (Z / p Z)^{\times}$ of order $p - 1$ , every element $[a]_{p}$ has a unique inverse $[a^{- 1}]_{p}$ . An element is self-inverse when $[a]_{p}^{2} = [1]_{p}$ , i.e., $a^{2} \equiv 1 (mod p)$ . Equivalently $(a - 1) (a + 1) \equiv 0 (mod p)$ . Since $F_{p} = Z / p Z$ is a field (an integral domain), $(a - 1) (a + 1) \equiv 0$ forces $a \equiv 1 (mod p)$ or $a \equiv - 1 (mod p)$ .

Hence the only self-inverse elements of $G$ are $[1]_{p}$ and $[- 1]_{p}$ . In the product $$ \prod_{[a]_p \in G} [a]_p ;=; (p - 1)! \pmod p, $$ every non-self-inverse element pairs with its distinct inverse, contributing $1$ to the product. The remaining unpaired factors are $[1]_{p}$ and $[- 1]_{p}$ , multiplying to $[- 1]_{p}$ . Hence $(p - 1)! \equiv - 1 (mod p)$ .

For $p = 2$ the statement is degenerate but holds: $(2 - 1)! = 1! = 1 \equiv - 1 (mod 2)$ . For $p = 7$ : $6! = 720 = 102 \cdot 7 + 6 \equiv 6 \equiv - 1 (mod 7)$ .

Rubric: full credit for the pairing argument with the field-property identification of self-inverses.

Exercise 6 (medium, symbolic).

Prove the converse of Wilson's theorem: if $(n - 1)! \equiv - 1 (mod n)$ for $n \geq 2$ , then $n$ is prime.

Hint

Argue by contrapositive: if $n$ is composite with $n > 4$ , show $(n - 1)! \equiv 0 (mod n)$ ; if $n = 4$ , compute $3!$ directly.

Answer

Argue by contrapositive. Suppose $n$ is composite, $n \geq 2$ .

Case $n > 4$ , $n$ composite. Write $n = ab$ with $1 < a, b < n$ . If $a \neq = b$ , then both $a$ and $b$ appear as separate factors in $(n - 1)! = 1 \cdot 2 \dots (n - 1)$ (since $a, b < n$ ), so $ab = n$ divides $(n - 1)!$ . If $a = b$ , then $n = a^{2}$ with $a \geq 3$ (since $n > 4$ ). Both $a$ and $2 a$ lie in ${1, 2, \dots, n - 1}$ (the condition $2 a < n = a^{2}$ requires $a > 2$ , satisfied since $a \geq 3$ ), so $2 a^{2} = 2 n$ divides $(n - 1)!$ , hence $n ∣ (n - 1)!$ . In both subcases $(n - 1)! \equiv 0 (mod n)$ , in particular $\neq \equiv - 1$ .

Case $n = 4$ . $(4 - 1)! = 3! = 6 \equiv 2 (mod 4)$ , not $\equiv - 1 \equiv 3 (mod 4)$ .

Case $n$ prime. Wilson gives $(n - 1)! \equiv - 1 (mod n)$ .

So $(n - 1)! \equiv - 1 (mod n)$ if and only if $n$ is prime. This is a genuine primality criterion, but its time complexity is exponential in $lo g n$ (computing $(n - 1)!$ takes $n$ multiplications) — impractical compared to the Miller-Rabin or AKS tests of [Master Theorem 6].

Rubric: full credit for the contrapositive case-split with the explicit handling of $n = 4$ as the lone exception.

Exercise 7 (hard, symbolic).

Prove Korselt's criterion ^{[Korselt 1899]}: a composite integer $n > 1$ satisfies $a^{n - 1} \equiv 1 (mod n)$ for every integer $a$ coprime to $n$ if and only if $n$ is squarefree and $(p - 1) ∣ (n - 1)$ for every prime $p$ dividing $n$ .

Hint

Use the CRT decomposition $(Z / n)^{\times} ≅ \prod_{p ∣ n} (Z / p^{e_{p}})^{\times}$ from 21.01.03. The condition $a^{n - 1} \equiv 1 (mod n)$ for all $a$ coprime to $n$ is equivalent to the Carmichael function $λ (n)$ dividing $n - 1$ .

Answer

The hypothesis $a^{n - 1} \equiv 1 (mod n)$ for every $a$ coprime to $n$ is the statement that the exponent of the group $(Z / n)^{\times}$ divides $n - 1$ — equivalently, $λ (n) ∣ (n - 1)$ .

Forward direction. Suppose $λ (n) ∣ (n - 1)$ and $n$ is composite. By the CRT structure from 21.01.03, $λ (n) = lcm_{p} λ (p^{e_{p}})$ where $n = \prod p^{e_{p}}$ . For $p$ odd, $λ (p^{e_{p}}) = p^{e_{p} - 1} (p - 1)$ (the group $(Z / p^{e_{p}})^{\times}$ is cyclic). If any $e_{p} \geq 2$ , then $p ∣ λ (p^{e_{p}}) ∣ λ (n) ∣ (n - 1)$ , so $p ∣ (n - 1)$ . But also $p ∣ n$ , hence $p ∣ g cd (n, n - 1) = 1$ , a contradiction. So $e_{p} = 1$ for every odd prime divisor of $n$ . The case $p = 2$ gives $λ (2^{e_{2}})$ as $1, 1, 2$ for $e_{2} = 0, 1, 2$ and $2^{e_{2} - 2}$ for $e_{2} \geq 3$ ; a similar argument plus $2 ∣ n \Rightarrow 2 ∤ (n - 1)$ forces $e_{2} \leq 1$ . Hence $n$ is squarefree.

With $n$ squarefree, $λ (p) = p - 1$ for each prime divisor, so $λ (n) = lcm_{p} (p - 1)$ . The condition $λ (n) ∣ (n - 1)$ is equivalent to $(p - 1) ∣ (n - 1)$ for every prime $p ∣ n$ .

Reverse direction. Suppose $n$ is squarefree with $(p - 1) ∣ (n - 1)$ for every $p ∣ n$ . Then $λ (n) = lcm_{p} (p - 1) ∣ (n - 1)$ , so $a^{n - 1} \equiv 1 (mod n)$ for every $a$ coprime to $n$ .

The smallest Carmichael number is $561 = 3 \cdot 11 \cdot 17$ (squarefree; $2 ∣ 560$ , $10 ∣ 560$ , $16 ∣ 560$ ). The next few are $1105, 1729, 2465, 2821, 6601, 8911, \dots$ . Alford-Granville-Pomerance 1994 Annals 140, 703 ^{[Alford-Granville-Pomerance 1994]} proved that there are infinitely many such $n$ — answering a 1912 question of Carmichael.

Rubric: full credit for the $λ (n) ∣ (n - 1)$ reformulation and the squarefree-forcing case-split.

Exercise 8 (hard, symbolic).

Prove Gauss's generalisation of Wilson ^{[Gauss 1801]}: for $n > 1$ , $$ \prod_{\gcd(a, n) = 1,, 1 \leq a \leq n} a ;\equiv; \begin{cases} -1 \pmod n & \text{if } n = 4, p^e, 2 p^e \text{ for an odd prime } p, \ +1 \pmod n & \text{otherwise.} \end{cases} $$

Hint

The product of all elements of a finite abelian group $G$ equals the product of all elements of order $\leq 2$ (the others pair off via $g \mapsto g^{- 1}$ ). Identify when the order- $2$ subgroup of $(Z / n)^{\times}$ has exactly one non-identity element.

Answer

Let $G = (Z / n)^{\times}$ and let $S = \prod_{a \in G} a$ . Pair each $g \in G$ with $g^{- 1}$ . Elements with $g \neq = g^{- 1}$ contribute $1$ to $S$ via the pair. Self-inverse elements (those with $g^{2} = 1$ ) contribute themselves. Hence $$ S ;=; \prod_{g \in G, , g^2 = 1} g. $$ The subgroup $G [2] = {g \in G : g^{2} = 1}$ is a finite abelian group of exponent $2$ , hence an elementary abelian $2$ -group: $G [2] ≅ (Z /2)^{t}$ for some $t \geq 0$ . The product of all elements of $(Z /2)^{t}$ is $(0, 0, \dots, 0)$ — the identity — when $t \geq 2$ (every coordinate sums an equal number of $0$ s and $1$ s), and equals the unique non-identity element when $t = 1$ . When $t = 0$ (i.e., $G [2]$ is the identity group, meaning $∣ G ∣$ is odd), $S = 1$ .

Cases. By the CRT structure of 21.01.03, $G = (Z / n)^{\times} ≅ \prod_{p} (Z / p^{e_{p}})^{\times}$ . The order- $2$ subgroup decomposes as $\prod_{p} G_{p} [2]$ . For $p$ odd, $(Z / p^{e})^{\times}$ is cyclic of even order $p^{e - 1} (p - 1)$ , hence has exactly one element of order $2$ (namely $[- 1]_{p^{e}}$ ); $∣ G_{p} [2] ∣ = 2$ . For $p = 2$ : $G_{2} [2]$ is the identity group for $e \leq 1$ , has order $2$ for $e = 2$ , and order $4$ for $e \geq 3$ .

So $t =$ (number of odd-prime divisors of $n$ ) $+ ϵ$ , where $ϵ \in {0, 1, 2}$ depending on the power of $2$ in $n$ . The case $t = 1$ — exactly one non-identity self-inverse element — happens precisely for $n \in {4, p^{e}, 2 p^{e}}$ with $p$ an odd prime. In this case the unique self-inverse element is $[- 1]_{n}$ , giving $S \equiv - 1 (mod n)$ . In every other case $t \geq 2$ , giving $S \equiv 1 (mod n)$ .

Wilson's classical theorem is the specialisation to $n = p$ prime, where $G = (Z / p)^{\times}$ has order $p - 1$ and $S = (p - 1)! \equiv - 1 (mod p)$ .

Rubric: full credit for the $G [2]$ reduction, the structure-theorem identification of $G [2]$ as elementary abelian, and the case-split on the number of factors.

Lean formalization Intermediate+

Mathlib supplies all three signature theorems and the operative supporting machinery. The Lean module Codex.NumberTheory.Elementary.FermatEulerWilson would package the unit's identifications alongside the standard Mathlib API.

-- Operative imports: Mathlib.Data.ZMod.Basic, Mathlib.Data.Nat.Totient,
-- Mathlib.NumberTheory.LucasLehmer, Mathlib.NumberTheory.Wilson,
-- Mathlib.GroupTheory.OrderOfElement, Mathlib.RingTheory.Polynomial.Cyclotomic.Basic

#check @ZMod.pow_card_sub_one_eq_one
-- Fermat's little theorem: for p prime, a : ZMod p with a ≠ 0 satisfies a^(p - 1) = 1.

#check @ZMod.pow_card
-- The unrestricted form: a^p ≡ a (mod p) for every integer a.

#check @ZMod.pow_totient
-- Euler's theorem: for n : ℕ with Coprime a n, a^(Nat.totient n) ≡ 1 (mod n).

#check @ZMod.wilsons_lemma
-- Wilson's theorem: for p prime, (p - 1)! ≡ -1 (mod p).

#check @Nat.totient
-- The Euler totient function, defined as the cardinality of the unit group.

#check @Nat.totient_prime_pow
-- φ(p^k) = p^(k - 1) * (p - 1) for p prime and k ≥ 1.

#check @orderOf_dvd_card
-- The general Lagrange-consequence: orderOf g divides Fintype.card G in a finite group.

The Fermat-Euler-Wilson trio in Mathlib rests on orderOf_dvd_card — the Lagrange-theorem consequence that the order of any element divides the group order. The polynomial-identity proof of Wilson is ZMod.wilsons_lemma and rests on the factorisation $x^{p - 1} - 1 = \prod_{a = 1}^{p - 1} (x - a)$ in $F_{p} [x]$ . What Mathlib does not yet supply as a unified module — the Carmichael function with explicit prime-power formula, Korselt's criterion, the smallest Carmichael number $561$ , the Miller-Rabin and AKS primality tests, and Gauss's generalised Wilson product — is the formalisation target documented in the unit metadata Mathlib gap analysis.

Advanced results Master

Theorem 1 (combinatorial / necklace proof of Fermat's little theorem). For $p$ prime and any integer $a \geq 1$ , the number of distinct necklaces of length $p$ over an alphabet of $a$ letters is $(a^{p} - a) / p + a$ , hence $p$ divides $a^{p} - a$ . The count: there are $a^{p}$ words of length $p$ ; the cyclic group $Z / p$ acts by rotation; orbits of monochromatic words have size $1$ (there are $a$ of these), and orbits of non-monochromatic words have size dividing $p$ , hence equal to $p$ (since $p$ is prime). So $a^{p} - a$ is divisible by $p$ . The argument generalises to Burnside-counting orbits of any prime-power group action; see Hardy-Wright 2008 §6.3 ^{[Hardy-Wright 2008]}. The combinatorial proof predates Euler's algebraic proof and is the natural argument for $p$ -adic-flavoured generalisations.

Theorem 2 (Euler's induction proof of Fermat). Fermat's little theorem in the form $a^{p} \equiv a (mod p)$ follows by induction on $a$ using $(a + 1)^{p} \equiv a^{p} + 1 (mod p)$ [Euler 1736]. The induction step uses the freshman's dream: in $F_{p}$ , $(a + b)^{p} = a^{p} + b^{p}$ , because every middle binomial coefficient $(k p)$ for $1 \leq k \leq p - 1$ is divisible by $p$ (the formula $(k p) = p! / (k! (p - k)!)$ contains $p$ in the numerator with no compensating factor in the denominator). Iterating from the base case $a = 1$ gives $a^{p} \equiv a (mod p)$ for every positive integer $a$ . Euler 1736 Comm. Acad. Sci. Petrop. 8 published this as the first proof of Fermat's little theorem; the freshman's-dream identity is also the operational content of the Frobenius endomorphism $Frob_{p} : F_{p} \to F_{p}$ , $x \mapsto x^{p}$ , being a ring homomorphism — the bridge to 01.02.18 pending finite fields.

Theorem 3 (Carmichael function and its prime-power formula). The Carmichael function $λ (n)$ , the exponent of $(Z / n)^{\times}$ , has values $λ (1) = λ (2) = 1$ , $λ (4) = 2$ , $λ (2^{k}) = 2^{k - 2}$ for $k \geq 3$ , $λ (p^{k}) = p^{k - 1} (p - 1)$ for $p$ an odd prime, and $λ (n) = lcm_{p} λ (p^{e_{p}})$ for $n = \prod p^{e_{p}}$ . ^{[Carmichael 1910]}. Always $λ (n) ∣ φ (n)$ , with equality if and only if $(Z / n)^{\times}$ is cyclic, which characterises $n \in {1, 2, 4, p^{k}, 2 p^{k}}$ for $p$ an odd prime. The Carmichael function is the tight exponent in Euler's theorem: $a^{λ (n)} \equiv 1 (mod n)$ for every $a$ coprime to $n$ , and $λ (n)$ is the least such integer. RSA security depends on $λ (N)$ , not $φ (N)$ : the private exponent satisfies $e d \equiv 1 (mod λ (N))$ as the necessary condition, with $λ (N) = lcm (p - 1, q - 1)$ for $N = pq$ .

Theorem 4 (Korselt's criterion and Carmichael numbers; Korselt 1899, Alford-Granville-Pomerance 1994). A composite integer $n$ is a Carmichael number (satisfying $a^{n - 1} \equiv 1 (mod n)$ for every $a$ coprime to $n$ ) if and only if $n$ is squarefree and $(p - 1) ∣ (n - 1)$ for every prime $p$ dividing $n$ ^{[Korselt 1899]}. The smallest Carmichael number is $561 = 3 \cdot 11 \cdot 17$ : squarefree, and $2 ∣ 560$ , $10 ∣ 560$ , $16 ∣ 560$ . The next few are $1105 = 5 \cdot 13 \cdot 17$ , $1729 = 7 \cdot 13 \cdot 19$ (Ramanujan's taxicab), $2465, 2821, 6601, 8911$ . Alford-Granville-Pomerance 1994 Annals 140, 703 ^{[Alford-Granville-Pomerance 1994]} proved the count $C (x)$ of Carmichael numbers up to $x$ satisfies $C (x) > x^{2/7}$ , settling Carmichael's 1912 conjecture. Carmichael numbers are precisely the composite false-positives of the Fermat primality test, motivating the strong-pseudoprime refinement of Miller-Rabin.

Theorem 5 (Miller-Rabin probabilistic primality test; Miller 1976, Rabin 1980). Let $n - 1 = 2^{s} d$ with $d$ odd. A composite $n$ is called a strong pseudoprime to base $a$ if $a^{d} \equiv 1 (mod n)$ or $a^{2^{r} d} \equiv - 1 (mod n)$ for some $0 \leq r < s$ . For every composite $n > 9$ , at most $1/4$ of bases $a \in {1, \dots, n - 1}$ are strong-pseudoprime witnesses ^{[Rabin 1980]}. The Miller-Rabin algorithm: for $k$ randomly chosen bases $a_{1}, \dots, a_{k}$ , declare $n$ "probably prime" if every $a_{i}$ is a strong-pseudoprime witness; declare composite otherwise. The false-positive probability is $4^{- k}$ for composite inputs. With $k = 40$ , the false-positive rate is below $2^{- 80}$ — well below cosmic-ray bit-flip error rates. Standard library implementations (OpenSSL, GMP, Java's BigInteger.isProbablePrime) use Miller-Rabin with $k$ ranging from $20$ to $128$ for RSA key generation. Miller 1976 originally proved a deterministic variant assuming the generalised Riemann hypothesis.

Theorem 6 (AKS deterministic polynomial-time primality test; Agrawal-Kayal-Saxena 2004). PRIMES is in P: there exists a deterministic algorithm that decides primality of $n$ in time polynomial in $lo g n$ ^{[AKS 2004]}. The Agrawal-Kayal-Saxena algorithm rests on a polynomial-identity strengthening of Fermat's little theorem: for $n > 1$ coprime to $a$ , $n$ is prime if and only if $(x + a)^{n} \equiv x^{n} + a (mod n, x^{r} - 1)$ as a polynomial identity in $(Z / n) [x] / (x^{r} - 1)$ , for an appropriately chosen $r$ of order $> (lo g n)^{2}$ in $(Z / n)^{\times}$ . The original algorithm runs in $\tilde{O} ((lo g n)^{12})$ ; Lenstra-Pomerance refinements bring it to $\tilde{O} ((lo g n)^{6})$ . AKS settled a long-standing open question — whether primality is in deterministic polynomial time — and confirmed that the polynomial-identity criterion is essentially the "right" generalisation of Fermat's congruence. In practice Miller-Rabin remains faster for RSA key generation, but AKS is the deterministic certificate of theoretical interest.

Theorem 7 (Gauss's generalised Wilson; Gauss 1801 art. 78). For $n > 1$ , $$ \prod_{\gcd(a, n) = 1, , 1 \leq a \leq n} a ;\equiv; \begin{cases} -1 \pmod n, & n \in {4, p^e, 2 p^e} \text{ for $p$ an odd prime,} \ +1 \pmod n, & \text{otherwise.} \end{cases} $$ ^{[Gauss 1801]}. The sign tracks whether $(Z / n)^{\times}$ has exactly one element of order $2$ (in which case the unpaired self-inverse $- 1$ contributes the $- 1$ ) or more than one (in which case the product of self-inverses collapses to $1$ ). The classification of cyclic $(Z / n)^{\times}$ — itself due to Gauss 1801 §III — supplies the case structure: $(Z / n)^{\times}$ is cyclic iff $n \in {1, 2, 4, p^{e}, 2 p^{e}}$ for $p$ an odd prime, and exactly these moduli (with the $n = 1, 2$ degenerate cases) give the $- 1$ branch.

Theorem 8 (RSA correctness and security; Rivest-Shamir-Adleman 1978). *Let $N = pq$ be a product of two distinct primes, $e$ an integer coprime to $φ (N) = (p - 1) (q - 1)$ , and $d$ the modular inverse of $e$ modulo $φ (N)$ . For every integer $M$ with $0 \leq M < N$ , $M^{e d} \equiv M (mod N)$ * ^{[Rivest-Shamir-Adleman 1978]}. *Proof.* If $g cd (M, N) = 1$ , then by Euler $M^{φ (N)} \equiv 1 (mod N)$ , so $M^{e d} = M^{1 + k φ (N)} = M \cdot (M^{φ (N)})^{k} \equiv M (mod N)$ . If $g cd (M, N) > 1$ , then $p ∣ M$ or $q ∣ M$ (not both, since $M < N = pq$ ); CRT on $p$ and $q$ separately gives $M^{e d} \equiv M$ in each factor, hence modulo $N$ . Security rests on the assumption that factoring $N$ is computationally hard: Coppersmith 1996 and Boneh-Durfee 2000 showed that knowing $d$ (or even partial knowledge of $d$ when $d$ is small) reduces to factoring; Shor 1994 showed that quantum algorithms factor in polynomial time, motivating post-quantum cryptography. RSA underpinned essentially all of e-commerce from 1995 until the post-quantum transition began in the late 2010s.

Synthesis. The Fermat-Euler-Wilson trio is the foundational reason that the multiplicative structure of finite fields and finite cyclic groups governs every elementary primality and exponentiation result in number theory. The central insight is exactly that the order of any element divides the order of the group containing it — Lagrange's theorem applied to $(Z / p)^{\times}$ and $(Z / n)^{\times}$ — and the entire chain of theorems above unfolds from this single fact. Putting these together with the Carmichael refinement, the tight exponent of $(Z / n)^{\times}$ is $λ (n)$ not $φ (n)$ , and this is exactly the operational content that makes the Fermat test fail on Carmichael numbers, the Miller-Rabin test recover correctness via strong pseudoprimes, and the AKS criterion supply a deterministic polynomial-identity replacement.

The pattern generalises in multiple directions. Replacing the discrete group $(Z / p)^{\times}$ by the elliptic-curve group $E (F_{p})$ identifies Fermat's theorem with the Hasse-Weil bound and underwrites elliptic-curve primality proving and ECDSA; replacing the integer modulus $n$ by a polynomial modulus $f \in F_{q} [x]$ identifies Fermat with the Frobenius decomposition $Frob_{q} : \overline{F_{q}} \to \overline{F_{q}}$ fixing $F_{q}$ pointwise, the bridge to 01.02.18 pending finite fields and Frobenius; replacing the multiplicative group by an additive flavour identifies Wilson with the sum formulas $\sum_{a \in F_{p}^{\times}} a = 0$ for $p \neq = 2$ . The bridge is everywhere the same: a finite-order multiplicative structure produces a cancellation identity, and primality is exactly the condition for the structure to be cyclic of maximal order.

The applied consequences are pervasive. RSA decryption rests on Euler's theorem; Diffie-Hellman key exchange and the Digital Signature Algorithm rest on the cyclic structure of $(Z / p)^{\times}$ that Fermat encodes; Miller-Rabin and AKS rest on strengthenings of Fermat's congruence; elliptic-curve cryptography reuses the same group-theoretic framework over $E (F_{p})$ . The post-quantum transition motivated by Shor 1994 keeps the cyclic-group structure but replaces the underlying hard problem (factoring, discrete log) with lattice-based or code-based or isogeny-based alternatives — yet even the new schemes inherit the Lagrange-orbit cancellation as their proof-of-correctness identity. Fermat's 1640 letter to Frénicle was the seed of all modern public-key cryptography.

Full proof set Master

Proposition 1 (Fermat's little theorem, polynomial-identity proof in $F_{p} [x]$ ). For $p$ prime, the polynomial identity $$ x^{p - 1} - 1 ;=; \prod_{a = 1}^{p - 1}(x - a) \quad \text{in } \mathbb{F}_p[x] $$ holds, recovering Fermat's little theorem $a^{p - 1} \equiv 1 (mod p)$ for $1 \leq a \leq p - 1$ as the evaluations of the left-hand side at each root.

Proof. The polynomial $x^{p - 1} - 1 \in F_{p} [x]$ has degree $p - 1$ . By Fermat's little theorem (proved separately above via Lagrange), every element $a \in F_{p}^{\times} = {1, 2, \dots, p - 1}$ satisfies $a^{p - 1} - 1 \equiv 0 (mod p)$ , so $x = a$ is a root in $F_{p}$ .

A polynomial of degree $d$ over a field has at most $d$ roots. The polynomial $x^{p - 1} - 1$ has $p - 1$ distinct roots in $F_{p}$ — the full set ${1, 2, \dots, p - 1}$ . Hence the factorisation $$ x^{p - 1} - 1 ;=; \prod_{a = 1}^{p - 1}(x - a) $$ holds in $F_{p} [x]$ . The two sides have equal degree and equal roots; their leading coefficients are both $1$ , so they agree. $□$

The polynomial-identity form is equivalent to Fermat but conceptually sharper: it identifies $F_{p}^{\times}$ as the set of roots of $x^{p - 1} - 1$ in $F_{p}$ , exposing $F_{p}$ as the splitting field of a separable polynomial of degree $p - 1$ . The Frobenius generalisation to $F_{p^{n}}$ replaces $p - 1$ by $p^{n} - 1$ and produces the same factorisation.

Proposition 2 (Euler's theorem, group-theoretic proof). For $g cd (a, n) = 1$ , $a^{φ (n)} \equiv 1 (mod n)$ .

Proof. The group $(Z / n Z)^{\times}$ has order $φ (n)$ . The residue $[a]_{n}$ lies in this group because $g cd (a, n) = 1$ . By Lagrange's theorem on finite groups, the order of any element divides the order of the group, so $ord ([a]_{n}) ∣ φ (n)$ . Writing $φ (n) = k \cdot ord ([a]_{n})$ : $$ [a]_n^{\varphi(n)} ;=; \left([a]_n^{\mathrm{ord}([a]_n)}\right)^k ;=; [1]_n^k ;=; [1]_n. \qquad \square $$

Proposition 3 (Lagrange's proof of Wilson via polynomial coefficients). For $p$ prime, $(p - 1)! \equiv - 1 (mod p)$ .

Proof (Lagrange 1771). Consider the polynomial $$ f(x) ;=; (x - 1)(x - 2) \cdots (x - (p - 1)) - (x^{p - 1} - 1) ;\in; \mathbb{F}_p[x]. $$ The first factor expands to a polynomial of degree $p - 1$ with leading coefficient $1$ and constant term $(- 1)^{p - 1} (p - 1)!$ . The second has leading coefficient $1$ and constant term $- 1$ . So $f (x)$ has degree at most $p - 2$ (the leading terms cancel) and constant term $(- 1)^{p - 1} (p - 1)! + 1$ .

By Proposition 1, $\prod_{a = 1}^{p - 1} (x - a) = x^{p - 1} - 1$ in $F_{p} [x]$ , so $f (x) = 0$ identically in $F_{p} [x]$ . All coefficients vanish — in particular the constant coefficient: $(- 1)^{p - 1} (p - 1)! + 1 \equiv 0 (mod p)$ . For $p$ odd, $(- 1)^{p - 1} = 1$ , giving $(p - 1)! \equiv - 1 (mod p)$ . For $p = 2$ , the identity reduces to $1! = 1 \equiv - 1 (mod 2)$ , also valid. $□$

This is the proof Lagrange 1771 Nouv. Mém. Acad. Berlin 2 published. The pairing-and-self-inverses argument from Exercise 5 is the modern textbook proof; both arguments produce the same conclusion via different operational content.

Proposition 4 (Korselt's criterion). A composite integer $n$ satisfies $a^{n - 1} \equiv 1 (mod n)$ for every $a$ coprime to $n$ if and only if $n$ is squarefree and $(p - 1) ∣ (n - 1)$ for every prime $p$ dividing $n$ .

Proof. The condition is equivalent to $λ (n) ∣ (n - 1)$ . By the CRT decomposition $(Z / n)^{\times} ≅ \prod_{p} (Z / p^{e_{p}})^{\times}$ and the prime-power formula $λ (p^{e}) = p^{e - 1} (p - 1)$ for $p$ odd (with $λ (2^{e})$ adjusted by the cyclic-versus-non-cyclic distinction), $λ (n) = lcm_{p} λ (p^{e_{p}})$ .

If any $e_{p} \geq 2$ for $p$ odd, then $p ∣ λ (p^{e_{p}}) ∣ λ (n) ∣ (n - 1)$ . But $p ∣ n$ , so $p ∣ g cd (n, n - 1) = 1$ , contradiction. Hence $n$ is squarefree at every odd prime. The case $p = 2$ with $e_{2} \geq 2$ is similarly ruled out by $2 ∣ n \Rightarrow 2 ∤ (n - 1)$ .

With $n$ squarefree, $λ (n) = lcm_{p} (p - 1)$ , and $λ (n) ∣ (n - 1)$ is equivalent to $(p - 1) ∣ (n - 1)$ for every $p ∣ n$ . The converse is immediate. $□$

The smallest Carmichael number is $561 = 3 \cdot 11 \cdot 17$ : squarefree, and $560 = 2^{4} \cdot 5 \cdot 7$ is divisible by $2 = 3 - 1$ , $10 = 11 - 1$ , $16 = 17 - 1$ . Alford-Granville-Pomerance 1994 Annals 140, 703 proved infinitely many Carmichael numbers exist, with density $C (x) > x^{2/7}$ .

Connections Master

Congruences and the CRT 21.01.03. Just shipped. The unit-group framework $(Z / n)^{\times}$ developed in 21.01.03 is the operative setting of all three Fermat-Euler-Wilson theorems. The CRT decomposition $(Z / n)^{\times} ≅ \prod_{p} (Z / p^{e_{p}})^{\times}$ supplies the prime-power reduction used in the Carmichael-function formula, Korselt's criterion, Gauss's generalised Wilson, and the CRT-based RSA decryption speedup. The totient $φ (n)$ is the cardinality and $λ (n)$ the exponent of this group; the multiplicativity of both functions descends from CRT. The present unit is operationally the next layer above the unit-group structure of 21.01.03.
Primes and the fundamental theorem 21.01.02. Shipped. Fermat's little theorem and Wilson's theorem are characterisations of primes: $a^{n - 1} \equiv 1 (mod n)$ for all $a$ coprime to $n$ fails generically on composites (Carmichael numbers are the celebrated exceptions); $(n - 1)! \equiv - 1 (mod n)$ holds if and only if $n$ is prime (the converse of Wilson). The fundamental theorem of arithmetic from 21.01.02 supplies the prime-power factorisation that feeds the structure theorem for $(Z / n)^{\times}$ , which is the engine of every result in this unit. Wilson's converse is a clean primality decision procedure — exponentially slow, but theoretically perfect.
Group 01.02.01. Shipped. The proofs of Fermat and Euler rest on Lagrange's theorem applied to the finite groups $(Z / p)^{\times}$ and $(Z / n)^{\times}$ . The order-divides-group-order pattern is the categorical core of every congruence appearing in this unit. The same Lagrange-orbit framework appears again in the necklace / Burnside proof of Fermat (Theorem 1) and in the pairing argument for Wilson (Exercise 5). The cyclic-group structure theorem from 01.02.01 is the operational core of the classification of when $(Z / n)^{\times}$ is cyclic and hence when Fermat's congruence is sharp.
Primitive roots 21.01.05. Pending. A primitive root modulo $n$ is a generator of $(Z / n)^{\times}$ when this group is cyclic. Gauss 1801 §III proved primitive roots exist modulo every odd prime power $p^{k}$ and modulo $2 p^{k}$ , settling the existence side of the cyclic-classification. The sharper form of Fermat — there exists $g$ with $g^{p - 1} \equiv 1 (mod p)$ and no smaller positive exponent works — promotes "order divides $p - 1$ " to "order equals $p - 1$ " for a witness. The downstream specialisation in 21.01.05 (when shipped) develops the index calculus, discrete logarithms, and the constructive existence of primitive roots via the lifting-the-exponent lemma.
Finite fields $F_{q}$ and Frobenius 01.02.18 pending. Pending. The base case is $F_{p} = Z / p Z$ , where Fermat's congruence $a^{p} \equiv a (mod p)$ is exactly the statement that the Frobenius endomorphism $Frob_{p} : F_{p} \to F_{p}$ , $x \mapsto x^{p}$ , is the identity. The freshman's-dream identity $(a + b)^{p} = a^{p} + b^{p}$ in $F_{p}$ (used in Euler's induction proof of Fermat, Theorem 2 above) is the additivity of $Frob_{p}$ . Generalising to $F_{p^{n}}$ replaces $p - 1$ by $p^{n} - 1$ and identifies $F_{p^{n}}^{\times}$ as the fixed set of $Frob_{p}^{n}$ . The non-linear / non-abelian extension of Fermat to elliptic-curve groups appears in 04.04.03 elliptic curves.

Historical & philosophical context Master

Fermat's little theorem appears in Fermat 1640's letter of 18 October to Bernard Frénicle de Bessy ^{[Fermat 1640]}: "tout nombre premier mesure infailliblement une des puissances - 1 de quelque progression que ce soit ..." — every prime $p$ divides infinitely many $a^{k} - 1$ in any arithmetic progression. Fermat states the result, claims a proof, but withholds it for fear of being "trop long" — characteristic Fermat. No proof of Fermat's appears in his extant correspondence; the first published proof is Euler 1736 Comm. Acad. Sci. Petrop. 8, 141 ^{[Euler 1736]}, by induction on $a$ using the binomial-coefficient divisibility $(a + 1)^{p} \equiv a^{p} + 1 (mod p)$ . Euler 1763 Novi Comm. Acad. Sci. Petrop. 8, 74 ^{[Euler 1763]} introduces the totient function (which Euler writes $π N$ ) and generalises the theorem to arbitrary moduli: $a^{φ (n)} \equiv 1 (mod n)$ for $g cd (a, n) = 1$ . The modern name "Fermat's little theorem" emerged in 20th-century textbooks to distinguish the result from Fermat's Last Theorem.

Wilson's theorem was stated without proof by John Wilson and communicated by Edward Waring in Meditationes Algebraicae (1770); the first published proof is Lagrange 1771 Nouv. Mém. Acad. Berlin 2, 125 ^{[Lagrange 1771]}, via the polynomial-identity argument of Proposition 3 above. Lagrange also proved the converse — if $(n - 1)! \equiv - 1 (mod n)$ then $n$ is prime — making Wilson the first published exact primality criterion. Gauss 1801 Disquisitiones Arithmeticae arts. 50-83 ^{[Gauss 1801]} gives the canonical modern development: arts. 50-51 (Fermat-Euler), arts. 75-78 (Wilson with the modern proof via pairing and self-inverses in $F_{p}^{\times}$ ), and arts. 79-83 (the generalisation to arbitrary moduli, with the explicit sign determined by the structure of $(Z / n)^{\times}$ ). Gauss credits Fermat and Euler explicitly but proves the results from scratch; the Disquisitiones is where Fermat-Euler-Wilson enters the textbook canon.

The applied legacy crystallised in the 20th century. The Fermat primality test — declare $n$ "probably prime" if $a^{n - 1} \equiv 1 (mod n)$ for several random $a$ — was the standard heuristic until Carmichael 1910 Bull. AMS 16, 232 ^{[Carmichael 1910]} showed that composite $n$ can systematically fool the test. The Carmichael numbers are exactly the composite false-positives, characterised by Korselt 1899 Math. Ann. 53, 173 ^{[Korselt 1899]} via the criterion $n$ squarefree and $(p - 1) ∣ (n - 1)$ for every $p ∣ n$ . Carmichael 1910 supplied the first example $n = 561$ and conjectured infinitely many exist; Alford-Granville-Pomerance 1994 Annals 140, 703 ^{[Alford-Granville-Pomerance 1994]} proved this with the explicit lower bound $C (x) > x^{2/7}$ . Miller 1976 J. Comput. Syst. Sci. 13, 300 ^{[Miller 1976]} introduced strong pseudoprimes — a refinement of Fermat's congruence that excludes Carmichael numbers — and proved deterministic primality testing under the generalised Riemann hypothesis. Rabin 1980 J. Number Th. 12, 128 ^{[Rabin 1980]} randomised Miller's test, producing the de facto standard for RSA key generation.

The deterministic-polynomial-time question opened by Gauss-Carmichael-Miller-Rabin was settled by Agrawal-Kayal-Saxena 2004 Annals 160, 781 ^{[AKS 2004]}: PRIMES is in P. The AKS algorithm rests on the polynomial-identity criterion $(x + a)^{n} \equiv x^{n} + a (mod n, x^{r} - 1)$ — itself a strengthening of Fermat's congruence to a polynomial-ring identity. The original complexity $\tilde{O} ((lo g n)^{12})$ has been refined to $\tilde{O} ((lo g n)^{6})$ by Lenstra-Pomerance and subsequent authors. In practical software, Miller-Rabin remains faster for RSA key generation, but AKS is the theoretical deterministic certificate.

The cryptographic legacy is dominated by Rivest-Shamir-Adleman 1978 CACM 21, 120 ^{[Rivest-Shamir-Adleman 1978]}, who introduced RSA based on Euler's theorem applied to the modulus $N = pq$ . The decryption identity $M^{e d} \equiv M (mod N)$ rests on $e d \equiv 1 (mod φ (N))$ and Euler's $M^{φ (N)} \equiv 1 (mod N)$ for $g cd (M, N) = 1$ . Coppersmith 1996 Eurocrypt and Boneh-Durfee 2000 IEEE Trans. Inform. Theory IT-46 showed that knowing $d$ (or partial information about $d$ when $d < N^{0.292}$ ) reduces to factoring $N$ . Shor 1994 Proc. FOCS 35, 124 produced a polynomial-time quantum factoring algorithm, prompting the post-quantum cryptographic transition currently underway at NIST and global standards bodies. Even the post-quantum schemes inherit the Lagrange-orbit / Fermat-Euler-Wilson framework as their correctness identity, just with the underlying hard problem replaced.

Bibliography Master

@misc{Fermat1640,
  author = {Fermat, Pierre de},
  title  = {Letter to Bernard Fr\'enicle de Bessy, 18 October 1640},
  year   = {1640},
  note   = {Reproduced in *Œuvres de Fermat*, ed. Tannery and Henry, Vol. II, pp. 209-210 (Paris: Gauthier-Villars, 1894). The first statement of Fermat's little theorem; no proof given.}
}

@article{Euler1736,
  author  = {Euler, Leonhard},
  title   = {Theorematum quorundam ad numeros primos spectantium demonstratio},
  journal = {Commentarii Academiae Scientiarum Imperialis Petropolitanae},
  volume  = {8},
  pages   = {141--146},
  year    = {1736},
  note    = {The first published proof of Fermat's little theorem, by induction on $a$ using $(a + 1)^p \equiv a^p + 1 \pmod p$. Reprinted in *Opera Omnia* Ser. I, Vol. 2, paper E54.}
}

@article{Euler1763,
  author  = {Euler, Leonhard},
  title   = {Theoremata arithmetica nova methodo demonstrata},
  journal = {Novi Commentarii Academiae Scientiarum Imperialis Petropolitanae},
  volume  = {8},
  pages   = {74--104},
  year    = {1763},
  note    = {Introduces the totient function $\varphi(n)$ and proves Euler's generalisation $a^{\varphi(n)} \equiv 1 \pmod n$. Reprinted in *Opera Omnia* Ser. I, Vol. 2, paper E271.}
}

@article{Lagrange1771,
  author  = {Lagrange, Joseph-Louis},
  title   = {D\'emonstration d'un th\'eor\`eme nouveau concernant les nombres premiers},
  journal = {Nouveaux M\'emoires de l'Acad\'emie Royale des Sciences et Belles-Lettres de Berlin},
  volume  = {2},
  pages   = {125--137},
  year    = {1771},
  note    = {The first proof of Wilson's theorem, via the polynomial-identity argument that $(x - 1)(x - 2) \cdots (x - (p - 1)) = x^{p - 1} - 1$ in $\mathbb{F}_p[x]$.}
}

@book{Gauss1801,
  author    = {Gauss, Carl Friedrich},
  title     = {Disquisitiones Arithmeticae},
  publisher = {Gerhard Fleischer},
  address   = {Leipzig},
  year      = {1801},
  note      = {English translation by Arthur A. Clarke, Yale University Press, 1965. Articles 50-83 contain the canonical modern development of Fermat-Euler-Wilson and their generalisations.}
}

@article{Korselt1899,
  author  = {Korselt, Alwin Reinhold},
  title   = {Probl\`eme chinois},
  journal = {L'interm\'ediaire des math\'ematiciens},
  volume  = {6},
  pages   = {142--143},
  year    = {1899},
  note    = {Korselt's criterion for Carmichael numbers.}
}

@article{Carmichael1910,
  author  = {Carmichael, Robert D.},
  title   = {Note on a new number theory function},
  journal = {Bulletin of the American Mathematical Society},
  volume  = {16},
  pages   = {232--238},
  year    = {1910},
  note    = {Introduces the Carmichael function $\lambda(n)$ and supplies the first example of a Carmichael number, $n = 561$.}
}

@article{Miller1976,
  author  = {Miller, Gary L.},
  title   = {Riemann's hypothesis and tests for primality},
  journal = {Journal of Computer and System Sciences},
  volume  = {13},
  pages   = {300--317},
  year    = {1976}
}

@article{Rabin1980,
  author  = {Rabin, Michael O.},
  title   = {Probabilistic algorithm for testing primality},
  journal = {Journal of Number Theory},
  volume  = {12},
  pages   = {128--138},
  year    = {1980}
}

@article{AGP1994,
  author  = {Alford, W. R. and Granville, Andrew and Pomerance, Carl},
  title   = {There are infinitely many Carmichael numbers},
  journal = {Annals of Mathematics},
  volume  = {140},
  pages   = {703--722},
  year    = {1994}
}

@article{AKS2004,
  author  = {Agrawal, Manindra and Kayal, Neeraj and Saxena, Nitin},
  title   = {{PRIMES} is in {P}},
  journal = {Annals of Mathematics},
  volume  = {160},
  pages   = {781--793},
  year    = {2004}
}

@article{RSA1978,
  author  = {Rivest, Ronald L. and Shamir, Adi and Adleman, Leonard},
  title   = {A method for obtaining digital signatures and public-key cryptosystems},
  journal = {Communications of the ACM},
  volume  = {21},
  pages   = {120--126},
  year    = {1978}
}

@book{HardyWright2008,
  author    = {Hardy, G. H. and Wright, E. M.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {6},
  publisher = {Oxford University Press},
  year      = {2008},
  note      = {Revised by D. R. Heath-Brown and J. H. Silverman, foreword by A. Wiles. Chapter VI develops Fermat-Euler-Wilson with multiple proofs.}
}

@book{IrelandRosen1990,
  author    = {Ireland, Kenneth and Rosen, Michael},
  title     = {A Classical Introduction to Modern Number Theory},
  edition   = {2},
  series    = {Graduate Texts in Mathematics},
  volume    = {84},
  publisher = {Springer},
  year      = {1990},
  note      = {§§3.2, 4 develop the group-theoretic framing of Fermat-Euler and Wilson's theorem.}
}

@book{Apostol1976,
  author    = {Apostol, Tom M.},
  title     = {Introduction to Analytic Number Theory},
  series    = {Undergraduate Texts in Mathematics},
  publisher = {Springer},
  year      = {1976},
  note      = {§5 develops the totient function and Fermat-Euler with arithmetic-function methods.}
}

@book{NivenZuckermanMontgomery1991,
  author    = {Niven, Ivan and Zuckerman, Herbert S. and Montgomery, Hugh L.},
  title     = {An Introduction to the Theory of Numbers},
  edition   = {5},
  publisher = {John Wiley},
  year      = {1991},
  note      = {Standard undergraduate development of Fermat-Euler-Wilson.}
}

Prerequisites

21.01.01
21.01.02
21.01.03

Tier anchors

beginner: Burton 2010 *Elementary Number Theory* 7e §5 (Fermat-Euler theorems with worked clock-arithmetic examples); Khan Academy 'Modular exponentiation' module
intermediate: Ireland-Rosen 1990 *A Classical Introduction to Modern Number Theory* (Springer GTM 84, 2e) §§3.2, 4; Apostol 1976 *Introduction to Analytic Number Theory* §5; Niven-Zuckerman-Montgomery 1991 *An Introduction to the Theory of Numbers* 5e §2
master: Fermat 1640 letter to Frénicle de Bessy (originator, no proof); Euler 1736 *Comm. Acad. Sci. Petrop.* 8 (first proof of FLT) and 1763 *Novi Comm. Acad. Sci. Petrop.* 8 (totient version); Lagrange 1771 *Nouv. Mém. Acad. Berlin* 2 (first proof of Wilson); Gauss 1801 *Disquisitiones Arithmeticae* arts. 50-83 (canonical modern formulation); Hardy-Wright 2008 6e §VI; Carmichael 1910 *Bull. AMS* 16; Alford-Granville-Pomerance 1994 *Annals* 140; Agrawal-Kayal-Saxena 2004 *Annals* 160 (PRIMES is in P)

References

Fermat, P. de — Letter to Frénicle de Bessy · Correspondence dated 18 October 1640. Fermat states the now-named little theorem: if $p$ is prime and $a$ is not divisible by $p$, then $p$ divides $a^{p-1} - 1$. He records that he has a proof but withholds it ('je vous envoierois la démonstration, si je n'appréhendois d'être trop long'). Reproduced in Fermat 1894 *Œuvres de Fermat*, ed. Tannery-Henry, Vol. II, pp. 209-210 (Paris: Gauthier-Villars). The first published proof is Euler 1736.
Euler, L. — Theorematum quorundam ad numeros primos spectantium demonstratio · *Commentarii Academiae Scientiarum Petropolitanae* 8 (1736), 141-146. Euler's first proof of Fermat's little theorem, by induction on $a$ using the binomial expansion $(a + 1)^p \equiv a^p + 1 \pmod p$. Reprinted in *Opera Omnia* Ser. I, Vol. 2, paper E54. The induction step requires that $p$ divides every binomial coefficient $\binom{p}{k}$ for $1 \leq k \leq p - 1$ — itself a consequence of the prime hypothesis.
Euler, L. — Theoremata arithmetica nova methodo demonstrata · *Novi Commentarii Academiae Scientiarum Petropolitanae* 8 (1763), 74-104. Euler introduces the totient function $\varphi(n)$ (which he writes $\pi N$, calling it the 'number of numbers less than $N$ which are coprime to $N$') and proves the generalisation $a^{\varphi(n)} \equiv 1 \pmod n$ for $\gcd(a, n) = 1$. Reprinted in *Opera Omnia* Ser. I, Vol. 2, paper E271. The proof uses the modern group-theoretic argument in disguise: a reduced residue system permuted by multiplication-by-$a$ produces the cancellation $a^{\varphi(n)} \prod \equiv \prod$ in $(\mathbb{Z}/n)^\times$.
Lagrange, J.-L. — Démonstration d'un théorème nouveau concernant les nombres premiers · *Nouveaux Mémoires de l'Académie Royale des Sciences et Belles-Lettres de Berlin* 2 (1771), 125-137. The first published proof of Wilson's theorem: $(p-1)! \equiv -1 \pmod p$ for $p$ prime. The theorem had been stated without proof by John Wilson and communicated by Edward Waring in *Meditationes Algebraicae* (1770). Lagrange's proof uses the factorisation argument: the polynomial $(x - 1)(x - 2) \cdots (x - (p-1)) - (x^{p-1} - 1)$ has degree at most $p - 2$ but vanishes at every nonzero residue modulo $p$, forcing all coefficients to be zero — in particular the constant term $(-1)^{p-1}(p-1)! + 1$.
Gauss, C. F. — Disquisitiones Arithmeticae · Leipzig: Gerhard Fleischer, 1801. Articles 50-83 give the canonical modern development of Fermat-Euler-Wilson and their consequences: Articles 50-51 (Fermat's little theorem and Euler's totient generalisation); Articles 52-56 (orders of elements and Lagrange consequences for $(\mathbb{Z}/n)^\times$); Articles 75-78 (Wilson's theorem and the converse-as-primality-test); Articles 79-83 (the generalisation $\prod_{\gcd(a, n) = 1} a \equiv \pm 1 \pmod n$ with the $\pm$ determined by the structure of $(\mathbb{Z}/n)^\times$). English translation by Clarke 1965 (Yale UP).
Carmichael, R. D. — Note on a new number theory function · *Bulletin of the American Mathematical Society* 16 (1910), 232-238. Introduces the Carmichael function $\lambda(n)$ as the exponent of $(\mathbb{Z}/n)^\times$ — the least positive integer such that $a^{\lambda(n)} \equiv 1 \pmod n$ for every $a$ coprime to $n$. Always divides $\varphi(n)$, with equality iff $(\mathbb{Z}/n)^\times$ is cyclic ($n \in \{1, 2, 4, p^e, 2 p^e\}$ for $p$ an odd prime).
Korselt, A. R. — Problème chinois · *L'intermédiaire des mathématiciens* 6 (1899), 142-143. Korselt's criterion: a composite integer $n$ satisfies $a^{n-1} \equiv 1 \pmod n$ for every $a$ coprime to $n$ if and only if $n$ is squarefree and $(p - 1) \mid (n - 1)$ for every prime $p$ dividing $n$. Korselt stated the criterion without producing an example; Carmichael 1910 *Amer. Math. Monthly* 17, 232 supplied the smallest instance $561 = 3 \cdot 11 \cdot 17$. Such composites are now called Carmichael numbers.
Miller, G. L. — Riemann's hypothesis and tests for primality · *Journal of Computer and System Sciences* 13 (1976), 300-317. Miller's deterministic primality test assuming the generalised Riemann hypothesis, based on a strengthening of Fermat's little theorem. Strong pseudoprimes: a composite $n$ with $n - 1 = 2^s d$ ($d$ odd) is a strong pseudoprime to base $a$ if $a^d \equiv 1 \pmod n$ or $a^{2^r d} \equiv -1 \pmod n$ for some $0 \leq r < s$. Rabin 1980 randomised the test to remove the GRH hypothesis.
Rabin, M. O. — Probabilistic algorithm for testing primality · *Journal of Number Theory* 12 (1980), 128-138. Rabin's probabilistic version of Miller's test: if $n$ is composite, at most $1/4$ of bases $a$ in $\{1, \ldots, n - 1\}$ are strong-pseudoprime witnesses, so $k$ random trials reduce the false-positive probability to $4^{-k}$. Polynomial-time on probabilistic Turing machines; the de facto industry primality test for RSA key generation.
Alford, W. R., Granville, A. & Pomerance, C. — There are infinitely many Carmichael numbers · *Annals of Mathematics* 140 (1994), 703-722. The Alford-Granville-Pomerance theorem: there exist infinitely many Carmichael numbers, with the count $C(x)$ of Carmichael numbers up to $x$ satisfying $C(x) > x^{2/7}$ for $x$ sufficiently large. Settled an open question from Carmichael 1912; the proof combines the Erdős 1956 heuristic with Maier-style intervals for primes in arithmetic progressions.
Agrawal, M., Kayal, N. & Saxena, N. — PRIMES is in P · *Annals of Mathematics* 160 (2004), 781-793. The AKS deterministic polynomial-time primality test, settling the long-standing open question of whether primality can be decided in deterministic polynomial time. Based on a polynomial-identity strengthening of Fermat's little theorem: $n$ is prime iff $(x + a)^n \equiv x^n + a \pmod{n, x^r - 1}$ for sufficiently many small $a$ and a carefully chosen $r$. Complexity $\tilde{O}((\log n)^{6})$ in the original paper, improved to $\tilde{O}((\log n)^{6})$ via Lenstra-Pomerance refinements.
Rivest, R. L., Shamir, A. & Adleman, L. — A method for obtaining digital signatures and public-key cryptosystems · *Communications of the ACM* 21 (1978), 120-126. The RSA public-key cryptosystem. The decryption identity $C^d \equiv M \pmod N$ with $N = pq$, $ed \equiv 1 \pmod{\varphi(N)}$ rests on Euler's theorem: $M^{ed} = M^{1 + k\varphi(N)} = M \cdot (M^{\varphi(N)})^k \equiv M \pmod N$ when $\gcd(M, N) = 1$. The corner case $\gcd(M, N) > 1$ is handled by CRT-on-$p$-and-$q$.
Hardy, G. H. & Wright, E. M. — An Introduction to the Theory of Numbers · Oxford University Press, 6th edition (2008), revised by D. R. Heath-Brown and J. H. Silverman. Chapter VI (Fermat's theorem and its consequences): §§6.1-6.6 cover Fermat's little theorem with Euler's proof and three additional proofs (combinatorial via necklaces, group-theoretic via Lagrange, polynomial via $\prod(x - a) = x^{p-1} - 1 \in \mathbb{F}_p[x]$); §§6.7-6.10 cover Wilson's theorem, the converse-primality-test, and the generalisation to arbitrary moduli.
Ireland, K. & Rosen, M. — A Classical Introduction to Modern Number Theory · Springer Graduate Texts in Mathematics 84, 2nd edition (1990), §§3.2, 4. Group-theoretic framing: $(\mathbb{Z}/n)^\times$ is a finite abelian group of order $\varphi(n)$, and Fermat-Euler is Lagrange's theorem applied to it. Wilson's theorem as the calculation $\prod_{g \in G} g$ in a finite abelian group with at most one element of order $2$. The chapter develops primitive roots and the structure of $(\mathbb{Z}/p^k)^\times$ as the natural sequel.

Estimated time

beginner: 18m
intermediate: 40m
master: 80m