Fermat's little theorem

Fermat's "biggest", and also his "last" theorem states that xⁿ + yⁿ = zⁿ has no solutions in positive integers x, y, z with n greater than 2.  This has finally been proven by Wiles in 1995.  However, in the study of primes it is Fermat's little theorem that is most used:

Fermat's Little Theorem.

Let p be a prime which does not divide the integer a, then a^p-1 = 1 (mod p).

It is so easy to calculate a^p-1 that most elementary primality tests are built using a version of Fermat's Little Theorem rather than Wilson's Theorem.

As usual, Fermat did not provide a proof (this time saying "I would send you the demonstration, if I did not fear its being too long" [Burton80, p79]).  Euler first published a proof in 1736, but Leibniz left virtually the same proof in an unpublished manuscript from sometime before 1683.

See Also: FermatQuotient

Related pages (outside of this work)

• Proof of this theorem
• Fermat's theorem, probable-primality and pseudoprimes