Raise each nonzero element of $\mathbb{Z}_{13}$ to the powers $1, 2, \ldots, 12$ and reduce modulo 13. The rows of the resulting table look irregular: the powers of 2 run through every nonzero element, the powers of 3 cycle through only $3, 9, 1$, and those of 12 alternate between 12 and 1. Yet every row ends in the same place. The twelfth power of every nonzero element is 1. Is that a property of 13 alone, and if not, what can it be used for?
The same happens for every prime: if $p$ is prime, then $a^{p-1} = 1$ for every nonzero $a$ in $\mathbb{Z}_p$. This is Fermat's little theorem.
First we prove it: multiplying by a unit rearranges the units. Then we use it on exponents, inverses and orders. Next we extend it to every modulus as Euler's theorem. Finally we turn it into a fast test for compositeness, whose gap, the Carmichael numbers, includes the running example 1729.
The article opens Public-Key Cryptography, whose second article, the RSA cryptosystem, rests on these theorems. It is the home of Fermat's and Euler's theorems and of the order of an element, which later units build on. It assumes the units of $\mathbb{Z}_n$, their inverses and Euler's function $\varphi(n)$, and repeated squaring for computing powers. The course text proves Fermat's theorem as Lemma 13.2 (Hungerford, 2014, Chapter 13). Judson (2026, §6.3) proves both theorems with Lagrange's theorem from group theory. Elements of $\mathbb{Z}_n$ are written without brackets when the modulus is clear.
Powers modulo a prime
The table of powers modulo 13 shows more than its last column.
- Every row is periodic. The powers of 5 are $5, 12, 8, 1$ and then repeat, because once $5^4 = 1$, each further power is 1 times an earlier one: $5^5 = 5^4 \cdot 5 = 5$.
- The periods are 1 (for $a = 1$), 2 (for 12), 3 (for 3 and 9), 4 (for 5 and 8), 6 (for 4 and 10) and 12 (for 2, 6, 7 and 11). Every period divides 12.
- In a row of period 12, the twelve powers are all different and so they are all twelve nonzero elements. Powers of 2 alone produce every nonzero element of $\mathbb{Z}_{13}$.
The same pattern appeared in the article on the integers modulo $n$, where the powers of 2 modulo 5 ran $2, 4, 3, 1$ with period 4, and the exponent of a power could be treated as a class modulo 4 but not modulo 5. Fermat's theorem explains both observations: exponents modulo a prime $p$ behave as classes modulo $p - 1$. Why should the last column be all 1s?
The theorem
Theorem (Fermat's little theorem). Let $p$ be a prime and $a$ an integer with $p \nmid a$. Then
$$a^{p-1} \equiv 1 \pmod p.$$
In the language of $\mathbb{Z}_p$: $a^{p-1} = 1$ for every nonzero element $a$ of $\mathbb{Z}_p$.
The proof rests on one observation about units, which holds in every $\mathbb{Z}_n$ and will be reused for Euler's theorem.
Multiplying by a unit rearranges the units
Recall from Units and Zero Divisors in the Integers Modulo n that $U(n)$ denotes the set of units of $\mathbb{Z}_n$, that a product of units is a unit, and that each unit $u$ has a unique inverse $u^{-1}$.
Lemma. Let $n \ge 2$ and let $u$ be a unit of $\mathbb{Z}_n$. The function $f \colon U(n) \to U(n)$ defined by $f(x) = ux$ is a bijection. Consequently, if $u_1, u_2, \ldots, u_m$ is a list of the units of $\mathbb{Z}_n$, each appearing once, then $uu_1, uu_2, \ldots, uu_m$ is the same list in some order.
Here is the idea. A unit is never a zero divisor, so it can be canceled, and multiplying by $u$ never sends two units to the same place. Then counting finishes the job: $m$ different units in a set of only $m$ units must be all of them.
Proof. If $x$ is a unit, then $ux$ is a product of two units and so a unit; hence $f$ does map $U(n)$ into $U(n)$. It is one-to-one: if $ux = uy$, then $u(x - y) = 0$. A nonzero class of $\mathbb{Z}_n$ is a unit or a zero divisor and never both, so $u$ is not a zero divisor, and therefore $x - y = 0$, that is, $x = y$. It is onto by counting: $U(n)$ is a finite set with $m$ elements, and the one-to-one function $f$ takes $m$ different values in it, which must be all $m$ elements. So $f$ is a bijection. In particular the list $uu_1, \ldots, uu_m$, which consists of the values $f(u_1), \ldots, f(u_m)$, contains every unit exactly once. $\blacksquare$
In $\mathbb{Z}_{11}$, where the units are the ten nonzero elements, multiplying $1, 2, \ldots, 10$ by 5 gives
$$5, \; 10, \; 4, \; 9, \; 3, \; 8, \; 2, \; 7, \; 1, \; 6,$$
which is $1, \ldots, 10$ in a new order. This is the observation, made in the article on units, that the row of a unit in the multiplication table of $\mathbb{Z}_n$ contains every element once.
Proof of Fermat's little theorem
Here is the plan of the proof. Multiply every nonzero element of $\mathbb{Z}_p$ by $a$. The lemma says the result is the same elements in a new order, so the two lists have the same product. One product carries $p - 1$ extra factors of $a$, and canceling the common part leaves $a^{p-1} = 1$.
Proof. Let $p$ be prime and $p \nmid a$. Then the class of $a$ in $\mathbb{Z}_p$ is nonzero, and since $p$ is prime, every nonzero element of $\mathbb{Z}_p$ is a unit (prime moduli). So $U(p) = \{1, 2, \ldots, p - 1\}$, and $a$ is a unit. By the lemma, the elements
$$a \cdot 1, \; a \cdot 2, \; \ldots, \; a \cdot (p - 1)$$
are the elements $1, 2, \ldots, p - 1$ in some order. Two lists with the same entries in different orders have the same product, because multiplication in $\mathbb{Z}_p$ is commutative and associative. Multiply each list out, collecting the $p - 1$ factors of $a$ on the left:
$$a^{p-1} \cdot \bigl(1 \cdot 2 \cdots (p - 1)\bigr) = 1 \cdot 2 \cdots (p - 1).$$
Write $P = 1 \cdot 2 \cdots (p - 1)$, an element of $\mathbb{Z}_p$. It is a product of units, so it is a unit, and multiplying both sides of $a^{p-1} P = P$ by $P^{-1}$ gives $a^{p-1} = 1$ in $\mathbb{Z}_p$. Read as a statement about integers, this says $a^{p-1} \equiv 1 \pmod p$. $\blacksquare$
The proof never needed the value of $P$. Wilson's theorem supplies it, $P = (p - 1)! = -1$. In $\mathbb{Z}_{11}$ with $a = 5$, the two sides of the proof's equation are both $10! = 3{,}628{,}800 \equiv 10 = -1$, while $5^{10} = 9{,}765{,}625 \equiv 1 \pmod{11}$. The course text gives the same rearrangement argument in the language of congruences, canceling the product $P$ with a cancellation lemma for primes (Hungerford, 2014, Lemmas 13.1 and 13.2). The script for this article checks the theorem for every prime below 200 and every $a$ not divisible by it.
Check your understanding. The proof used that $p$ is prime at exactly one point. Where? Then predict whether $2^{20} \equiv 1 \pmod{21}$.
Primality was used only to know that every nonzero element of $\mathbb{Z}_p$ is a unit, so that the lemma applies to the whole list $1, \ldots, p - 1$. In $\mathbb{Z}_{21}$ that fails, since $3, 6, 7, 9, 12, 14, 15, 18$ are zero divisors, and the conclusion fails with it: the script finds $2^{20} \equiv 4 \pmod{21}$.
A form for every integer
The hypothesis $p \nmid a$ cannot be dropped from the statement $a^{p-1} \equiv 1$: if $p \mid a$, then $a^{p-1} \equiv 0$. With one more factor of $a$ there are no exceptions, and that version has a proof of its own, independent of the lemma on units.
Proposition. If $p$ is prime, then $a^p \equiv a \pmod p$ for every integer $a$.
Here is the idea. The statement holds for $a = 0$. Expanding $(a + 1)^p$ by the binomial theorem, every term except $a^p$ and 1 carries a binomial coefficient divisible by $p$, so if the statement holds for $a$ it holds for $a + 1$. It climbs from 0 to every positive integer, and congruence carries it to the negative ones. For $p = 7$ the middle coefficients are $7, 21, 35, 35, 21, 7$, all multiples of 7.
Proof. First, $p$ divides $\binom{p}{k}$ whenever $0 < k < p$. Count the ways to choose a committee of $k$ people from $p$ and then a chair from the committee. Choosing the committee first gives $k\binom{p}{k}$; choosing the chair first, from all $p$ people, and then the other $k - 1$ members from the remaining $p - 1$ gives $p\binom{p-1}{k-1}$. So
$$k\binom{p}{k} = p\binom{p - 1}{k - 1},$$
and $p$ divides $k\binom{p}{k}$. Since $0 < k < p$, the prime $p$ does not divide $k$, and Euclid's lemma gives $p \mid \binom{p}{k}$. For $p = 7$ and $k = 3$ the identity reads $3 \cdot 35 = 105 = 7 \cdot 15$.
Next, induction on $a \ge 0$. For $a = 0$, $0^p = 0$. Suppose $a^p \equiv a \pmod p$. By the binomial theorem,
$$(a + 1)^p = a^p + \sum_{k=1}^{p-1} \binom{p}{k} a^k + 1 \equiv a^p + 1 \equiv a + 1 \pmod p,$$
since every term of the sum is a multiple of $p$. So $a^p \equiv a$ for every $a \ge 0$. Finally, an arbitrary integer $a$ leaves a remainder $r$ with $0 \le r < p$ on division by $p$, so $a \equiv r$, and by the rule for powers of congruences $a^p \equiv r^p \equiv r \equiv a \pmod p$. $\blacksquare$
The proposition also gives Fermat's theorem a second time. If $p \nmid a$, then $a$ is a unit of $\mathbb{Z}_p$, and canceling it from $a \cdot a^{p-1} = a \cdot 1$ leaves $a^{p-1} = 1$. So the two forms say the same thing about units, and the second adds only that 0 is fixed. Euler's first published proof of the theorem also proceeded by induction on $a$ (see the history below). The divisibility of $\binom{p}{k}$ returns in ring homomorphisms, where it makes $a \mapsto a^p$ respect sums.
This is the form the RSA cryptosystem needs, because a message there may be any number at all, including one divisible by $p$. Judson (2026, Theorem 6.3.3) states both forms.
Using the theorem
What does the theorem buy? Smaller exponents, inverses as powers, and a limit on the period of each row.
Reducing exponents
Corollary. Let $p$ be prime, $p \nmid a$, and let $m$ and $m'$ be nonnegative integers with $m \equiv m' \pmod{p - 1}$. Then $a^m \equiv a^{m'} \pmod p$.
Proof. Suppose $m \ge m'$ (otherwise exchange them). Then $m - m' = (p - 1)t$ for an integer $t \ge 0$, and
$$a^m = a^{m'} \bigl(a^{p-1}\bigr)^t \equiv a^{m'} \cdot 1^t = a^{m'} \pmod p. \qquad \blacksquare$$
So modulo a prime $p$, exponents may be reduced modulo $p - 1$. To find $3^{100}$ modulo 13, divide 100 by 12: $100 = 12 \cdot 8 + 4$, so $3^{100} \equiv 3^4 = 81 \equiv 3 \pmod{13}$. This settles the puzzle of the powers of 2 modulo 5: the period there was 4 because $5 - 1 = 4$. The corollary does not say that $p - 1$ is the smallest period; in the table, $3^3$ is already 1 modulo 13, and the true period of a row is the subject of the next section.
The theorem also gives a formula for inverses. If $p \nmid a$, then $a \cdot a^{p-2} = a^{p-1} = 1$ in $\mathbb{Z}_p$, so
$$a^{-1} = a^{p-2} \quad \text{in } \mathbb{Z}_p.$$
In $\mathbb{Z}_{13}$, $5^{-1} = 5^{11}$, which the script reduces to 8; and indeed $5 \cdot 8 = 40 = 3 \cdot 13 + 1$. With repeated squaring this costs about $2 \log_2 p$ multiplications. That is comparable to the extended Euclidean algorithm, which has the advantage of working for every modulus, prime or not.
The order of an element
Definition. Let $n \ge 2$ and let $a$ be a unit of $\mathbb{Z}_n$. The order of $a$ is the smallest positive integer $k$ with $a^k = 1$.
Such a $k$ exists. The powers $a, a^2, a^3, \ldots$ lie in the finite set $\mathbb{Z}_n$, so two of them coincide, say $a^i = a^j$ with $i < j$; multiplying by $(a^{-1})^i$ gives $a^{j-i} = 1$. For a prime modulus, Fermat's theorem gives the exponent $p - 1$ directly.
Proposition. Let $a$ be a unit of $\mathbb{Z}_n$ of order $k$. For an integer $m \ge 0$, $a^m = 1$ if and only if $k \mid m$.
Here is the idea. The powers of $a$ cycle with period $k$, so $a^m$ depends only on the remainder of $m$ on division by $k$, and the only remainder that gives 1 is 0.
Proof. If $m = kt$, then $a^m = (a^k)^t = 1$. Conversely, suppose $a^m = 1$, and divide $m$ by $k$ with the division algorithm: $m = kt + r$ with $0 \le r < k$. Then
$$1 = a^m = (a^k)^t a^r = a^r.$$
Since $r < k$ and $k$ is the smallest positive exponent giving 1, $r$ cannot be positive, so $r = 0$ and $k \mid m$. $\blacksquare$
Corollary. If $p$ is prime and $p \nmid a$, the order of $a$ modulo $p$ divides $p - 1$.
Proof. $a^{p-1} = 1$ by Fermat's theorem, so the order divides $p - 1$ by the proposition. $\blacksquare$
This is why every period in the table divides 12. The orders modulo 13 are
| order | 1 | 2 | 3 | 4 | 6 | 12 |
|---|---|---|---|---|---|---|
| elements | 1 | 12 | 3, 9 | 5, 8 | 4, 10 | 2, 6, 7, 11 |
An element whose order is $p - 1$, such as 2 modulo 13, is called a primitive root modulo $p$: its powers are all the nonzero elements. Every prime has one, a fact usually proved in a course on fields. Judson (2026, Corollary 22.1.11) proves that the nonzero elements of any finite field are the powers of a single element. Primitive roots reappear in the key exchange of Diffie and Hellman.
Square roots of $-1$
The article on Integral Domains and Fields proved that for an odd prime $p$, the equation $x^2 = -1$ has a solution in $\mathbb{Z}_p$ exactly when $p \equiv 1 \pmod 4$, and showed that a square root of $-1$ forces $p \equiv 1 \pmod 4$ by partitioning the nonzero elements into blocks of four. Fermat's theorem gives a two-line proof of that direction.
Proposition. Let $p$ be an odd prime. If $x^2 \equiv -1 \pmod p$ for some integer $x$, then $p \equiv 1 \pmod 4$.
Here is the idea. Raise $x^2 = -1$ to the power $(p - 1)/2$. Fermat's theorem makes the left side 1, so $(-1)^{(p-1)/2}$ must be 1 as well, and that needs an even exponent.
Proof. Here $p \nmid x$, since otherwise $x^2 \equiv 0 \not\equiv -1$. Since $p$ is odd, $(p - 1)/2$ is an integer, and
$$x^{p-1} = \bigl(x^2\bigr)^{(p-1)/2} \equiv (-1)^{(p-1)/2} \pmod p.$$
By Fermat's theorem the left side is congruent to 1. If $(p - 1)/2$ were odd, the right side would be $-1$, giving $1 \equiv -1$, that is, $p \mid 2$, impossible for an odd prime. So $(p - 1)/2$ is even, which says $4 \mid p - 1$. $\blacksquare$
For $p = 13$, $x = 5$ satisfies $5^2 = 25 \equiv -1$, and $5^{12} = (5^2)^6 = (-1)^6 = 1$, as the proof requires. For $p = 7$, 11 and 19, which are $3 \bmod 4$, the script finds no square root of $-1$, and it confirms the full statement for every prime below 1000.
Euler's theorem
For a composite modulus, $a^{n-1} = 1$ usually fails, as $2^{20} \equiv 4 \pmod{21}$ showed. But the rearrangement argument still works if we keep only the units. Here is the idea: run the proof of Fermat's theorem on the list of units alone, which has $\varphi(n)$ entries in place of $p - 1$.
Theorem (Euler). Let $n \ge 2$ and let $a$ be an integer with $\gcd(a, n) = 1$. Then
$$a^{\varphi(n)} \equiv 1 \pmod n,$$
where $\varphi(n)$, Euler's phi function, is the number of integers from 1 to $n$ that are relatively prime to $n$.
Proof. By the theorem on units, the class of $a$ is a unit of $\mathbb{Z}_n$. The units are the classes of the integers from 1 to $n$ relatively prime to $n$, so there are $m = \varphi(n)$ of them; list them as $u_1, \ldots, u_m$. By the lemma, $au_1, \ldots, au_m$ is the same list in another order, so the two lists have the same product:
$$a^{m} \cdot (u_1 u_2 \cdots u_m) = u_1 u_2 \cdots u_m.$$
The product $Q = u_1 \cdots u_m$ is a unit, and multiplying by $Q^{-1}$ gives $a^m = 1$ in $\mathbb{Z}_n$, which is the congruence claimed. $\blacksquare$
When $n = p$ is prime, $\varphi(p) = p - 1$ and Euler's theorem is Fermat's. In $\mathbb{Z}_{21}$ the units are $1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20$, so $\varphi(21) = 12$, and multiplying them by 2 gives
$$2, \; 4, \; 8, \; 10, \; 16, \; 20, \; 1, \; 5, \; 11, \; 13, \; 17, \; 19,$$
the same twelve units rearranged. The theorem predicts $2^{12} \equiv 1 \pmod{21}$, and indeed $2^{12} = 4096 = 21 \cdot 195 + 1$. The hypothesis $\gcd(a, n) = 1$ is necessary: a zero divisor $a$ satisfies $ab = 0$ for some nonzero $b$, so $a^k = 1$ would give $b = a^k b = a^{k-1}(ab) = 0$, and no power of a zero divisor is ever 1.
Euler published the generalization in 1763 (Euler, E271). The proof via group theory is short once Lagrange's theorem is available. $U(n)$ is a group with $\varphi(n)$ elements, and the order of an element of a finite group divides the number of elements (Judson, 2026, Theorems 6.3.1 and 6.3.2; see Lagrange's theorem).
Check your understanding. Euler's theorem gives $a^{12} = 1$ for every unit of $\mathbb{Z}_{21}$, so the order of a unit divides 12. Could a unit of $\mathbb{Z}_{21}$ have order 4?
None does, though 4 divides 12. Every unit reaches 1 by the sixth power, so every order divides 6; the script finds only 1, 2, 3 and 6. Euler's exponent is a guarantee, not always the smallest one.
Combining congruences for relatively prime moduli
Why does every unit of $\mathbb{Z}_{21}$ satisfy $a^6 = 1$, half of Euler's exponent? The reason is that 21 splits into 3 and 7, and congruences modulo relatively prime numbers can be checked separately.
Lemma. Let $m$ and $k$ be relatively prime integers. If $m \mid c$ and $k \mid c$, then $mk \mid c$. Consequently, for all integers $a$ and $b$,
$$a \equiv b \pmod{mk} \quad \Longleftrightarrow \quad a \equiv b \pmod m \text{ and } a \equiv b \pmod k.$$
Here is the idea. Bezout's identity writes 1 as a combination of $m$ and $k$. Multiplying it by $c$ writes $c$ as a sum of two terms, each of which visibly contains both $m$ and $k$.
Proof. Since $\gcd(m, k) = 1$, Bezout's identity gives integers $x$ and $y$ with $mx + ky = 1$. Multiplying by $c$,
$$c = c\,mx + c\,ky.$$
Write $c = ks$ and $c = mt$, which is possible because $k \mid c$ and $m \mid c$, and substitute the first into the first term and the second into the second term: $c = ks \cdot mx + mt \cdot ky = mk(sx + ty)$. So $mk \mid c$. The equivalence is the case $c = a - b$: if $mk \mid a - b$, then $m$ and $k$, being divisors of $mk$, divide $a - b$, and the converse is what was just proved. $\blacksquare$
For example, with $m = 4$ and $k = 9$, Bezout's identity reads $4 \cdot (-2) + 9 \cdot 1 = 1$. Any $c$ divisible by both 4 and 9 then splits as $c = -8c + 9c$, and both $-8c$ and $9c$ are multiples of 36.
Distinct primes are relatively prime, so the lemma applies to them, and by induction it extends to any number of pairwise relatively prime moduli: if $p_1, \ldots, p_r$ are distinct primes each dividing $c$, then $p_1 \cdots p_r$ divides $c$, since $p_1 \cdots p_{r-1}$ and $p_r$ are relatively prime.
Back to $\mathbb{Z}_{21}$. For a unit $a$, $\gcd(a, 21) = 1$, so neither 3 nor 7 divides $a$. By Fermat, $a^2 \equiv 1 \pmod 3$ and $a^6 \equiv 1 \pmod 7$. Raising the first to the third power gives $a^6 \equiv 1$ modulo both 3 and 7, and the lemma gives $a^6 \equiv 1 \pmod{21}$. In general the exponent $\operatorname{lcm}(p - 1, q - 1)$ works modulo a product $pq$ of distinct primes. The original RSA paper notes it as an alternative to $(p - 1)(q - 1)$ (Rivest, Shamir and Adleman, 1978, §IX-C).
The same reasoning explains a number met in the article on modular arithmetic: the powers of 3 modulo $1001 = 7 \cdot 11 \cdot 13$ repeat with period 30. The orders of 3 modulo 7, 11 and 13 are 6, 5 and 3. By the lemma and the proposition on orders, $3^m \equiv 1 \pmod{1001}$ exactly when $3^m \equiv 1$ modulo each of 7, 11 and 13. That happens when 6, 5 and 3 all divide $m$, that is, when $\operatorname{lcm}(6, 5, 3) = 30$ divides $m$. Euler's theorem guarantees only the exponent $\varphi(1001) = 720$, which is a multiple of 30, as it must be.
The phi function of a product of two primes
RSA needs the number of units of $\mathbb{Z}_{pq}$.
Proposition. If $p$ and $q$ are distinct primes, then $\varphi(pq) = (p - 1)(q - 1)$.
Here is the idea. Count the complement: the numbers that share a factor with $pq$ are the multiples of $p$ and the multiples of $q$, and the two lists overlap only in $pq$ itself.
Proof. Count the integers $a$ from 1 to $pq$ with $\gcd(a, pq) > 1$. Such a common divisor greater than 1 has a prime factor, which divides $pq$ and so, by Euclid's lemma, is $p$ or $q$. So these are the integers in the range divisible by $p$ or by $q$. The multiples of $p$ are $p, 2p, \ldots, qp$, which is $q$ numbers, and the multiples of $q$ are $p$ numbers. An integer divisible by both is divisible by $pq$ by the lemma, which leaves only $pq$ itself, counted twice. So $p + q - 1$ integers share a factor with $pq$, and
$$\varphi(pq) = pq - p - q + 1 = (p - 1)(q - 1). \qquad \blacksquare$$
For example $\varphi(21) = 2 \cdot 6 = 12$, and for the primes 43 and 71 used in the RSA article, $\varphi(3053) = 42 \cdot 70 = 2940$. More generally $\varphi(mk) = \varphi(m)\varphi(k)$ whenever $\gcd(m, k) = 1$, which is a consequence of the Chinese remainder theorem; it gives $\varphi(1001) = 6 \cdot 10 \cdot 12 = 720$.
A test for primality
The theorems so far describe numbers we already know to be prime. Can Fermat's theorem tell us whether a number is prime in the first place? Its contrapositive says something about composites: if $1 \le a < n$ and
$$a^{n-1} \not\equiv 1 \pmod n,$$
then $n$ is not prime. The test proves that $n$ is composite without producing a factor.
Take the running number $n = 1001$ and $a = 2$. Repeated squaring computes $2^{1000} \bmod 1001$ with nine squarings and five further multiplications, since $1000 = 512 + 256 + 128 + 64 + 32 + 8$. The script finds $2^{1000} \equiv 562 \pmod{1001}$. Since $562 \neq 1$, 1001 is composite. The factor 7 accounts for the failure: 2 has order 3 modulo 7, and $1000 = 3 \cdot 333 + 1$, so $2^{1000} \equiv 2 \pmod 7$, not 1. For $n = 1013$, which trial division showed to be prime, $2^{1012} \equiv 1 \pmod{1013}$, as the theorem requires.
Check your understanding. The orders of 2 modulo 7, 11 and 13 are 3, 10 and 12. Which of these primes divide $2^{1000} - 1$?
Only 11, since of 3, 10 and 12 only 10 divides 1000 (the proposition on orders). So $562 \equiv 1 \pmod{11}$, and the script confirms $\gcd(562 - 1, 1001) = 11$. Here the failed test happens to expose a factor. The test does not promise one; it shows only that some prime factor misbehaves.
The cost is the point. Trial division needs up to $\sqrt{n}$ divisions, which for a number of 300 digits is about $10^{150}$. The Fermat test needs about $\log_2 n$ squarings, roughly a thousand for the same number. This is what makes it possible to find the large primes that the RSA cryptosystem needs.
Pseudoprimes
A composite number can pass the test. An odd composite $n$ with $2^{n-1} \equiv 1 \pmod n$ is called a pseudoprime to the base 2. The script finds 22 of them below 10,000, against 1,229 primes; the smallest is $341 = 11 \cdot 31$, and the next are 561, 645, 1105 and 1387. A second base often exposes them: $3^{340} \equiv 56 \pmod{341}$, so 341 fails the test to the base 3. One might hope that trying a few bases always catches a composite. It does not.
Carmichael numbers
Definition. A Carmichael number is a composite integer $n$ such that $a^{n-1} \equiv 1 \pmod n$ for every integer $a$ with $\gcd(a, n) = 1$.
A Carmichael number passes the Fermat test for every base that does not share a factor with it, and finding such a base is as hard as finding a factor. The number 1729 from the first unit is one. The following criterion shows why.
Proposition (Korselt's criterion, one direction). Let $n = p_1 p_2 \cdots p_r$ be a product of $r \ge 2$ distinct primes, and suppose that $p_i - 1$ divides $n - 1$ for each $i$. Then $n$ is a Carmichael number.
Here is the idea. Modulo each prime factor $p_i$, Fermat's theorem makes $a^{p_i - 1} = 1$, and since $p_i - 1$ divides $n - 1$, also $a^{n-1} = 1$. The lemma on relatively prime moduli then combines the primes.
Proof. $n$ is composite since $r \ge 2$. Let $\gcd(a, n) = 1$. For each $i$, $p_i \nmid a$, since otherwise $p_i$ would be a common divisor of $a$ and $n$. Write $n - 1 = (p_i - 1)t_i$ with $t_i$ a positive integer. By Fermat's theorem,
$$a^{n-1} = \bigl(a^{p_i - 1}\bigr)^{t_i} \equiv 1 \pmod{p_i}.$$
So each of the distinct primes $p_1, \ldots, p_r$ divides $a^{n-1} - 1$, and by the lemma on relatively prime moduli their product $n$ divides it. $\blacksquare$
For $1729 = 7 \cdot 13 \cdot 19$, the numbers $p - 1$ are 6, 12 and 18, and
$$1728 = 6 \cdot 288 = 12 \cdot 144 = 18 \cdot 96.$$
So every base relatively prime to 1729 passes the Fermat test. That is 1,296 of the 1,728 bases from 1 to 1728 (the units, $\varphi(1729) = 6 \cdot 12 \cdot 18$); the other 432 are the bases sharing a factor with 1729. The smallest Carmichael number is $561 = 3 \cdot 11 \cdot 17$, with $560 = 2 \cdot 280 = 10 \cdot 56 = 16 \cdot 35$. By contrast $1001 = 7 \cdot 11 \cdot 13$ fails the criterion, since 6 does not divide 1000, and the base 2 exposed it above. The converse also holds: every Carmichael number is a product of at least three distinct primes satisfying the divisibility condition. The criterion is due to Korselt (1899), and the numbers carry the name of Carmichael (1910); the smallest is 561 (Judson, 2026, §7.5). The script finds the Carmichael numbers below 20,000 by brute force,
$$561, \; 1105, \; 1729, \; 2465, \; 2821, \; 6601, \; 8911, \; 10585, \; 15841,$$
and confirms that they are exactly the numbers meeting Korselt's condition in that range. Counting with the condition, there are 1, 7, 16 and 43 below $10^3$, $10^4$, $10^5$ and $10^6$. They are rare, but there are infinitely many, as Alford, Granville and Pomerance proved (Judson, 2026, §7.5, records the result).
The strong test
Can the test be repaired, or do Carmichael numbers defeat every test of this kind? The Fermat test checks only the last step of a calculation that carries more information. If $p$ is an odd prime, then $\mathbb{Z}_p$ has no zero divisors, so the only square roots of 1 in it are $1$ and $-1$: $x^2 = 1$ means $(x - 1)(x + 1) = 0$, and one factor must be 0. This is the step used in the proof of Wilson's theorem, and the integers modulo 24 showed how it fails for a composite modulus.
Proposition. Let $p$ be an odd prime, write $p - 1 = 2^s t$ with $t$ odd, and let $p \nmid a$. Then either $a^t \equiv 1 \pmod p$, or $a^{2^j t} \equiv -1 \pmod p$ for some $j$ with $0 \le j < s$.
Here is the idea. Squaring $a^t$ repeatedly reaches $a^{p-1} = 1$, and the term just before the first 1 is a square root of 1 other than 1, so it is $-1$.
Proof. Consider the sequence $a^t, a^{2t}, a^{4t}, \ldots, a^{2^s t}$ in $\mathbb{Z}_p$, in which each term is the square of the one before. Its last term is $a^{p-1} = 1$ by Fermat's theorem. Let $a^{2^j t}$ be the first term equal to 1. If $j = 0$, then $a^t = 1$. Otherwise the term $x = a^{2^{j-1} t}$ before it satisfies $x^2 = 1$ and $x \neq 1$, so $x = -1$, with $0 \le j - 1 < s$. $\blacksquare$
An odd number $n$ for which this conclusion fails for some base $a$ between 1 and $n - 1$ is certainly composite, and the failure usually exhibits a square root of 1 other than $\pm 1$. For $n = 561$, write $560 = 2^4 \cdot 35$. With $a = 2$, the script computes
$$2^{35} \equiv 263, \quad 263^2 \equiv 166, \quad 166^2 \equiv 67, \quad 67^2 \equiv 1 \pmod{561}.$$
The first 1 is preceded by 67, not by $-1 = 560$. So 561 is composite, even though it passes the Fermat test for every base relatively prime to it. The witness 67 does more. $67^2 - 1 = 66 \cdot 68$ is divisible by 561 while neither factor is, and $\gcd(66, 561) = 33$ and $\gcd(68, 561) = 17$ are proper factors.
Back to the running number. For 1729, with $1728 = 2^6 \cdot 27$, the base 2 gives $2^{27} \equiv 645$, then $645^2 \equiv 1065$ and $1065^2 \equiv 1$. The square root 1065 of 1 gives $\gcd(1064, 1729) = 133 = 7 \cdot 19$ and $\gcd(1066, 1729) = 13$. The strong test catches 1729 at the first base. For the prime 1013, $1012 = 2^2 \cdot 253$, and the sequence $2^{253} \equiv 45$, $45^2 \equiv 1012 = -1$, then 1, is exactly as the proposition requires.
Unlike the Fermat test, the strong test has no Carmichael numbers to fear. Among the 1,728 bases for 1729, only 162 pass it, and for 561 only 10 of 560. The script finds that no odd composite below 5,000 passes for more than a quarter of the bases (the maximum, exactly one quarter, is at $n = 9$). The bound holds for every odd composite, a theorem proved independently by Rabin (1980) and by Monier (1980) (Conrad, n.d., Theorem 2.9 and §5). Repeating the test with independently chosen random bases therefore makes an error astronomically unlikely.
The Miller–Rabin test built on this proposition is the test the U.S. federal digital signature standard prescribes for generating RSA primes (NIST, 2023, Appendix B.3). It is named for Rabin, who devised it, and for Miller, on whose ideas it draws. The original RSA paper recommended a different probabilistic test of the same kind, due to Solovay and Strassen (Rivest, Shamir and Adleman, 1978, §VII-B).
History
The theorem is named for Pierre de Fermat, who stated it in the seventeenth century without publishing a proof. The first published proof is Euler's, written in 1736 and printed in 1741, which proceeds by induction on $a$ (Euler, E54). Euler returned to the theorem several times, and a paper printed in 1763 counted the residues relatively prime to a modulus, the number now written $\varphi(n)$, and proved the general theorem for any modulus (Euler, E271). The rearrangement proof given here is the one usually taught today, in the course text and elsewhere. More than three centuries after Fermat, the theorem became the mathematical core of public-key cryptography.
Where it leads
- The RSA cryptosystem encrypts and decrypts by powers modulo $n = pq$; $a^p \equiv a$ modulo $p$ and $q$, combined by the lemma on relatively prime moduli, proves that decryption recovers every message.
- Lagrange's theorem proves that the order of an element divides the order of a finite group, with Euler's theorem as the case $U(n)$.
- The Chinese remainder theorem turns the lemma on relatively prime moduli into $\mathbb{Z}_{mk} \cong \mathbb{Z}_m \times \mathbb{Z}_k$, from which $\varphi(mk) = \varphi(m)\varphi(k)$ follows.
- In a finite field with $q$ elements, the same rearrangement argument gives $a^{q-1} = 1$ for every nonzero $a$; the finite fields built from irreducible polynomials are the setting.
What we have learned
The last column modulo 13 is no accident. Multiplying by a unit rearranges the units, which gives $a^{p-1} = 1$ modulo a prime and $a^{\varphi(n)} = 1$ for every unit modulo $n$. Exponents reduce, inverses are powers, and orders divide $p - 1$. Read backwards, the theorem tests for compositeness: 1001 fails at once, while the Carmichael number 1729 passes until the strong test exposes it.
Raising to the thirteenth power modulo $3053 = 43 \cdot 71$ rearranges the numbers from 0 to 3052. Which power undoes it, and why do the two primes make that power easy to find? The next article, The RSA Cryptosystem, answers both.
References
- Carmichael, R. D. (1910). Note on a new number theory function. Bulletin of the American Mathematical Society, 16(5), 232–238. Cited for attribution only: the paper for which the numbers are named. record
- Conrad, K. (n.d.). The Miller–Rabin test. Expository note, University of Connecticut, kconrad.math.uconn.edu. Theorem 2.9, proved in §5: for an odd composite $n$, fewer than a quarter of the integers from 2 to $n - 2$ are nonwitnesses (bases passing the strong test), due independently to Monier and to Rabin. record
- Euler, L. (1741). Theorematum quorundam ad numeros primos spectantium demonstratio (E54, written 1736). Commentarii academiae scientiarum Petropolitanae, 8, 141–146. The Euler Archive's record describes it as the first proof of Fermat's little theorem, by induction on $a$; cited from that record. record
- Euler, L. (1763). Theoremata arithmetica nova methodo demonstrata (E271, written 1758). Novi Commentarii academiae scientiarum Petropolitanae, 8, 74–104. Cited from the Euler Archive's record: the generalization to any modulus, with the count of residues prime to $N$. record
- Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), Chapter 13. Brooks/Cole, Cengage Learning. The course text: a cancellation lemma for primes (Lemma 13.1) and Fermat's little theorem (Lemma 13.2), proved by the rearrangement argument in the language of congruences. record · 44 pages
- Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026). Free online at judsonbooks.org. §6.3: $\lvert U(n) \rvert = \varphi(n)$ (Theorem 6.3.1), Euler's theorem (Theorem 6.3.2) and Fermat's little theorem in both forms (Theorem 6.3.3), proved with Lagrange's theorem; §7.5: pseudoprimes, Carmichael numbers, 561 as the smallest, and the theorem of Alford, Granville and Pomerance that there are infinitely many; Corollary 22.1.11: the multiplicative group of a finite field is cyclic. record · 44 pages
- Korselt, A. (1899). Problème chinois. L'Intermédiaire des mathématiciens, 6, 142–143. Cited for priority only: the criterion for Carmichael numbers. record
- Monier, L. (1980). Evaluation and comparison of two efficient probabilistic primality testing algorithms. Theoretical Computer Science, 12, 97–108. Cited for attribution only, through Conrad (n.d.). record
- National Institute of Standards and Technology (2023). Digital Signature Standard (DSS), FIPS 186-5. Appendix B.3: the Miller–Rabin probabilistic primality test, "due to M.O. Rabin, based in part on ideas from Gary L. Miller", is required when generating the primes of an RSA key. record · 2 pages
- Rabin, M. O. (1980). Probabilistic algorithm for testing primality. Journal of Number Theory, 12(1), 128–138. Cited for attribution only, through Conrad (n.d.): the bound of one quarter on the proportion of bases that an odd composite passes. record
- Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120–126. §VII-B recommends the Solovay–Strassen probabilistic test for finding primes; §IX-C notes that $\varphi(n)$ may be replaced by $\operatorname{lcm}(p - 1, q - 1)$. record · 3 pages