Congruences and Fermat's Little Theorem: Computing in a World of Remainders

0. Key points

• Sorting the integers by “the remainder on division by $n$” carries addition, subtraction, and multiplication along unchanged. This is the congruence $a \equiv b \pmod n$, and the quotient set $\mathbb{Z}/n\mathbb{Z}$ becomes a commutative ring.
• Division, by contrast, is not always available. The class $[a]$ has an inverse in $\mathbb{Z}/n\mathbb{Z}$ exactly when $\gcd(a,n)=1$, and the sole reason for this is Bézout’s identity.
• When $n$ is a prime $p$, the ring $\mathbb{Z}/p\mathbb{Z}$ is a field: every nonzero element is invertible. Fermat’s little theorem $a^{p-1} \equiv 1 \pmod p$ (for $p \nmid a$) follows from this.
• The extension to general $n$ is Euler’s theorem $a^{\varphi(n)} \equiv 1 \pmod n$, whose proof has exactly the same skeleton as Fermat’s: multiplication by $a$ is a permutation of the group of units.
• The Chinese remainder theorem is the isomorphism $\mathbb{Z}/mn\mathbb{Z} \cong \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}$ (for $\gcd(m,n)=1$), and it supports both the multiplicativity of $\varphi$ and the correctness of RSA.
• The converse of Fermat’s little theorem is false. Carmichael numbers such as $561$ are counterexamples, and it is they that pushed primality testing towards probabilistic algorithms.

1. Motivation — arithmetic on a clock face

Suppose it is $7$ o’clock; what time will it be $8$ hours from now? We compute $7+8=15$, but there is no $15$ on a clock face, so we answer $3$ o’clock. In everyday life we are already adding inside the world of “remainders on division by $12$“.

Addition modulo 12. Advancing 8 from 7 brings us back to 3.

This way of computing with remainders alone had been used piecemeal for a long time. Casting out nines, which detects multiples of $9$ from the sum of the digits, was a medieval merchant’s device for checking arithmetic, and calendar computations are in essence computations with remainders. But it was Gauss, in the Disquisitiones Arithmeticae (1801), who systematized the practice with the symbol $\equiv$ and treated it as an algebraic system in its own right. With this single piece of notation Gauss unified techniques of number theory that had until then been scattered.

Why should merely introducing a symbol produce progress? Because congruences obey almost the same rules as equalities. “One may add the same thing to both sides” and “one may multiply both sides by the same thing” both hold, so our instincts for manipulating equations carry over intact. As a result a problem such as finding the last two digits of $2^{100}$ — a computation with a $31$-digit number if carried out honestly — turns into a handful of multiplications of numbers below $100$.

There is, however, one decisive difference from equality: division is not free. We have $2 \times 3 \equiv 2 \times 9 \pmod{12}$ while $3 \not\equiv 9 \pmod{12}$. Pinning down exactly where the boundary between “divisible” and “not divisible” lies is the technical heart of this article, and from it flow both Fermat’s little theorem and RSA.

This article is the sequel to The charm of primes — the prime number theorem. Think of it as looking at primes from the side of “how they behave” rather than “how many there are”.

2. Preliminaries — the division algorithm and Bézout’s identity

Throughout, $\mathbb{Z}$ denotes the integers and $\mathbb{N} = \{1,2,3,\ldots\}$ (excluding $0$). We write $a \mid b$ for ”$a$ divides $b$”, that is, for the existence of some $c \in \mathbb{Z}$ with $b = ac$.

Theorem 2.1（Division algorithm）

Let $a \in \mathbb{Z}$ and $n \in \mathbb{N}$. Then there is exactly one pair of integers $q, r$ with

$$a = qn + r, \qquad 0 \le r < n .$$

Proof（Theorem 2.1）

We first prove existence. Consider the set $S = \{a - qn \mid q \in \mathbb{Z}\} \cap \mathbb{Z}_{\ge 0}$. Taking $q$ to be a sufficiently small negative integer (for instance $q = -|a|$) gives $a - qn = a + |a|n \ge a + |a| \ge 0$, so $S \ne \varnothing$. Being a nonempty set of nonnegative integers, $S$ has a least element $r = a - qn$ by well-ordering（Axiom 3.1）［Techniques of Proof］.

If $r \ge n$, then $r - n = a - (q+1)n$ is again nonnegative and lies in $S$, while $r - n < r$, contradicting the minimality of $r$. Hence $0 \le r < n$.

Now uniqueness. Suppose $a = qn + r = q'n + r'$ with $0 \le r, r' < n$. Then $(q - q')n = r' - r$. The right-hand side satisfies $|r' - r| < n$, so $|q - q'| \cdot n < n$, hence $|q - q'| < 1$, that is, $q = q'$. Substituting back gives $r = r'$.

∎

We write this $r$ as $a \bmod n$. This is the meaning of $\bmod$ when it is used as “the operation of taking the remainder” (the $\pmod n$ that appears later is a parenthetical indicating a relation, and plays a different role).

When $a$ and $b$ are not both $0$, we write $\gcd(a,b)$ for the largest common divisor of $a$ and $b$. When $\gcd(a,b)=1$ we say that $a$ and $b$ are coprime (the notation agrees with Definition 2.1［Primes and the Prime Number Theorem］).

Theorem 2.2（Bézout's identity）

Let $a, b$ be integers, not both $0$. Then there exist integers $x, y$ with

$$ax + by = \gcd(a,b) .$$

Moreover, $\{ax+by \mid x,y \in \mathbb{Z}\}$ coincides with the set of all multiples of $\gcd(a,b)$.

Proof（Theorem 2.2）

Put $I = \{ax + by \mid x, y \in \mathbb{Z}\}$ and let $I^{+}$ be the set of positive integers in $I$. If $a \ne 0$ then $a \cdot a + b \cdot 0 = a^2 > 0$ lies in $I^{+}$; if $a = 0$ then $b \ne 0$, so $b^2 \in I^{+}$. Either way $I^{+} \ne \varnothing$, so by well-ordering it has a least element $d = ax_0 + by_0 > 0$.

We first show $d \mid a$. By Theorem 2.1 write $a = qd + r$ with $0 \le r < d$; then

$$r = a - qd = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0) \in I .$$

If $r > 0$ then $r \in I^{+}$ and $r < d$, contradicting the minimality of $d$. Hence $r = 0$, that is, $d \mid a$. The same argument gives $d \mid b$, so $d$ is a common divisor of $a$ and $b$.

Conversely, let $c$ be any common divisor of $a$ and $b$. Both terms on the right of $d = ax_0 + by_0$ are divisible by $c$, so $c \mid d$ and therefore $c \le d$. Hence $d = \gcd(a,b)$, and $d = ax_0 + by_0$ is the representation sought.

The last assertion follows because every element $ax+by$ of $I$ is a multiple of $d$ (since $d \mid a$ and $d \mid b$), while conversely every multiple $kd = a(kx_0) + b(ky_0)$ of $d$ lies in $I$.

∎

Lemma 2.3（Euclid's lemma）

If $\gcd(c,n) = 1$ and $n \mid cm$, then $n \mid m$. In particular, if $p$ is prime and $p \mid ab$, then $p \mid a$ or $p \mid b$.

Proof（Lemma 2.3）

By Theorem 2.2 there are integers $x, y$ with $cx + ny = 1$. Multiplying both sides by $m$ gives

$$m = (cm)x + n(my) .$$

By hypothesis $n \mid cm$, so the first term on the right is divisible by $n$, and the second term is plainly a multiple of $n$. Hence $n \mid m$.

For the second statement, suppose $p \nmid a$. Since $p$ is prime, $\gcd(p,a)$ is either $1$ or $p$, and $p$ is excluded, so $\gcd(p,a)=1$. Applying the first part with $c = a$, $n = p$, $m = b$ yields $p \mid b$.

∎

3. Congruences

Definition 3.1（Congruence）

Let $n \in \mathbb{N}$. For integers $a, b$, if $n \mid (a - b)$ we say that $a$ and $b$ are congruent modulo $n$ and write

$$a \equiv b \pmod n .$$

We call $n$ the modulus of the congruence.

Proposition 3.2

Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$, and it has exactly $n$ equivalence classes, namely the sets of integers congruent to each of $0, 1, \ldots, n-1$.

Proof（Proposition 3.2）

Reflexivity holds because $n \mid 0 = a - a$. Symmetry follows because if $n \mid (a-b)$ then $b - a = -(a-b)$ is also a multiple of $n$. For transitivity, if $a - b = nk$ and $b - c = nl$ then $a - c = n(k+l)$.

Now we count the classes. By Theorem 2.1 every $a$ can be written $a = qn + r$ with $0 \le r < n$, so $a - r = qn$, that is, $a \equiv r \pmod n$. Hence each class contains one of $0,\ldots,n-1$. Moreover if $0 \le r < r' < n$ then $0 < r' - r < n$, so $n \nmid (r' - r)$ and $r$ is not congruent to $r'$. Therefore there are exactly $n$ classes.

∎

For equivalence relations in general, see Relations and equivalence relations — what does “the same” mean? (the first half of the proposition above is Proposition 3.4［関係と同値関係］). We write $[a]$ or $[a]_n$ for the class containing $a$ and call it the residue class of $a$.

Proposition 3.3（Arithmetic of congruences）

Suppose $a \equiv b \pmod n$ and $c \equiv d \pmod n$. Then

$$a + c \equiv b + d, \qquad a - c \equiv b - d, \qquad ac \equiv bd \pmod n .$$

In particular $a^k \equiv b^k \pmod n$ for every $k \in \mathbb{N}$.

Proof（Proposition 3.3）

By hypothesis there are integers $s,t$ with $a - b = ns$ and $c - d = nt$. For addition,

$$(a+c) - (b+d) = (a-b) + (c-d) = n(s+t)$$

is divisible by $n$. Subtraction is identical up to a change of sign. For multiplication,

$$ac - bd = ac - bc + bc - bd = c(a-b) + b(c-d) = n(cs + bt) ,$$

so $n \mid (ac - bd)$. Here we used the device of adding and subtracting $bc$.

The statement about powers is proved by induction on $k$. The case $k=1$ is the hypothesis itself. If $a^k \equiv b^k$, applying the multiplicative statement to this and to $a \equiv b$ gives $a^{k+1} \equiv b^{k+1}$.

∎

It is Proposition 3.3 that licenses us to treat congruences like equations. Thanks to it, enormous powers can be tracked using remainders alone.

Example 3.4（The last two digits of 2 to the 100th power）

We compute $2^{100} \bmod 100$. We have $2^{10} = 1024 \equiv 24 \pmod{100}$. Squaring both sides using Proposition 3.3,

$$2^{20} \equiv 24^2 = 576 \equiv 76 \pmod{100}.$$

Furthermore $76^2 = 5776 \equiv 76 \pmod{100}$, so $2^{40} \equiv 76$ and $2^{80} \equiv 76$. Therefore

$$2^{100} = 2^{80} \cdot 2^{20} \equiv 76 \cdot 76 = 5776 \equiv 76 \pmod{100}.$$

The number $2^{100}$ has $31$ digits, yet we found its last two digits to be $76$ without ever multiplying numbers of more than three digits.

Example 3.5（Casting out nines and the test for 11）

Since $10 \equiv 1 \pmod 9$, Proposition 3.3 gives $10^k \equiv 1 \pmod 9$. Hence for $N = \sum_{k} d_k 10^k$ (where the $d_k$ are the digits),

$$N \equiv \sum_k d_k \pmod 9 .$$

This proves that multiples of $9$ can be detected from the digit sum. For example, if $N = 987654$ then $9+8+7+6+5+4 = 39 \equiv 3+9 = 12 \equiv 3 \pmod 9$, so $N \equiv 3 \pmod 9$.

On the other hand $10 \equiv -1 \pmod{11}$, so $10^k \equiv (-1)^k$ and

$$N \equiv \sum_k (-1)^k d_k \pmod{11} .$$

For $987654$, attaching alternating signs starting from the units digit gives $4 - 5 + 6 - 7 + 8 - 9 = -3 \equiv 8 \pmod{11}$.

Division alone is a different matter. The next proposition is the precise rule for “dividing both sides” of a congruence.

Proposition 3.6（Cancellation law）

Let $n \in \mathbb{N}$, $c \in \mathbb{Z}$, and $d = \gcd(c,n)$. Then

$$ca \equiv cb \pmod n \iff a \equiv b \pmod{n/d} .$$

In particular, one may conclude $a \equiv b \pmod n$ from $ca \equiv cb \pmod n$ precisely when $\gcd(c,n)=1$.

Proof（Proposition 3.6）

Write $c = dc'$ and $n = dn'$; then $\gcd(c', n') = 1$ (if $e > 1$ were a common divisor of the two, then $de$ would be a common divisor of $c$ and $n$, contradicting the maximality of $d$).

$(\Rightarrow)$ The congruence $ca \equiv cb \pmod n$ says $n \mid c(a-b)$, that is, $dn' \mid dc'(a-b)$; dividing both sides by $d$ gives $n' \mid c'(a-b)$. Since $\gcd(c',n')=1$, Lemma 2.3 yields $n' \mid (a-b)$, that is, $a \equiv b \pmod{n'}$.

