Fermat’s little theorem and Euler’s theorem

In lesson 4 we found that \(3^6 \equiv 1 \pmod 7\) and \(5^6 \equiv 1 \pmod 7\), and used these facts to compute enormous powers modulo 7. That was no accident. Pierre de Fermat noticed in 1640 that \(a^{p-1} \equiv 1 \pmod p\) for every prime \(p\) and every \(a\) not divisible by \(p\). He wrote to a friend that he would send a proof if it were not too long. Leibniz proved it around 1683 in unpublished notes, and Euler published proofs in 1736 and later generalized it to every modulus. Fermat's little theorem, so called to distinguish it from his famous last theorem, is the engine of primality testing and of RSA.

Fermat's little theorem

Theorem (Fermat). If \(p\) is prime and \(p \nmid a\), then \[a^{p-1} \equiv 1 \pmod p.\] Consequently \(a^p \equiv a \pmod p\) for every integer \(a\).

Proof. Consider the \(p - 1\) numbers \(a, 2a, 3a, \ldots, (p - 1)a\). None is \(\equiv 0 \pmod p\), since \(p\) divides neither \(a\) nor \(k\). No two are congruent: if \(ia \equiv ja\), then cancelling \(a\), which is allowed because \(\gcd(a, p) = 1\), gives \(i \equiv j\), so \(i = j\). Therefore these numbers are congruent, in some order, to \(1, 2, \ldots, p - 1\). Multiplying them all together, \[a \cdot 2a \cdots (p - 1)a \equiv 1 \cdot 2 \cdots (p - 1) \pmod p,\] that is, \(a^{p-1}(p - 1)! \equiv (p - 1)! \pmod p\). Since \((p - 1)!\) is a product of numbers coprime to \(p\), it is coprime to \(p\) and can be cancelled, leaving \(a^{p-1} \equiv 1\). Multiplying by \(a\) gives \(a^p \equiv a\), which also holds trivially when \(p \mid a\).

The figure shows the permutations for \(a = 3\) and \(a = 2\) modulo 7. Multiplication by 3 strings all six residues into one cycle, while multiplication by 2 splits them into two cycles of length 3. Either way the residues are only rearranged, so the product \(1 \cdot 2 \cdots 6\) is unchanged. The cycle lengths are not accidental either: they are the orders of 3 and 2 modulo 7, which lesson 8 studies.

A second proof uses the binomial theorem. For a prime \(p\) and \(0 < k < p\), the binomial coefficient \(\binom{p}{k} = \frac{p!}{k!(p - k)!}\) is divisible by \(p\), since \(p\) divides the numerator but not the denominator. Hence \((a + 1)^p \equiv a^p + 1 \pmod p\), the so-called freshman's dream. Induction on \(a \ge 0\) then gives \(a^p \equiv a\): it holds for \(a = 0\), and if \(a^p \equiv a\) then \((a + 1)^p \equiv a^p + 1 \equiv a + 1\). A third, combinatorial proof counts necklaces: there are \(a^p - a\) strings of \(p\) beads, each bead one of \(a\) kinds, that use at least two kinds, and rotating the string groups them into sets of exactly \(p\), since \(p\) is prime, so \(p \mid a^p - a\).

Using Fermat's theorem

Reducing exponents. If \(p \nmid a\) and \(m \equiv n \pmod{p - 1}\), then \(a^m \equiv a^n \pmod p\), since \(a^{p-1} \equiv 1\). Exponents reduce modulo \(p - 1\), not modulo \(p\). For example, \(2^{1000} \bmod 13\): since \(1000 = 12 \cdot 83 + 4\), \(2^{1000} \equiv 2^4 = 16 \equiv 3 \pmod{13}\).

Inverses. If \(p \nmid a\), then \(a \cdot a^{p-2} = a^{p-1} \equiv 1\), so \(a^{-1} \equiv a^{p-2} \pmod p\). For example \(3^{-1} \bmod 11\) is \(3^9 \bmod 11\). Since \(3^5 = 243 \equiv 1 \pmod{11}\), \(3^9 \equiv 3^4 = 81 \equiv 4\), and indeed \(3 \cdot 4 = 12 \equiv 1\).

Proving numbers composite. If \(a^{n-1} \not\equiv 1 \pmod n\) for some \(a\) coprime to \(n\), then \(n\) is not prime. This is the Fermat test. It proves that \(n = 91\) is composite without factoring: \(2^{90} \equiv 64 \pmod{91}\). The test is extremely fast, but the converse fails: \(2^{340} \equiv 1 \pmod{341}\) although \(341 = 11 \cdot 31\). Worse, there are Carmichael numbers, composites \(n\) with \(a^{n-1} \equiv 1 \pmod n\) for every \(a\) coprime to \(n\); the smallest is \(561 = 3 \cdot 11 \cdot 17\). Lesson 11 explains how to repair the test.

