This is a beautiful theorem which states that the difference between a positive integer and a prime power of , , is divisible by . It’s history can be found in Wikipedia: Fermat posited the theorem (and as usual, did not give the proof) while Euler first published a proof using mathematical induction. Below, we will state the theorem and provide a simple-to-understand proof using only modular arithmetic, followed by another simple proof using mathematical induction.
For an integer and a prime , the following is true:
Note that if , the statement is trivially true. Therefore, we focus on the case that , that is, is a positive integer such that does not divide . (This also implies that .) In that case, we can divide both side of the main statement by and have the following statement:
Proving the above statement will complete the proof.
When we divide with prime , the remainder must be one of . Therefore, one of the following congruences must be true:
Now consider the numbers . These numbers are . We ask the following question: is it possible that two different numbers and be congruent modulo ? Let us find out. (Hint: we are going to use contradiction.)
Suppose when , we have and such that and yet . Since and , it follows that
Next, we have, due to our assumption, that
which contradicts . This implies, if , . Therefore each is congruent to a unique number . Thus the sequence of all numbers
is nothing but a rearrangement of the numbers
Since , by dividing both sides by it follows that
A Proof by Induction
We will prove that for a given prime , the following statement is true for all natural number such that does not divide :
When , the statement trivially holds since .
Suppose the above statement is true for . That is,
where . This implies,
We need to prove that where .
Now there can be two cases depending on whether divides .
In this case, we can use the inductive hypothesis: .
Since , we can divide both sides by and thus arrive at
Now the second case.
If divides , then
Therefore, for all primes and natural numbers , the following statement holds: