##  [Fermat's Little Theorem](/fermats-little-theorem-1) 

 Definition

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

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

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

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

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

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

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

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

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.