Fermat's Little Theorem

For any prime p and integer a not divisible by p: a^(p-1) ≡ 1 (mod p)
Reveals primes create regular structure in modular exponentiation via multiplicative cycling
Stated by Fermat (1640) without proof; first proven by Euler (1736)
Generalizes to Euler's Theorem and emerges from Lagrange's Theorem on multiplicative groups
Foundation for modern cryptography, primality testing, and computational number theory
Shows why primes are special: only they make all non-zero elements cycle predictably

Fermat's Little Theorem

Overview

Fermat's Little Theorem stands as one of the most elegant and useful results in elementary number theory, establishing a fundamental relationship between prime numbers and modular arithmetic. Despite its deceptively simple statement, this theorem underpins much of modern cryptography, primality testing, and computational number theory. For a first encounter with deep number-theoretic ideas, Fermat's Little Theorem offers the perfect balance: accessible to prove with basic tools, yet profound in its applications.

The theorem tells us something remarkable: when you raise any integer to the power of a prime $p$ , then reduce modulo $p$ , the result depends only on the original integer modulo $p$ , and in particular, if the integer is not divisible by $p$ , raising it to the $p - 1$ power always yields 1. This is not obvious—why should exponentiation interact so cleanly with division by primes? The answer lies in the structure of modular arithmetic and the properties that make primes special.

Historically, Pierre de Fermat stated this result in a letter to Frénicle de Bessy in 1640, though he provided no proof. The first published proof came from Leonhard Euler in 1736, who later generalized it to the more comprehensive Euler's Theorem. The theorem has since become a cornerstone of algebraic number theory and group theory, where it emerges as a special case of Lagrange's Theorem applied to the multiplicative group of integers modulo a prime.

Fermat's Little Theorem reveals that prime numbers impose a regular, predictable structure on exponentiation: every non-zero element, when raised to the power $p - 1$ , becomes 1 modulo $p$ . This "multiplicative cycling" is unique to primes and is the foundation for their role in cryptography.

Fermat's Little Theorem: Let

p

be a prime number. Then for any integer

a

not divisible by

p

, we have

a^{p - 1} \equiv 1 (mod p)

Equivalently, for any integer

a

(including those divisible by

p

), we have

a^{p} \equiv a (mod p)

Core Theory

Main Result

