A Simple Proof of a 400-Year Old Theorem about Numbers
Sometimes the simplest proofs give the best insights into how mathematicians think
--
Fermat’s Little Theorem is a beautiful number-theoretic result which states that, for any integer a and any prime number p, aᵖ﹣a is divisible by p. For example, if a = 4 and p = 3 then aᵖ﹣a = 60 which is divisible by 3.
Fermat first proposed this in a 1640 letter to a friend, but stated that he would not show a proof because it would take up too much space in the letter. Now, many of us know that Fermat had some history with his claims of having proofs that were just a little too long for his communication medium. The other time he made this claim, the problem didn’t get solved for about 350 years and needed over one hundred pages of some of the most complex mathematics in history.
In this case it didn’t take that long. The first published proof by Leonhard Euler (a consequence of Euler’s theorem) arrived within a century, and there is evidence that Leibniz had already proved it about 50 years earlier using pretty much the same method as Euler — he just never published the proof.
Many proofs of Fermat’s Little Theorem exist today — using a variety of methods such as multinomials, power products or group theory. But in this article I want to illustrate a really simple proof that I think is both a great example of how to solve a problem using first principles, and also a great illustration of how Pure Mathematicians think about discrete objects.
1. Permutations on ordered sets
Definition 1.1: Imagine you have a finite ordered set of objects S. We define a simple permutation on S as the removal of the object at the end of the set and the placing of that object at the beginning of the set.
Example 1.2: If S = {a,b,d,g,r,k} and T= {g,r,k,a,b,d} then T can be derived from three simple permutations on S.
Note that a series of simple permutations will eventually return the original ordered set. This will happen in the maximal case after l simple permutations, where l is the size of the set, but it can also happen sooner. For example, you can return {b,a,b,a} to itself after two simple permutations. However…
