As I was looking through different proofs to use for my communicating mathematics post, I came across a proof that I had never even heard of before. This proof was called Fermat’s Little Theorem, which is not to be confused with Fermat’s Last Theorem. This proof states the following
Let p be a prime number which does not divide the integer a, then ap-1 = 1(mod p).
True to Fermat’s form, a proof of this was not provided. Euler was the first to finish and publish the proof. Although a proof almost identical to Euler’s was found in a manuscript of Leibniz fifty years prior to that of Euler.
To begin this proof, we will list the first p-1 multiples of a, which looks like this:
a, 2a, 3a, … (p-1)a
After this, assume that we have some ra and sa that are the same modulo p. This means that we can conclude
r = s(mod p)
and also the p-1 multiples of a above are distinct and nonzero. This means that they must be congruent to 1, 2, 3, … ,(p-1) in some way. The next step of this proof is to multiply each of these congruencies together in order to obtain the following
a*2a*3a*…*(p-1)a = 1*2*3*…*(p-1)(mod p).
We can further simplify this as the following
ap-1(p-1)! = (p-1)!(mod p)
Now, the last step of this proof is to divide each by (p-1)!. By doing this, we can see that we will get
ap-1 = 1(mod p)
This is exactly what we were trying to show. Therefore, we have just proved Fermat’s Little Theorem.
Fermat’s Little Theorem is important to math because ap-1 is so easy to calculate, that most primality tests are built using a version of this theorem.