$(\Leftarrow)$ If $n' \mid (a-b)$ then $n = dn' \mid dc'(a-b) = c(a-b)$, so $ca \equiv cb \pmod n$.

∎

Example 3.7（An example where division breaks down）

We have $2 \cdot 3 = 6$ and $2 \cdot 9 = 18$, and $18 - 6 = 12$, so $2 \cdot 3 \equiv 2 \cdot 9 \pmod{12}$. But $9 - 3 = 6$ is not a multiple of $12$, so $3 \not\equiv 9 \pmod{12}$. As Proposition 3.6 says, here $d = \gcd(2,12) = 2$, so the most one may correctly conclude is $3 \equiv 9 \pmod 6$ — and indeed $9 - 3 = 6$ satisfies this.

4. The ring Z/nZ and its group of units

Definition 4.1（Ring of residue classes）

Let $n \in \mathbb{N}$. We write

$$\mathbb{Z}/n\mathbb{Z} = \{[0], [1], \ldots, [n-1]\}$$

for the set of all residue classes modulo $n$, with operations defined by

$$[a] + [b] := [a+b], \qquad [a] \cdot [b] := [ab] .$$

There is something to be verified in this definition. The symbol $[a]$ denotes an equivalence class, and there is freedom in the choice of the representative $a$. Unless $[a+b] = [a'+b']$ and $[ab] = [a'b']$ whenever $[a] = [a']$ and $[b] = [b']$, the operations are not well defined. But this is precisely the content of Proposition 3.3. Hence the operations are independent of the choice of representatives (the same statement phrased in the language of quotient sets is Theorem 5.4［関係と同値関係］).

Proposition 4.2

With the operations of Definition 4.1, the set $\mathbb{Z}/n\mathbb{Z}$ is a commutative ring with identity $[1]$.

Proof（Proposition 4.2）

Associativity, commutativity, and distributivity all follow at once from the corresponding laws in $\mathbb{Z}$. For instance, distributivity reads

$$[a]([b]+[c]) = [a][b+c] = [a(b+c)] = [ab+ac] = [ab]+[ac] = [a][b]+[a][c] ,$$

where only the third equality uses distributivity in $\mathbb{Z}$; the others merely rewrite the definition. The additive identity is $[0]$, the additive inverse of $[a]$ is $[-a]$, and the multiplicative identity is $[1]$.

∎

For ring theory in general see Foundations of rings and fields, and for the viewpoint of $\mathbb{Z}/n\mathbb{Z}$ as the quotient ring by the ideal $n\mathbb{Z}$ see Theorem 4.2［イデアルと剰余環］ in Ideals and quotient rings.

Definition 4.3（Group of units）

An element $[a]$ of the ring $\mathbb{Z}/n\mathbb{Z}$ is called a unit if there is some $[b]$ with $[a][b] = [1]$. The set of all units is written $(\mathbb{Z}/n\mathbb{Z})^{\times}$.

Proposition 4.4

An element $[a] \in \mathbb{Z}/n\mathbb{Z}$ is a unit if and only if $\gcd(a,n) = 1$. Moreover $(\mathbb{Z}/n\mathbb{Z})^{\times}$ is a group under multiplication.

Proof（Proposition 4.4）

$(\Leftarrow)$ If $\gcd(a,n)=1$, then by Theorem 2.2 there are integers $x,y$ with $ax + ny = 1$. This says $ax - 1 = -ny$, that is, $ax \equiv 1 \pmod n$, so $[a][x] = [1]$.

$(\Rightarrow)$ If $[a][b] = [1]$, then $ab - 1 = nk$ for some integer $k$, so $ab - nk = 1$. Now $d = \gcd(a,n)$ divides both terms on the left, so $d \mid 1$ and therefore $d = 1$.

Let us check the group axioms. The class $[1]$ is a unit. If $[a]$ and $[b]$ are units with $[a][x]=[1]$ and $[b][y]=[1]$, then $[ab][xy] = [a][x][b][y] = [1]$, so the product $[ab]$ is a unit and the operation is closed. Associativity comes from multiplication in the ring, and the existence of inverses is the definition of a unit.

∎

Corollary 4.5

The ring $\mathbb{Z}/n\mathbb{Z}$ is a field if and only if $n$ is prime.

Proof（Corollary 4.5）

Let $n = p$ be prime. Saying $[a] \ne [0]$ means $p \nmid a$, and since $p$ is prime, $\gcd(a,p) \in \{1,p\}$ with $p$ excluded, so $\gcd(a,p)=1$. By Proposition 4.4, $[a]$ is a unit, so $\mathbb{Z}/p\mathbb{Z}$ is a field (and $p \ge 2$ ensures $[1] \ne [0]$).

Conversely, if $n$ is composite then $n = ab$ with $1 < a, b < n$, and $[a] \ne [0]$, $[b] \ne [0]$ while $[a][b] = [n] = [0]$. A field has no zero divisors (if $[a][b]=[0]$ and $[a]$ is invertible, multiplying both sides by $[a]^{-1}$ gives $[b]=[0]$), so this is not a field. For $n = 1$ we have $[1]=[0]$, which violates the definition of a field.