Divisibility facts. For every integer \(n\), \(n^{13} - n\) is divisible by \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 13 = 2730\). Indeed, for each of these primes \(p\), \(p - 1\) divides 12, so \(n^{13} = n \cdot (n^{p-1})^{12/(p-1)} \equiv n \pmod p\) when \(p \nmid n\), and trivially when \(p \mid n\). Then the Chinese remainder theorem, or the fact that coprime divisors multiply, combines the primes.

Fast exponentiation

To use these theorems with large numbers we need to compute \(a^k \bmod n\) quickly. Multiplying by \(a\) a total of \(k - 1\) times is hopeless when \(k\) has hundreds of digits. Instead, repeated squaring gives \(a, a^2, a^4, a^8, \ldots\) modulo \(n\), and \(a^k\) is the product of those powers corresponding to the 1s in the binary expansion of \(k\). To compute \(3^{45} \bmod 100\): \(45 = 32 + 8 + 4 + 1\). Squaring repeatedly, \(3^1 = 3\), \(3^2 = 9\), \(3^4 = 81\), \(3^8 \equiv 81^2 = 6561 \equiv 61\), \(3^{16} \equiv 61^2 = 3721 \equiv 21\), \(3^{32} \equiv 21^2 = 441 \equiv 41\). Then \(3^{45} \equiv 41 \cdot 61 \cdot 81 \cdot 3\). Now \(41 \cdot 61 = 2501 \equiv 1\), so \(3^{45} \equiv 81 \cdot 3 = 243 \equiv 43 \pmod{100}\).

The method needs at most \(2\log_2 k\) multiplications, and every intermediate number is less than \(n^2\), because we reduce after each step. For a 2048-bit exponent that is about 4,000 multiplications instead of \(2^{2048}\), the difference between a few milliseconds and an impossibility. The idea is ancient: it appears in the Indian Chandahsutra of Pingala, from around 200 BCE, in a rule for counting poetic rhythms.

Euler's phi function

For a composite modulus, Fermat's theorem fails as stated, since \(a^{n-1} \equiv 1\) usually does not hold. Euler found the right generalization by restricting attention to the numbers coprime to \(n\).

Definition. Euler's phi function \(\varphi(n)\) is the number of integers \(k\) with \(1 \le k \le n\) and \(\gcd(k, n) = 1\). A reduced residue system modulo \(n\) is a set of \(\varphi(n)\) integers, pairwise incongruent modulo \(n\), each coprime to \(n\).

For example, the numbers from 1 to 12 coprime to 12 are 1, 5, 7, 11, so \(\varphi(12) = 4\). For a prime, \(\varphi(p) = p - 1\). For a prime power, the numbers from 1 to \(p^k\) not coprime to \(p^k\) are the multiples of \(p\), of which there are \(p^{k-1}\), so \(\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)\). By the Chinese remainder theorem, as remarked in lesson 5, \(\varphi(mn) = \varphi(m)\varphi(n)\) when \(\gcd(m, n) = 1\). Together these give \[\varphi(n) = n\prod_{p \mid n}\Big(1 - \frac{1}{p}\Big).\] So \(\varphi(100) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40\). Lesson 7 develops these properties systematically.

Euler's theorem

Theorem (Euler, 1763). If \(\gcd(a, n) = 1\), then \[a^{\varphi(n)} \equiv 1 \pmod n.\]

Proof. Let \(r_1, \ldots, r_{\varphi(n)}\) be a reduced residue system. The numbers \(ar_1, \ldots, ar_{\varphi(n)}\) are coprime to \(n\) (a common prime factor of \(ar_i\) and \(n\) would divide \(a\) or \(r_i\)) and pairwise incongruent (cancel \(a\)). So they form another reduced residue system, and their product is congruent to the product of the \(r_i\): \(a^{\varphi(n)}\prod r_i \equiv \prod r_i\). The product \(\prod r_i\) is coprime to \(n\), so it cancels.

When \(n = p\) this is exactly Fermat's theorem. In the language of group theory, the units modulo \(n\) form a group of order \(\varphi(n)\), and Euler's theorem is Lagrange's theorem that an element's order divides the group order.

Examples: the last two digits of \(7^{2026}\). Since \(\gcd(7, 100) = 1\) and \(\varphi(100) = 40\), and \(2026 \equiv 26 \pmod{40}\), \(7^{2026} \equiv 7^{26} \pmod{100}\). Now \(7^2 = 49\), \(7^4 \equiv 49^2 = 2401 \equiv 1\), so \(7^{26} = (7^4)^6 \cdot 7^2 \equiv 49\). The last two digits are 49. As this example shows, the true exponent that brings \(a\) back to 1 can be much smaller than \(\varphi(n)\); here it is 4.

