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

 Definition

A number-theoretic statement that if p is prime and a is an integer not divisible by p, then a^{p−1} ≡ 1 (mod p); equivalently a^p ≡ a (mod p) for all integers a.

 

 

 

 

 

 





## Principle

Principle

Units modulo a prime form a finite multiplicative group of order p−1, so every unit's order divides p−1, forcing a^{p−1} to be the identity in that group.

 

 

 

 

 





## Demonstration

Demonstration

For p=7 and a=3, compute 3^6 = 729, and 729 ≡ 1 (mod 7), illustrating the theorem's congruence in a concrete case.

 

 

 

 

## Misapplication

Misapplication

Using the congruence a^{n−1} ≡ 1 (mod n) as a primality test without care: many composite n (Carmichael or Fermat pseudoprimes relative to a) can satisfy the congruence for some or all a, producing false positives.

 

 

 

 

 





## Consequence

Consequence

Underpins simple modular inverse computations and many primality heuristics; it is a base case for Euler's theorem and for constructions in elementary cryptographic protocols when modulus is prime.

 

 

 

 

## Reversal

Reversal

The converse fails: if a^{n−1} ≡ 1 (mod n) for some a coprime to n, n need not be prime. Studying the reversal leads to pseudoprimes, Carmichael numbers, and stronger primality criteria like Euler or strong probable-prime tests.

 

 

 

 

 





## Boundary

Boundary

Applies only when modulus is prime in its classical form, and requires gcd(a,p)=1 for the multiplicative-group statement; it does not hold for arbitrary composite moduli without extra hypotheses.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Sits adjacent to Euler's theorem (which replaces p−1 by φ(n)) and to probabilistic primality tests; tension arises between exact algebraic group facts and heuristic use in primality testing where exceptions exist.

 

 

 

 

 





## Synthesis

Synthesis

Fermat's Little Theorem captures the group-theoretic fact that the multiplicative group modulo a prime is cyclic of order dividing p−1, giving a simple congruence that seeds generalizations and tests in modular arithmetic.