∎

For a prime $p$ we write $\mathbb{F}_p$ for the field $\mathbb{Z}/p\mathbb{Z}$. What Corollary 4.5 says is that the primes are the only moduli producing a “finite world in which one can divide”. The special status of primes takes an algebraic form here. The same statement is obtained from the side of ring theory as Corollary 5.5［環と体の基礎］.

Definition 4.6（Euler's totient function）

For $n \in \mathbb{N}$ set

$$\varphi(n) := \#\{a \in \mathbb{Z} \mid 1 \le a \le n,\ \gcd(a,n)=1\} .$$

By Proposition 4.4 we have $\varphi(n) = \#(\mathbb{Z}/n\mathbb{Z})^{\times}$.

Example 4.7（The group of units of Z/12Z）

Among $1$ through $12$, those coprime to $12$ are $1, 5, 7, 11$, four in all, so $\varphi(12)=4$ and $(\mathbb{Z}/12\mathbb{Z})^{\times} = \{[1],[5],[7],[11]\}$. Writing out the multiplication table,

$$[5]^2 = [25] = [1], \quad [7]^2 = [49] = [1], \quad [11]^2 = [121] = [1], \quad [5][7] = [35] = [11] ,$$

so every element other than the identity has order $2$. This group is therefore isomorphic to the Klein four-group $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ and is not cyclic. By contrast, it is known that for a prime $p$ the group $(\mathbb{Z}/p\mathbb{Z})^{\times}$ is always cyclic (existence of a primitive root).

Theorem 4.8（Chinese remainder theorem）

Let $m, n \in \mathbb{N}$ with $\gcd(m,n)=1$. Then the map

$$\Phi : \mathbb{Z}/mn\mathbb{Z} \longrightarrow \mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}, \qquad [a]_{mn} \longmapsto ([a]_m, [a]_n)$$

is a well-defined ring isomorphism. In particular, for any integers $r, s$ the simultaneous congruences $x \equiv r \pmod m$ and $x \equiv s \pmod n$ have a unique solution modulo $mn$.

Proof（Theorem 4.8）

Well-definedness: if $[a]_{mn} = [a']_{mn}$ then $mn \mid (a-a')$, hence in particular $m \mid (a-a')$ and $n \mid (a-a')$, so $([a]_m,[a]_n) = ([a']_m,[a']_n)$. That $\Phi$ is a ring homomorphism follows at once, since addition and multiplication in each component are exactly the operations of Definition 4.1; and $\Phi([1]_{mn}) = ([1]_m,[1]_n)$ is clear.

Injectivity: suppose $\Phi([a]_{mn}) = ([0]_m,[0]_n)$, so $m \mid a$ and $n \mid a$. Writing $a = mk$ we get $n \mid mk$, and since $\gcd(n,m)=1$, Lemma 2.3 gives $n \mid k$, say $k = nl$. Hence $a = mnl$, that is, $[a]_{mn} = [0]_{mn}$. Since the kernel of the homomorphism is trivial, $\Phi$ is injective.

Surjectivity: the domain and codomain are both finite, with $mn$ and $m \cdot n$ elements respectively, hence of equal size. An injective map between finite sets of equal cardinality is surjective, so $\Phi$ is a bijection.

The final assertion is exactly the bijectivity of $\Phi$: the preimage of $([r]_m,[s]_n)$ is a single residue class $[x]_{mn}$, which means existence of a solution together with uniqueness modulo $mn$.

∎

Corollary 4.9

If $\gcd(m,n)=1$ then $\varphi(mn) = \varphi(m)\varphi(n)$. Moreover, if $n = p_1^{e_1}\cdots p_k^{e_k}$ is the prime factorization of $n$, then

$$\varphi(n) = n \prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right).$$

Proof（Corollary 4.9）

A ring isomorphism carries units to units and non-units to non-units (since $\Phi(u)\Phi(u^{-1}) = \Phi(1) = 1$, and likewise in the other direction for $\Phi^{-1}$). Hence the map $\Phi$ of Theorem 4.8 induces a bijection between groups of units,

$$(\mathbb{Z}/mn\mathbb{Z})^{\times} \xrightarrow{\ \sim\ } (\mathbb{Z}/m\mathbb{Z})^{\times} \times (\mathbb{Z}/n\mathbb{Z})^{\times} .$$

Counting elements on both sides gives $\varphi(mn)=\varphi(m)\varphi(n)$.

For a prime power $p^e$, the integers from $1$ to $p^e$ that are not coprime to $p^e$ are the multiples of $p$, namely $p, 2p, \ldots, p^{e-1}\cdot p$, of which there are $p^{e-1}$. Hence

$$\varphi(p^e) = p^e - p^{e-1} = p^e\left(1 - \frac{1}{p}\right).$$

Distinct prime powers are coprime, so repeated use of multiplicativity gives the formula.

∎

5. Fermat’s little theorem and Euler’s theorem

Fermat stated this theorem in a letter to Frénicle in 1640, but omitted the proof, saying it would run too long. The first published proof is due to Euler (1736).

Theorem 5.1（Fermat's little theorem）

Let $p$ be prime and let $a$ be an integer with $p \nmid a$. Then

$$a^{p-1} \equiv 1 \pmod p .$$

Proof（Theorem 5.1）

Let $S = \{1, 2, \ldots, p-1\}$ and define a map $\sigma$ by sending $x \in S$ to $ax \bmod p$. We argue in three steps.

Step one (the values of $\sigma$ lie in $S$). From $1 \le x \le p-1$ and $p \nmid a$, the second half of Lemma 2.3 gives $p \nmid ax$. Hence $ax \bmod p \ne 0$, that is, $\sigma(x) \in S$.

