The magic of mathematics and theoretical computer science is all the unexpected connections. You start looking for general principles and then mysterious connections emerge. Nobody can say why this is. — Robert Endre Tarjan

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.

Statement

For an integer and a prime , the following is true:

Proof

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

Therefore,

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 :

(Basis)

When , the statement trivially holds since .

(Inductive Hypothesis)

Suppose the above statement is true for . That is,

where . This implies,

.

(Induction)

We need to prove that where .

Now there can be two cases depending on whether divides .

[Case 1]

In this case, we can use the inductive hypothesis: .

Then,

Since , we can divide both sides by and thus arrive at
.

Now the second case.

[Case 2]

If divides , then

Therefore, for all primes and natural numbers , the following statement holds:
.

Yes! Thank you very much for pointing towards it. (Let me summarize the counting argument below. A nice presentation can be found here.)

Suppose we are making necklaces from beads. Each bead can be one of colors. Since we have no restriction on colors, there can be different bead-strings of length . Of these, only strings are single-colored. Let’s take them out: now we have strings left. Now let’s join the two ends of each of these strings to make a necklace. How many of these necklaces are unique? Only

because every unique necklace can be generated from different strings. Since the cardinality of any set is an integer, the cardinality of the set “unique non-monochromatic necklaces containing beads, each bead having one of colors” is also an integer. This implies that is an integer, or equivalently, is a multiple of .

As far as I can remember, there is also a nice combinatorial proof for this theorem 🙂

Yes! Thank you very much for pointing towards it. (Let me summarize the counting argument below. A nice presentation can be found here.)

Suppose we are making necklaces from beads. Each bead can be one of colors. Since we have no restriction on colors, there can be different bead-strings of length . Of these, only strings are single-colored. Let’s take them out: now we have strings left. Now let’s join the two ends of each of these strings to make a necklace. How many of these necklaces are unique? Only

because every unique necklace can be generated from different strings. Since the cardinality of any set is an integer, the cardinality of the set “unique non-monochromatic necklaces containing beads, each bead having one of colors” is also an integer. This implies that is an integer, or equivalently, is a multiple of .