Home
Search Site
Largest
The 5000
Top 20
Finding
How Many?
Mersenne
Glossary
Prime Curios!
Prime Lists
FAQ
email list
Titans
Submit primes

Fermat's "biggest", and also his "last" theorem states that x^{n}
+ y^{n} = z^{n} has no solutions in positive integers
x, y, z with n > 2. This has finally been proven by Wiles
in 1995. Here we are concerned with his "little" but perhaps his most
used theorem which he stated in a letter to Fre'nicle on 18 October 1640:
 Fermat's Little Theorem.
 Let p be a prime which does not divide the integer a,
then a^{p1} = 1 (mod p).
It is so easy to calculate a^{p1} 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.
 Proof.

Start by listing the first p1 positive multiples of
a:
a, 2a, 3a, ... (p 1)a
Suppose that ra and sa are the
same modulo
p, then we have r = s (mod p), so the
p1 multiples of a above are distinct and nonzero; that is,
they must be congruent to 1, 2, 3, ..., p1 in some order.
Multiply all these congruences together and we find
a^{.}2a^{.}3a^{.}...^{.}(p1)a
= 1^{.}2^{.}3^{.}...^{.}(p1) (mod p)
or better,
a^{(p1)}(p1)! = (p1)! (mod p).
Divide both side by (p1)! to complete the proof.
Sometimes Fermat's Little Theorem is presented in the following form:
 Corollary.
 Let p be a prime and
a any integer,
then a^{p} = a (mod p).
 Proof.

The result is trival (both sides are zero) if p divides
a. If p does not divide a, then we need only
multiply the congruence in Fermat's Little Theorem by a to
complete the proof.
