Fermat's Little Theorem

Statement

The most common form is: for any integer a and any prime p,

a^p ≡ a (mod p).

A frequently used corollary applies when a is not divisible by p (i.e., gcd(a,p)=1):

a^(p−1) ≡ 1 (mod p).

These equivalent formulations are often presented together when introducing the result. The theorem is named after Pierre de Fermat and is one of several statements attributed to him about primes and powers. For a concise reference entry see theorem page, and for background on primes consult prime number resources.

Proof idea and history

Elementary proofs use combinatorial or group-theoretic arguments. One approach considers the nonzero residues modulo p and shows multiplication by a permutes those residues when gcd(a,p)=1, leading to the corollary a^(p−1) ≡ 1. Historically the result was noted by Fermat; later mathematicians provided clearer and more general frameworks, notably group theory and ring theory, that explain the theorem's place among related results.

Applications and examples

Fermat's little theorem is used in fast exponentiation algorithms, modular arithmetic simplifications, and as the basis of simple primality tests. Example: for p=7 and a=2, 2^7 ≡ 2 (mod 7) and therefore 2^6 ≡ 1 (mod 7). In practice, the theorem helps reduce large exponents modulo a prime.

Limitations and related results

Its converse is false: an integer n for which a^(n−1) ≡ 1 (mod n) for many a need not be prime; composite numbers that behave like primes in this way include Carmichael numbers. A classical generalization is Euler's theorem, which replaces p by any modulus and p−1 by Euler's totient function φ(n). For further reading see introductory texts or the linked entries above.