Fermat's Little Theorem

Statement of Fermat’s Little Theorem

Theorem

Fermat’s Little Theorem: If $p$ is a prime and $a$ is an integer not divisible by $p$, then:

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

Equivalent Formulation

For any integer $a$ and prime $p$:

$a^p \equiv a \pmod{p}$

This form works even when $p \mid a$ (both sides are $0 \bmod p$).

Examples

• $p = 5$, $a = 2$: $2^4 = 16 \equiv 1 \pmod{5}$
• $p = 7$, $a = 3$: $3^6 = 729 \equiv 1 \pmod{7}$
• $p = 11$, $a = 2$: $2^{10} = 1024 \equiv 1 \pmod{11}$

Examinable Proof

The Proof Strategy

We show that $a, 2a, 3a, \ldots, (p-1)a$ modulo $p$ form a permutation of $1, 2, 3, \ldots, p-1$.

Step 1: Non-zeroness

Each $ia \pmod{p}$ is non-zero for $1 \leq i \leq p-1$.

Reason: $p \nmid a$ by hypothesis, and $p \nmid i$ since $1 \leq i < p$ and $p$ is prime.

Thus $p \nmid ia$.

Step 2: Distinctness

If $ia \equiv ja \pmod{p}$ for $1 \leq i, j \leq p-1$, then $i = j$.

Proof: $ia \equiv ja \pmod{p}$ means $p \mid (i-j)a$.

Since $p \nmid a$ and $p$ is prime, Euclid’s lemma gives $p \mid (i-j)$.

But $|i - j| \leq p - 2 < p$, so $|i - j| = 0$ and $i = j$.

Step 3: Permutation Argument

The numbers $1, 2, \ldots, p-1$ are $p-1$ distinct non-zero residues modulo $p$.

By Steps 1 and 2, $a, 2a, \ldots, (p-1)a$ are also $p-1$ distinct non-zero residues modulo $p$.

Therefore:

$\{a, 2a, \ldots, (p-1)a\} = \{1, 2, \ldots, p-1\} \pmod{p}$

Step 4: Product Equality

Taking products:

$a \cdot 2a \cdot 3a \cdot \cdots \cdot (p-1)a \equiv 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (p-1) \pmod{p}$

This simplifies to:

$a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$

Step 5: Cancellation

Since $1 \leq (p-1)! < p!$ and $(p-1)!$ is the product of integers $1$ through $p-1$, none of which are divisible by $p$, we have $p \nmid (p-1)!$.

Thus $\gcd(p, (p-1)!) = 1$.

By the cancellation property of modular arithmetic:

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

Applications

Modular Exponentiation

To compute $a^k \bmod p$ where $p$ is prime:

1. Reduce $k$ modulo $p-1$: $k = q(p-1) + r$ with $0 \leq r < p-1$
2. Then $a^k \equiv a^r \pmod{p}$

Example: Compute $3^{100} \bmod 7$.

$100 = 16 \cdot 6 + 4$, so $3^{100} \equiv 3^4 = 81 \equiv 4 \pmod{7}$.

Primality Testing

If there exists $a$ with $p \nmid a$ such that $a^{p-1} \not\equiv 1 \pmod{p}$, then $p$ is not prime.

Note: The converse is not true in general. A Carmichael number is composite but satisfies $a^{n-1} \equiv 1 \pmod{n}$ for all $a$ coprime to $n$.

Diffie-Hellman Key Exchange

Two parties agree on:

• A large prime $p$
• A generator $g$ of $(\mathbb{Z}/p\mathbb{Z})^\times$

Each picks a secret:

• Alice picks secret $a$, sends $g^a \bmod p$
• Bob picks secret $b$, sends $g^b \bmod p$

Shared secret: $(g^a)^b = (g^b)^a = g^{ab} \bmod p$.

Security relies on the difficulty of computing discrete logarithms.

Fermat’s Theorem and Wilson’s Theorem

Wilson’s Theorem

$(p-1)! \equiv -1 \pmod{p}$ iff $p$ is prime.

Connection

In our proof of Fermat’s Little Theorem, we used that $(p-1)!$ is coprime to $p$. Wilson’s theorem gives its exact value.

Generalisations

Euler’s Theorem

For $a$ coprime to $n$: $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi(n)$ is Euler’s totient function.

When $n$ is prime, $\phi(n) = n-1$, giving Fermat’s Little Theorem.

---

Summary

• Fermat’s Little Theorem: $a^{p-1} \equiv 1 \pmod{p}$ for prime $p$ and $p \nmid a$
• Proof uses permutation argument and cancellation
• Applications: fast modular exponentiation, cryptography (Diffie-Hellman), primality testing
• Generalised by Euler’s theorem to composite moduli