Step two ($\sigma$ is injective). Suppose $\sigma(x) = \sigma(y)$, so $ax \equiv ay \pmod p$. From $p \nmid a$ we get $\gcd(a,p)=1$, so applying Proposition 3.6 with $c=a$, $n=p$, $d=1$ gives $x \equiv y \pmod p$. Since $x$ and $y$ both lie between $1$ and $p-1$, we have $|x-y| < p$ and hence $x = y$. An injective map from the finite set $S$ to itself is a bijection, so $\sigma$ is a permutation of $S$.

Step three (comparing products). Since $\sigma$ is a permutation,

$$\prod_{x \in S} \sigma(x) = \prod_{x \in S} x = (p-1)! .$$

On the other hand $\sigma(x) \equiv ax \pmod p$ for each $x$, so applying Proposition 3.3 $p-1$ times,

$$\prod_{x \in S}\sigma(x) \equiv \prod_{x\in S} (ax) = a^{p-1}(p-1)! \pmod p .$$

Combining the two gives $a^{p-1}(p-1)! \equiv (p-1)! \pmod p$. None of the $x$ with $1 \le x \le p-1$ is divisible by $p$, so repeated use of Lemma 2.3 gives $p \nmid (p-1)!$, that is, $\gcd((p-1)!,p)=1$. Hence Proposition 3.6 lets us cancel $(p-1)!$, and we obtain $a^{p-1} \equiv 1 \pmod p$.

∎

Corollary 5.2

Let $p$ be prime. Then $a^{p} \equiv a \pmod p$ for every integer $a$.

Proof（Corollary 5.2）

If $p \nmid a$, multiply both sides of Theorem 5.1 by $a$ to get $a^p \equiv a \pmod p$. If $p \mid a$, then $a \equiv 0 \pmod p$, so Proposition 3.3 gives $a^p \equiv 0^p = 0 \equiv a \pmod p$. In either case the congruence holds.

∎

The form in Corollary 5.2 imposes no condition on $a$, which makes it convenient; it will do the work later when we prove the correctness of RSA.

Theorem 5.3（Euler's theorem）

Let $n \in \mathbb{N}$ and $a \in \mathbb{Z}$ with $\gcd(a,n)=1$. Then

$$a^{\varphi(n)} \equiv 1 \pmod n .$$

Proof（Theorem 5.3）

We lift the proof of Theorem 5.1 verbatim. Put $U = (\mathbb{Z}/n\mathbb{Z})^{\times}$, so that $\#U = \varphi(n)$ (Definition 4.6). Since $\gcd(a,n)=1$, Proposition 4.4 gives $[a] \in U$.

Consider the map $\mu_{[a]} : U \to U$, $[x] \mapsto [a][x]$. Because $U$ is a group (Proposition 4.4), we have $[a][x] \in U$, so $\mu_{[a]}$ really does map $U$ into $U$. Moreover $\mu_{[a]^{-1}}$ is an inverse map, so $\mu_{[a]}$ is a bijection, that is, a permutation of $U$.

Now compute the product $P = \prod_{[x]\in U}[x]$ of all elements of $U$ in two ways. Reordering by a permutation does not change the product, so

$$P = \prod_{[x]\in U} \mu_{[a]}([x]) = \prod_{[x]\in U} [a][x] = [a]^{\varphi(n)} P .$$

Being a product of units, $P$ is itself a unit (by the group property in Proposition 4.4), so multiplying both sides by $P^{-1}$ gives $[a]^{\varphi(n)} = [1]$, that is, $a^{\varphi(n)} \equiv 1 \pmod n$.

∎

Remark 5.4

