The statement, and sketches of the usual proofs
Fermat's little theorem states that if is a prime and is an integer not divisible by , then is congruent to .
One proof is to note that x can be regarded as an element of the multiplicative group of non-zero residue classes ( ). It generates a cyclic subgroup, and the order of that subgroup is the minimal r such that . By Lagrange's theorem, this must divide , from which the theorem readily follows.
Another proof is to deal with a modified statement: that for every .