A basic theorem in elementary number theory which asserts that for a prime p and integer a with p not dividing a, one has a^{p-1} ≡ 1 (mod p); equivalently a^p ≡ a (mod p) for all integers a.

Principle

The multiplicative group of integers modulo a prime p is cyclic of order p−1, so any element a with gcd(a,p)=1 has order dividing p−1, yielding the congruence a^{p-1} ≡ 1 (mod p).

Demonstration

For example with a=2 and p=7, 2^6 = 64 ≡ 1 (mod 7). A group-theoretic proof uses that {1,a,a^2,...,a^{p-2}} permutes the nonzero residue classes modulo p, so multiplying gives a^{p-1} ≡ 1.

Misapplication

Using the congruence to test primality as a biconditional: composite numbers can satisfy a^{n-1} ≡ 1 (mod n) for some a (Carmichael or pseudoprimes), and the theorem fails when gcd(a,p) ≠ 1.

Consequence

Forms the basis of many modular arithmetic arguments, simple primality tests and algorithms, and generalizes to Euler's theorem for composite moduli via Euler's totient function.

Reversal

The naive converse 'if a^{n-1} ≡ 1 (mod n) for many a then n is prime' is false; the correct reversal is that failing the congruence for some a certifies compositeness, but passing it does not guarantee primality.

Boundary

Requires p to be prime and gcd(a,p)=1 for the a^{p-1} ≡ 1 formulation; the variant a^p ≡ a holds for all a mod p. It does not apply to composite moduli without replacing p−1 by φ(n).

Semantic Tension

Often conflated with Euler's theorem and with probabilistic primality tests; tension arises between the deterministic congruence and the existence of pseudoprimes that mimic prime behavior for many bases.

Synthesis

Fermat's Little Theorem connects the algebraic structure of the multiplicative residues modulo a prime with simple congruences: invertible residues have order dividing p−1, yielding a^{p-1} ≡ 1 (mod p) and powerful applications in number theory.