Euler's theorem also solves linear congruences directly: if \(\gcd(a, n) = 1\), the solution of \(ax \equiv b \pmod n\) is \(x \equiv a^{\varphi(n) - 1}b\). And it underlies RSA, where messages are raised to a power \(e\) and recovered with a power \(d\) satisfying \(ed \equiv 1 \pmod{\varphi(n)}\), so that \(m^{ed} = m \cdot (m^{\varphi(n)})^k \equiv m\).

Wilson's theorem

Theorem (Wilson). If \(p\) is prime, then \((p - 1)! \equiv -1 \pmod p\).

Proof. For \(p = 2\) and \(p = 3\) it is checked directly. For \(p \ge 5\), each \(a\) in \(1, 2, \ldots, p - 1\) has a unique inverse in the same range. The only numbers that are their own inverses satisfy \(a^2 \equiv 1\), that is, \(p \mid (a - 1)(a + 1)\), so \(a = 1\) or \(a = p - 1\). The remaining numbers \(2, \ldots, p - 2\) fall into pairs \(\{a, a^{-1}\}\) with product 1, so \((p - 1)! \equiv 1 \cdot (p - 1) \cdot 1 \equiv -1\). For \(p = 7\): \(6! = 1 \cdot (2 \cdot 4)(3 \cdot 5) \cdot 6 \equiv 1 \cdot 1 \cdot 1 \cdot 6 \equiv -1\).

The converse is also true: if \(n > 4\) is composite, then \((n - 1)! \equiv 0 \pmod n\), so the congruence \((n - 1)! \equiv -1\) characterizes the primes. As a primality test it is useless, since computing \((n - 1)!\) takes about \(n\) multiplications. It was stated by the Arab mathematician Ibn al-Haytham around 1000 CE and published, without proof, by Edward Waring in 1770, crediting his student John Wilson; Lagrange gave the first proof in 1771.

Fermat and Euler by computer

The program verifies Fermat's theorem for all small primes, implements square-and-multiply with a count of the multiplications, applies the Fermat test to 91, 341 and 561, computes \(\varphi(n)\) by counting and by the product formula, and checks Wilson's theorem.

import math

def power_mod(a, k, n):
    result, base, mults = 1, a % n, 0
    while k:
        if k & 1:
            result = result * base % n; mults += 1
        base = base * base % n; mults += 1
        k >>= 1
    return result, mults

print("3^45 mod 100:", power_mod(3, 45, 100))
r, m = power_mod(5, 2**2048 - 1, 10**9 + 7)
print("5^(2^2048 - 1) mod 1000000007:", r, "using", m, "multiplications")

primes = [p for p in range(2, 200) if all(p % d for d in range(2, math.isqrt(p) + 1))]
print("Fermat holds for all a < p < 200:", all(pow(a, p - 1, p) == 1 for p in primes for a in range(1, p)))

for n in [91, 341, 561]:
    print(f"n={n}: 2^(n-1) mod n = {pow(2, n - 1, n)}, 3^(n-1) mod n = {pow(3, n - 1, n)}")
print("561 passes for every coprime a:", all(pow(a, 560, 561) == 1 for a in range(1, 561) if math.gcd(a, 561) == 1))

def phi_count(n):
    return sum(1 for k in range(1, n + 1) if math.gcd(k, n) == 1)

def phi(n):
    result, m, p = n, n, 2
    while p * p <= m:
        if m % p == 0:
            while m % p == 0:
                m //= p
            result -= result // p
        p += 1
    if m > 1:
        result -= result // m
    return result

print("phi(n), n = 1..20:", [phi(n) for n in range(1, 21)])
print("formula agrees with counting up to 2000:", all(phi(n) == phi_count(n) for n in range(1, 2001)))
print("Euler holds mod 100:", all(pow(a, phi(100), 100) == 1 for a in range(1, 100) if math.gcd(a, 100) == 1))
print("last two digits of 7^2026:", pow(7, 2026, 100))
print("Wilson: n with (n-1)! = -1 mod n, n < 60:", [n for n in range(2, 60) if math.factorial(n - 1) % n == n - 1])

3^45 mod 100: (43, 10)
5^(2^2048 - 1) mod 1000000007: 906028129 using 4096 multiplications
Fermat holds for all a < p < 200: True
n=91: 2^(n-1) mod n = 64, 3^(n-1) mod n = 1
n=341: 2^(n-1) mod n = 1, 3^(n-1) mod n = 56
n=561: 2^(n-1) mod n = 1, 3^(n-1) mod n = 375
561 passes for every coprime a: True
phi(n), n = 1..20: [1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8]
formula agrees with counting up to 2000: True
Euler holds mod 100: True
last two digits of 7^2026: 49
Wilson: n with (n-1)! = -1 mod n, n < 60: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]

A power with a 617-digit exponent takes about 4,000 multiplications. The Fermat test exposes 91 at once, but 341 fools base 2 (base 3 catches it), and 561 fools every base coprime to it. The numbers satisfying Wilson's congruence are exactly the primes.