In the language of group theory, Theorem 5.3 is a one-liner: it is just the corollary of Lagrange’s theorem stating that $g^{\#G} = e$ for an element $g$ of a finite group $G$, applied to $G = (\mathbb{Z}/n\mathbb{Z})^{\times}$. For details see Theorem 7.3［Subgroups and Cosets］ in Subgroups and cosets (Lagrange’s theorem). The proof above amounts to writing out that special case without group-theoretic language. Historically it came first; the notion of a group was distilled from an accumulation of such concrete examples (Introduction to group theory — the definition and examples).

Proposition 5.5

Let $p$ be prime and $p \nmid a$. Then the inverse of $[a]$ in $\mathbb{Z}/p\mathbb{Z}$ is given by $[a^{p-2}]$.

Proof（Proposition 5.5）

Since $p \ge 2$ we have $p - 2 \ge 0$, so $a^{p-2}$ is an integer. By Theorem 5.1,

$$[a] \cdot [a^{p-2}] = [a^{p-1}] = [1] .$$

The inverse is unique (by general group theory, or because if $[b]$ and $[b']$ are both inverses then $[b] = [b][a][b'] = [b']$), so this is $[a]^{-1}$.

∎

Example 5.6（3 to the 1000th power modulo 7）

Since $7$ is prime and $7 \nmid 3$, Theorem 5.1 gives $3^6 \equiv 1 \pmod 7$. As $1000 = 6 \cdot 166 + 4$,

$$3^{1000} = (3^{6})^{166} \cdot 3^{4} \equiv 1^{166}\cdot 3^4 = 81 \pmod 7 .$$

Since $81 = 7\cdot 11 + 4$, we get $3^{1000} \equiv 4 \pmod 7$. Replacing the exponent by its remainder modulo $\varphi(7)=6$ is the practical use of the little theorem.

6. Applications — fast exponentiation, RSA, primality testing

6.1. Repeated squaring

Computing $a^e \bmod n$ does not require $e$ multiplications. Expand $e$ in binary and square repeatedly to get $a, a^2, a^4, \ldots$, multiplying in only the terms needed; then $O(\log e)$ multiplications suffice. Since we reduce $\bmod\ n$ at every stage, no intermediate number ever exceeds $n^2$ (the justification is Proposition 3.3).

def power_mod(a, e, n):
    """Compute a^e mod n by repeated squaring. Requires e >= 0, n >= 1."""
    result = 1
    a %= n
    while e > 0:
        if e & 1:
            result = result * a % n
        a = a * a % n
        e >>= 1
    return result

assert power_mod(2, 100, 100) == 76      # last two digits of 2^100
assert power_mod(3, 1000, 7) == 4        # 3^1000 modulo 7

To compute inverses we use the extended Euclidean algorithm, which is the proof of Theorem 2.2 turned into a procedure.

def ext_gcd(a, b):
    """Return (g, x, y) with g = gcd(a, b) and a*x + b*y = g."""
    if b == 0:
        return (a, 1, 0)
    g, x, y = ext_gcd(b, a % b)
    return (g, y, x - (a // b) * y)

def inverse_mod(a, n):
    g, x, _ = ext_gcd(a % n, n)
    if g != 1:
        raise ValueError("the inverse does not exist")
    return x % n

assert inverse_mod(7, 120) == 103

6.2. The RSA cryptosystem

Theorem 6.1（Correctness of RSA）

Let $p \ne q$ be primes, and set $n = pq$ and $\varphi(n) = (p-1)(q-1)$. Suppose integers $e, d$ satisfy

$$ed \equiv 1 \pmod{\varphi(n)}, \qquad \gcd(e,\varphi(n)) = 1 .$$

Then for every integer $m$,

$$(m^{e})^{d} \equiv m \pmod n .$$

Proof（Theorem 6.1）

By hypothesis there is an integer $k \ge 0$ with $ed = 1 + k\varphi(n) = 1 + k(p-1)(q-1)$ (we may assume $ed \ge 1$).

We first show $m^{ed} \equiv m \pmod p$. If $p \mid m$ then both sides are congruent to $0$ and the claim holds. If $p \nmid m$, then Theorem 5.1 gives $m^{p-1}\equiv 1 \pmod p$, so

$$m^{ed} = m \cdot \left(m^{p-1}\right)^{k(q-1)} \equiv m \cdot 1^{k(q-1)} = m \pmod p ,$$

where we used the multiplicative and power statements of Proposition 3.3. Interchanging $p$ and $q$, the same argument gives $m^{ed}\equiv m \pmod q$.

Hence $p \mid (m^{ed}-m)$ and $q \mid (m^{ed}-m)$. Since $p \ne q$ are both prime, $\gcd(p,q)=1$, so the injectivity argument of Theorem 4.8 (or Lemma 2.3 directly) gives $pq \mid (m^{ed}-m)$, that is, $m^{ed}\equiv m \pmod n$.

It matters that we did not assume $\gcd(m,n)=1$. Using Theorem 5.3 as it stands would require that hypothesis, but splitting into prime factors and using the form Corollary 5.2 dispenses with it.

∎

flowchart TD
A["choose primes p, q"] --> B["n = pq, phi = (p-1)(q-1)"]
B --> C["choose e with gcd(e, phi) = 1"]
C --> D["find d = e^-1 mod phi by extended Euclid"]
D --> E["public key (n, e)"]
D --> F["private key (n, d)"]
E --> G["encrypt c = m^e mod n"]
G --> H["decrypt m = c^d mod n"]
F --> H

Key generation, encryption, and decryption in RSA. Security rests on the difficulty of recovering p and q from n.

Example 6.2（Carrying RSA through with a small key）

Take $p = 11$ and $q = 13$, so $n = 143$ and $\varphi(n) = 10 \cdot 12 = 120$. The exponent $e = 7$ satisfies $\gcd(7,120)=1$. Then $d$ solves $7d \equiv 1 \pmod{120}$, and from $7 \cdot 103 = 721 = 6\cdot 120 + 1$ we get $d = 103$.

Encrypt the plaintext $m = 5$:

$$5^2 = 25,\quad 5^4 \equiv 25^2 = 625 = 4\cdot 143 + 53 \equiv 53 \pmod{143},$$$$c = 5^7 = 5^4\cdot 5^2 \cdot 5 \equiv 53 \cdot 25 \cdot 5 \pmod{143}.$$

Since $53\cdot 25 = 1325 = 9\cdot 143 + 38 \equiv 38$ and $38 \cdot 5 = 190 = 143 + 47 \equiv 47$, we get $c = 47$.

Now decrypt. Instead of computing $47^{103} \bmod 143$ directly, we use Theorem 4.8 and split into the moduli $11$ and $13$.

Modulo $11$: $47 = 4\cdot 11 + 3 \equiv 3$, and Theorem 5.1 gives $3^{10}\equiv 1 \pmod{11}$; since $103 = 10\cdot 10 + 3$, we get $47^{103} \equiv 3^{3} = 27 \equiv 5 \pmod{11}$.

Modulo $13$: $47 = 3\cdot 13 + 8 \equiv 8$ and $8^{12}\equiv 1 \pmod{13}$; since $103 = 12\cdot 8 + 7$, we get $47^{103}\equiv 8^{7} \pmod{13}$. Here $8^2 = 64 = 4\cdot 13 + 12 \equiv -1$, so $8^7 = (8^2)^3 \cdot 8 \equiv (-1)^3\cdot 8 = -8 \equiv 5 \pmod{13}$.

The unique solution modulo $143$ of $x \equiv 5 \pmod{11}$ and $x \equiv 5 \pmod{13}$ is $x = 5$. The plaintext $m=5$ has indeed been recovered.

Caution

In real RSA, $p$ and $q$ are primes of several hundred digits, and the plaintext is not converted directly into a number but processed by a padding scheme such as OAEP. Textbook “naive RSA” has weaknesses that are fatal in practice: the same plaintext always produces the same ciphertext, and for small $e$ with a short plaintext the quantity $m^e$ may not even exceed $n$, so the message can be recovered by taking an integer root.

6.3. The Fermat primality test and Carmichael numbers

The contrapositive of Corollary 5.2 can be used to test primality: if $a^{n-1}\not\equiv 1 \pmod n$ for some $a$ (with $\gcd(a,n)=1$), then $n$ is not prime. This test runs quickly using repeated squaring.

The trouble is the converse. The fact that $a^{n-1}\equiv 1 \pmod n$ holds does not make $n$ prime.

Definition 6.3（Carmichael number）

A composite number $n$ satisfying $a^{n-1}\equiv 1 \pmod n$ for every integer $a$ with $\gcd(a,n)=1$ is called a Carmichael number.

Example 6.4（561 is a Carmichael number）

We have $561 = 3\cdot 11\cdot 17$, which is composite. Also $560$ is divisible by each of $2, 10, 16$ (indeed $560 = 2\cdot 280 = 10\cdot 56 = 16\cdot 35$). If $\gcd(a,561)=1$, then $a$ is divisible by none of $3, 11, 17$, so Theorem 5.1 gives

$$a^{2}\equiv 1 \pmod 3, \qquad a^{10}\equiv 1\pmod{11}, \qquad a^{16}\equiv 1 \pmod{17}.$$

Since $560$ is a multiple of each of these exponents, we get $a^{560} = (a^{2})^{280} \equiv 1 \pmod 3$ and similarly for the others, so $a^{560}\equiv 1$ modulo all three primes. Using Theorem 4.8 twice yields $561 \mid (a^{560}-1)$, that is, $a^{560}\equiv 1 \pmod{561}$.

Here $561$ is the smallest Carmichael number. In 1994 Alford, Granville, and Pomerance proved that there are infinitely many Carmichael numbers.

The Fermat test is therefore not a deterministic primality test. The defect is remedied by the Miller–Rabin test, which writes $n-1 = 2^{s}t$ with $t$ odd and inspects the sequence $a^{t}, a^{2t},\ldots$ to detect the appearance of a nontrivial square root of $1$. The principle is that if $\mathbb{Z}/p\mathbb{Z}$ is a field (Corollary 4.5), the solutions of $x^2 = 1$ are only $\pm 1$. A composite number slips past the Miller–Rabin test with probability at most $1/4$ for each base, so taking many bases gives certainty that is ample in practice.

Remark 6.5

The ring $\mathbb{Z}/n\mathbb{Z}$ treated in this article is the first step in the practice of studying arithmetic objects by mapping them into finite algebraic systems. Pushing the same idea further leads to the procedure of counting, for each prime $p$, the number of solutions of an equation over $\mathbb{F}_p$ and assembling these counts into a generating function. Carrying this out for elliptic curves gives the Hasse–Weil $L$-function, the subject of Elliptic curves and modular forms and Fermat’s Last Theorem. The names are similar, but this is the distance separating Fermat’s little theorem from his last theorem.

7. Exercises

Exercise 7.1Easy

Find the units digit of $7^{2026}$.

Solution

The units digit is the residue modulo $10$. We have $\gcd(7,10)=1$ and $\varphi(10)=\varphi(2)\varphi(5)=1\cdot 4=4$ (Corollary 4.9), so Theorem 5.3 gives $7^{4}\equiv 1 \pmod{10}$. Since $2026 = 4\cdot 506 + 2$,

$$7^{2026} = (7^{4})^{506}\cdot 7^{2} \equiv 1^{506}\cdot 49 \equiv 9 \pmod{10}.$$

Hence the units digit is $9$.

Exercise 7.2Standard

Prove that $(p-1)! \equiv -1 \pmod p$ for every prime $p$ (Wilson’s theorem).

Solution

For $p = 2$ we have $1! = 1 \equiv -1 \pmod 2$, so the claim holds; assume from now on that $p$ is an odd prime.

Since $\mathbb{Z}/p\mathbb{Z}$ is a field (Corollary 4.5), all of $[1],\ldots,[p-1]$ are invertible. We first determine the elements that are their own inverses. The equation $[x]^2=[1]$ is equivalent to $p \mid (x-1)(x+1)$, and Lemma 2.3 gives $p \mid (x-1)$ or $p \mid (x+1)$, that is, $x \equiv 1$ or $x\equiv -1 \pmod p$. For an odd prime $p$ we have $1 \not\equiv -1$, so there are exactly two self-inverse elements, $[1]$ and $[p-1]$.

The remaining $p-3$ elements split into pairs $\{[x], [x]^{-1}\}$ of distinct elements (uniqueness of inverses makes this pairing consistent). The product of each pair is $[1]$, so

$$(p-1)! = \prod_{x=1}^{p-1}[x] = [1]\cdot [p-1]\cdot \prod_{\text{pairs}} [1] = [p-1] = [-1].$$

Hence $(p-1)!\equiv -1 \pmod p$.

Exercise 7.3Standard

For $341 = 11\cdot 31$, show that $2^{340}\equiv 1 \pmod{341}$ (so that $341$ is a Fermat pseudoprime to the base $2$). Also compute $3^{340} \bmod 341$ and confirm that the base $3$ does detect $341$ as composite.

Solution

Base $2$: from $2^{10}=1024 = 93\cdot 11 + 1$ we get $2^{10}\equiv 1 \pmod{11}$, and since $340 = 10\cdot 34$, $2^{340}\equiv 1 \pmod{11}$. Also $2^{5}=32 = 31+1 \equiv 1 \pmod{31}$ and $340 = 5\cdot 68$, so $2^{340}\equiv 1 \pmod{31}$. Since $\gcd(11,31)=1$, Theorem 4.8 gives $341 \mid (2^{340}-1)$, that is, $2^{340}\equiv 1\pmod{341}$.

Base $3$: modulo $11$ we have $3^{5}=243 = 22\cdot 11 + 1 \equiv 1$ and $340 = 5\cdot 68$, so $3^{340}\equiv 1 \pmod{11}$. Modulo $31$, Theorem 5.1 gives $3^{30}\equiv 1$, and since $340 = 30\cdot 11 + 10$ we get $3^{340}\equiv 3^{10} \pmod{31}$. Here $3^{3}=27$ and $3^{5}=243 = 7\cdot 31 + 26 \equiv -5$, so $3^{10} \equiv (-5)^2 = 25 \pmod{31}$.

Since $3^{340}\equiv 25 \not\equiv 1 \pmod{31}$, we have $3^{340}\not\equiv 1 \pmod{341}$, and the contrapositive of Corollary 5.2 shows that $341$ is composite. To find the value, solve $x\equiv 1 \pmod{11}$ and $x \equiv 25 \pmod{31}$. Putting $x = 25 + 31k$ and using $25 \equiv 3$, $31\equiv 9 \pmod{11}$, we need $3 + 9k \equiv 1$, that is, $9k \equiv -2 \equiv 9 \pmod{11}$; since $\gcd(9,11)=1$, Proposition 3.6 gives $k \equiv 1 \pmod{11}$. Taking $k=1$ gives $x = 56$, so $3^{340}\equiv 56 \pmod{341}$.

Exercise 7.4Hard

Show that if a composite number $n$ is a Carmichael number (Definition 6.3), then $n$ is squarefree and $(p-1)\mid (n-1)$ for every prime factor $p$ of $n$ (the necessity half of Korselt’s criterion).

Solution

Let $n$ be a Carmichael number.

Squarefreeness. Suppose there were a prime $p$ with $p^{2}\mid n$. From the prime factorization of $n$ we may write $n = p^{e}m$ with $e \ge 2$ and $p \nmid m$. Since $\gcd(p^{2}, m)=1$, Theorem 4.8 supplies an integer $a$ with

$$a \equiv 1 + p \pmod{p^{2}}, \qquad a \equiv 1 \pmod{m} .$$

This $a$ is not divisible by $p$ (because $a \equiv 1 \pmod p$) and is divisible by no prime factor of $m$ (because $a\equiv 1 \pmod m$), so $\gcd(a,n)=1$.

By the binomial theorem, modulo $p^{2}$,

$$a^{k} \equiv (1+p)^{k} \equiv 1 + kp \pmod{p^{2}}$$

(every term of degree at least $2$ in $p$ is a multiple of $p^{2}$). Hence $a^{n-1}\equiv 1 \pmod{p^{2}}$ is equivalent to $p^{2} \mid (n-1)p$, that is, to $p \mid (n-1)$. But $p \mid n$, so $p \nmid (n-1)$ — a contradiction. Therefore $n$ is squarefree.

The divisibility $(p-1)\mid(n-1)$. Let $p$ be a prime factor of $n$. The ring $\mathbb{Z}/p\mathbb{Z}$ is a field and its group of units $(\mathbb{Z}/p\mathbb{Z})^{\times}$ is cyclic of order $p-1$. Take a generator $g$, and use Theorem 4.8 to obtain $a$ with $a \equiv g \pmod p$ and $a \equiv 1 \pmod{n/p}$; then $\gcd(a,n)=1$ (since $n$ is squarefree we may use $\gcd(p, n/p)=1$).

By the definition of a Carmichael number, $a^{n-1}\equiv 1 \pmod n$, and in particular $a^{n-1}\equiv 1 \pmod p$. That is, $g^{n-1} = 1$ holds in $(\mathbb{Z}/p\mathbb{Z})^{\times}$. The order of $g$ is $p-1$, so the only $k$ with $g^{k}=1$ are the multiples of $p-1$. Hence $(p-1)\mid(n-1)$.

(For $561$, that $3-1=2$, $11-1=10$, and $17-1=16$ all divide $560$ was checked in Example 6.4.)

References

• Teiji Takagi, Shotō Seisūron Kōgi, 2nd ed., Kyoritsu Shuppan, 1971 (in Japanese) — Chapters 1 and 2. A classic, available in Japanese, running from the introduction of congruences through Euler’s theorem to primitive roots.
• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008 — Chapters 5 and 6 (congruences and Fermat’s theorem).
• K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Springer GTM 84, 1990 — Chapters 3 and 4, treating the structure of residue rings and their unit groups algebraically.
• C. F. Gauss, Disquisitiones Arithmeticae, 1801 (English translation: Springer, 1986) — Sections 1 and 2 introduce the congruence symbol $\equiv$ and its basic properties.
• R. L. Rivest, A. Shamir, L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM 21 (1978), 120–126. DOI: 10.1145/359340.359342
• W. R. Alford, A. Granville, C. Pomerance, “There are Infinitely Many Carmichael Numbers”, Annals of Mathematics 139 (1994), 703–722.
• Akihiko Yukie, Daisūgaku 1: Gunron Nyūmon, Nippon Hyoron Sha, 2010 (in Japanese) — Chapter 2, where the route from Lagrange’s theorem to Theorem 5.3 is set out.

Appendix: A combinatorial proof of Fermat’s little theorem

Setting up the objects to be counted. There is a proof of Theorem 5.1 that uses no residue classes at all. Let $a \ge 1$ be an integer, $p$ a prime, and let $X$ be the set of all strings of $p$ beads in a row, each bead having one of $a$ colours. Then $\#X = a^{p}$.

Separating monochromatic strings from the rest. Let the “cyclic shift” act on $X$: the operation $\tau$ sending a string $(x_1,\ldots,x_p)$ to $(x_2,\ldots,x_p,x_1)$. Since $\tau^{p}$ is the identity, $X$ is partitioned into the orbits of $\tau$. If the orbit of some string has size $k$, then $k$ is the least positive integer with $\tau^{k}$ fixing that string, and since $\tau^{p}$ also fixes it, $k \mid p$. As $p$ is prime, either $k = 1$ or $k = p$.

An orbit has size 1 only for monochromatic strings. Saying $k=1$ means invariance under $\tau$, that is, $x_1 = x_2 = \cdots = x_p$. There are as many such strings as there are colours, namely $a$. The remaining $a^{p}-a$ strings all lie in orbits of size $p$.

The conclusion of the count. The set obtained from $X$ by removing the monochromatic strings is a disjoint union of orbits of size $p$, so its cardinality is a multiple of $p$. That is,

$$p \mid (a^{p}-a) ,$$

which is nothing other than Corollary 5.2. When $p \nmid a$ we have $\gcd(a,p)=1$, so Proposition 3.6 lets us cancel $a$ and obtain $a^{p-1}\equiv 1 \pmod p$. For $a$ negative or zero, replace $a$ by its remainder on division by $p$; Proposition 3.3 then gives the same conclusion.

What this proof means. The essential point is that it explains an arithmetic fact, “divisibility by $p$”, as a fact about counting: “the objects can be sorted into groups of $p$”. It is also the simplest manifestation of the general theory of orbits and fixed points, in which the group $\mathbb{Z}/p\mathbb{Z}$ acts on a set and the size of each orbit divides the order of the group (Theorem 6.1［Subgroups and Cosets］).