Number Theory: In Context and Interactive

Subsection 7.8.1 Counting motivation

In both cases we will have a natural question about objects situated on a circle, which may be naturally rotated by \(2\pi/n\) radian (or \(360/n\) degrees). Since such an object will certainly look the same after doing this rotation \(n\) times (\(2\pi\)/\(360\)°), we can call this a \(n\)-action, and call the initial rotation a basic \(n\)-rotation⁷.

In particular, we will want to look at classes of such objects that share some obvious similarity when rotated in this fashion. As an example, consider configurations of \(n\) equally spaced points around a circle, two separate pairs of which are connected by a line segment. You can think of this as ways of cutting a round birthday cake, using two cuts going between \(n\) equally-spaced candles along the edge⁸. Figure 7.8.1 shows a few examples for \(n=7\text{;}\) notice how the two cuts on the left are rotations of each other, while the others clearly are not.

Now consider any object of this type, and suppose the object looks the same after some smallest nonzero number \(k\leq n\) of basic \(n\)-rotations⁹. Then of course that will still be the case after another \(k\) of them, and so forth for any multiple \(km\) of \(k\text{.}\) But we also know that after \(n\) basic \(n\)-rotations the object is the same.

Now use the Division Algorithm. We have that \(n=kq+r\) for some \(0\leq r\lt k\text{.}\) Since we just noted the object is the same after \(kq\) basic \(n\)-rotations, then applying just \(r\) of them must also bring it back to its original configuration as well – except we said \(r\lt k\text{,}\) which is impossible by hypothesis unless \(r=0\text{.}\) So \(k\) must be a proper divisor of \(n\text{.}\)

That this is possible can be noted in Figure 7.8.2, where the left-hand cuts would now be preserved by a mere \(k=3\text{,}\) not only \(n=6\text{,}\) basic \(6\)-rotations.

But when \(n=p\) is prime, there are no proper divisors except \(1\) itself! So the only configurations which could be rotated non-trivially would be ones that are identical under any number of basic \(p\)-rotations at all.

Finally, that means that all the configurations which cannot be rotated non-trivially must generate \(p\) different configurations when rotated – configurations which are necessarily different from any others' rotations, so that they partition the set of all the configurations. This yields the key fact we will use in both proofs.

Subsection 7.8.2 The combinatorial proofs

Solomon Golomb provided the following creative proof of Fermat's Little Theorem as a classroom note¹⁰ in [E.7.41]. The proof is of the statement in the form we will see later in Exercise 9.6.3:

It has been reused in many texts and spread throughout the internet as the ‘pearl’ or ‘necklace’ proof¹¹.

Over a century ago, Robert Carmichael (whom we will meet again in Definition 12.2.9) gave the following very interesting proof¹². As Golomb points out in his article, it is of a very similar nature to the previous one, which motivates the unified presentation here.

We start with Carmichael's introduction.

Let \(p\) points be distributed at equal intervals on the circumference of a circle. The whole number of \(p\)-gons which can be formed by joining up these \(p\) points in every possible order is evidently

\begin{equation*} \frac{1}{2p}p(p-1)\cdots 3\cdot 2\cdot 1\text{.} \end{equation*}

Indeed, if we start by picking one of \(p\) starting points on the circle, then there are \(p!\) ways to join the rest in some order, but we then need to divide by the number of starting points of such a configuration, as well as the two directions we could have chosen to start. Further, to use Fact 7.8.3 we need to subtract the ones like the one on the left in Figure 7.8.4, of which there are \(\frac{p-1}{2}\) since from a starting point that is the number of distances (right or left) one can go to the next point (and from then on it continues identically so that any rotation will keep it unchanged).

So we have that

\begin{equation*} \frac{1}{2p}p(p-1)(p-2)\cdots 3\cdot 2\cdot 1 - \frac{1}{2}(p-1)\equiv 0 \text{ (mod }p)\text{;} \end{equation*}

multiplying by two and simplifying yields

\begin{equation*} (p-1)! - p+1\equiv 0 \text{ (mod }p) \end{equation*}

which immediately implies

\begin{equation*} (p-1)!\equiv -1 \text{ (mod }p) \end{equation*}

as desired.