Theorem [1] (Fermat's Little Theorem): Let

p

be a prime number and let

a

be an integer with

g cd (a, p) = 1

. Then

a^{p - 1} \equiv 1 (mod p)

Theorem [2] (Alternative Formulation): Let

p

be a prime number. Then for any integer

a

a^{p} \equiv a (mod p)

We present two proofs of Theorem [1], each illuminating different aspects of the result.

Proof 1 (Combinatorial Argument via Multiplication):

Consider the set $S = {1, 2, 3, \dots, p - 1}$ of non-zero residues modulo $p$ .

Since $g cd (a, p) = 1$ , multiplication by $a$ is a bijection on $S$ modulo $p$ . That is, the set

a S = {a \cdot 1, a \cdot 2, a \cdot 3, \dots, a \cdot (p - 1)}

is a permutation of

S

when reduced modulo

p

To see this: if $ai \equiv aj (mod p)$ for $1 \leq i, j \leq p - 1$ , then $p ∣ a (i - j)$ . Since $p$ is prime and $g cd (a, p) = 1$ , by Euclid's Lemma we have $p ∣ (i - j)$ . But $∣ i - j ∣ < p$ , so $i = j$ . Thus all elements of $a S$ are distinct modulo $p$ , and since there are $p - 1$ of them, they must be exactly $S$ in some order.

Therefore:

k = 1 \prod p - 1 (ak) \equiv k = 1 \prod p - 1 k (mod p)

This gives us:

a^{p - 1} k = 1 \prod p - 1 k \equiv k = 1 \prod p - 1 k (mod p)

Now $(p - 1)! = \prod_{k = 1}^{p - 1} k$ is not divisible by $p$ (since each factor is less than $p$ ), so $g cd ((p - 1)!, p) = 1$ . By the cancellation law in modular arithmetic, we can divide both sides by $(p - 1)!$ :

a^{p - 1} \equiv 1 (mod p)

Proof 2 (Group-Theoretic):

Consider the multiplicative group $(Z / p Z)^{*} = {1, 2, \dots, p - 1}$ under multiplication modulo $p$ . Since $p$ is prime, this is indeed a group of order $p - 1$ .

By Lagrange's Theorem from group theory, the order of any element divides the order of the group. If $a \in (Z / p Z)^{*}$ , then the order of $a$ divides $p - 1$ , meaning $a^{p - 1} = 1$ in the group, which translates to $a^{p - 1} \equiv 1 (mod p)$ .

Proof of Theorem [2] from Theorem [1]:

If $g cd (a, p) = 1$ , then by Theorem [1], $a^{p - 1} \equiv 1 (mod p)$ , so multiplying both sides by $a$ gives $a^{p} \equiv a (mod p)$ .

If $p ∣ a$ , then $a \equiv 0 (mod p)$ , so $a^{p} \equiv 0^{p} = 0 \equiv a (mod p)$ . □

Common Error: Fermat's Little Theorem requires

p

to be prime. Students often mistakenly apply it when

p

is composite. For example, with

a = 2

and

n = 4

, we have

2^{4 - 1} = 8 \equiv 0 (mod 4)

, not 1. The theorem fails completely for composite moduli (though Euler's Theorem provides the correct generalization using the Euler totient function). Pierre de Fermat (1640) — First stated this theorem in correspondence, claiming to have a proof but never publishing it, launching centuries of investigation into modular arithmetic and prime numbers.

Examples and Applications

1

Computing large powers efficiently

Calculate $5^{100} (mod 11)$ .

Solution: Since 11 is prime and

g cd (5, 11) = 1

, Fermat's Little Theorem tells us that

5^{10} \equiv 1 (mod 11)

We write $100 = 10 \cdot 10$ , so:

5^{100} = (5^{10})^{10} \equiv 1^{10} = 1 (mod 11)

Without Fermat's Little Theorem, computing $5^{100}$ directly would be computationally intensive. This theorem reduces the problem dramatically.

2

Finding modular inverses

Find the multiplicative inverse of 7 modulo 13.

Solution: We seek

x

such that

7 x \equiv 1 (mod 13)

By Fermat's Little Theorem, $7^{12} \equiv 1 (mod 13)$ . Rewriting:

7 \cdot 7^{11} \equiv 1 (mod 13)

So $x \equiv 7^{11} (mod 13)$ is our inverse. We compute efficiently:

$7^{2} = 49 \equiv 10 (mod 13)$
$7^{4} \equiv 1 0^{2} = 100 \equiv 9 (mod 13)$
$7^{8} \equiv 9^{2} = 81 \equiv 3 (mod 13)$
$7^{11} = 7^{8} \cdot 7^{2} \cdot 7 \equiv 3 \cdot 10 \cdot 7 = 210 \equiv 2 (mod 13)$

Check: $7 \cdot 2 = 14 \equiv 1 (mod 13)$ . ✓

Thus the inverse of 7 modulo 13 is 2.

Why the prime hypothesis is essential

Consider $a = 2$ and $n = 6$ (composite). If Fermat's Little Theorem applied to composite moduli, we'd expect $2^{6 - 1} = 2^{5} = 32 \equiv 1 (mod 6)$ .

However, $32 = 5 \cdot 6 + 2$ , so $32 \equiv 2 (mod 6)$ , not 1.

The failure occurs because the multiplicative group $(Z /6 Z)^{*} = {1, 5}$ has order $ϕ (6) = 2$ , not $6 - 1 = 5$ . For composite $n$ , we must use Euler's Theorem: $a^{ϕ (n)} \equiv 1 (mod n)$ when $g cd (a, n) = 1$ . Here $ϕ (6) = 2$ , and indeed $2^{2} = 4 \equiv 1 (mod 6)$ fails too (it gives $4$ ), illustrating that even Euler's theorem requires coprimality!

Actually, $g cd (2, 6) = 2 \neq = 1$ , so neither theorem applies. For a valid example: $5^{2} = 25 \equiv 1 (mod 6)$ . ✓

Mental Model: The Cyclic Odometer

Imagine an odometer with $p$ positions (where $p$ is prime) that advances by multiplying by $a$ each step, wrapping around modulo $p$ . Since $p$ is prime, the only way to return to position 1 is if you've hit every non-zero position exactly once (or some divisor's worth of times).

Fermat's Little Theorem guarantees that after exactly $p - 1$ steps, you're back at 1. The primality of $p$ ensures that multiplication by any $a \neq \equiv 0$ creates a permutation of the non-zero residues—there are no "short circuits" or smaller cycles (unless $a$ has smaller order dividing $p - 1$ ).

Geometrically, think of the $p - 1$ non-zero residues as nodes in a cycle graph. Multiplication by $a$ is an arrow from each node to another. Primality ensures this graph is strongly connected: starting from 1, you can reach every other node and return, creating a beautiful cyclic symmetry.

Historical Development

Pierre de Fermat first stated this theorem in a letter dated October 18, 1640, to his correspondent Frénicle de Bessy. As was typical for Fermat, he claimed to have a proof but did not provide it, writing instead that he would send the demonstration if Frénicle had trouble finding it himself. No proof from Fermat survives.

The first published proof appeared in 1736 by Leonhard Euler, who recognized the theorem's importance and placed it on rigorous footing. Euler later generalized the result around 1760 to what is now called Euler's Theorem, which applies to composite moduli using the Euler totient function $ϕ (n)$ . This generalization states that $a^{ϕ (n)} \equiv 1 (mod n)$ when $g cd (a, n) = 1$ , recovering Fermat's Little Theorem as the special case where $n = p$ is prime (since $ϕ (p) = p - 1$ ).

The theorem gained new practical importance in the 20th century with the development of public-key cryptography. The RSA algorithm, invented by Rivest, Shamir, and Adleman in 1977, relies crucially on Fermat's Little Theorem and its generalization for both encryption and efficient computation of modular inverses.

Connections to Other Areas

Connection to Finite Field Theory: Fermat's Little Theorem can be reinterpreted as the statement that in the finite field

F_{p}

with

p

elements, every non-zero element satisfies

x^{p - 1} = 1

. This connects to the deeper fact that the multiplicative group

F_{p}^{*}

is cyclic group|cyclic of order

p - 1

. The theorem thus becomes a special case of the general principle that in any finite group, every element's order divides the group order—revealing that elementary number theory and abstract algebra are intimately connected. This perspective extends to Galois theory, where Fermat's Little Theorem helps us understand the Frobenius endomorphism

x \mapsto x^{p}

in characteristic

p

Fermat's Little Theorem