Communicating Mathematics

Fermat's Little Theorem:

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 a^p-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

a^p-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

a^p-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 a^p-1 is so easy to calculate, that most primality tests are built using a version of this theorem.