Fermat's Little Theorem — Mathematics Knowledge System

Overview

Fermat's little theorem (stated by Pierre de Fermat in 1640) says that raising any integer to a prime power leaves the number unchanged modulo that prime: aᵖ ≡ a (mod p) for every prime p. When a is not a multiple of p, dividing through by a gives the sharper and more useful form aᵖ⁻¹ ≡ 1 (mod p). This is the reason modular exponentiation is so tame for prime moduli — the exponent only matters modulo p − 1 — and it powers the Fermat primality test, the correctness of RSA decryption, and fast computation of modular inverses (since a·aᵖ⁻² ≡ 1). It is the p-prime special case of Euler's theorem.

Intuition

List the nonzero residues 1, 2, …, p − 1 and multiply every one of them by a (mod p). Because a is invertible, this just shuffles the same list into a new order — no residue is repeated or lost. Multiplying the whole list together before and after the shuffle gives (p−1)! ≡ aᵖ⁻¹·(p−1)! (mod p). Cancelling (p−1)!, which is coprime to p, leaves aᵖ⁻¹ ≡ 1. The theorem is really the statement that 'multiply by a' permutes the nonzero residues.

Formal Definition

Definition

Let p be a prime and a an integer.

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

General form (holds for every integer a)

\gcd(a,p) = 1 \ \Rightarrow\ a^{p-1} \equiv 1 \pmod{p}

Reduced form (a not divisible by p)

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

Modular inverse via the theorem

Worked Examples

2⁶ = 64.
$2^{6} = 64$
64 = 9·7 + 1, so 64 ≡ 1 (mod 7), exactly as aᵖ⁻¹ ≡ 1 predicts.
$64 \equiv 1 \pmod 7$

Answer: 2⁶ ≡ 1 (mod 7). ✓

Practice Problems

Difficulty 2/10

Compute 81 mod 5.

Difficulty 5/10

Using Fermat's little theorem, find the inverse of 3 modulo 7 (i.e. the x with 3x ≡ 1 mod 7).

Difficulty 4/10

Explain how Fermat's little theorem gives a fast (but not perfect) primality test.

Quiz

Summary

aᵖ ≡ a (mod p) for every prime p; if gcd(a, p) = 1 then aᵖ⁻¹ ≡ 1 (mod p).
Consequence: modular inverse a⁻¹ ≡ aᵖ⁻² (mod p), used throughout cryptography.
Basis of the Fermat primality test and the p-prime special case of Euler's theorem.

References

WebsiteWikipedia — Fermat's little theorem