NTIC Counting Proofs of Congruences

Section 7.8 Counting Proofs of Congruences

Some number theoretic results require essentially no number theory for their proof, but may be tackled using basic ideas from combinatorics, the discipline of counting well. The essential idea in all of these types of proofs is to find two (or more) ways to count something you care about; with skill (or luck), equating these will lead to an algebraic formula that might be quite challenging to verify with mere manipulation. Although in this text we do not really address partitions, additive number theory, or other beautiful combinatorial elements of the discipline, it is worth showing two classic proofs, by counting pictures, of the classic theorems in Section 7.5. Both appear in [E.2.11], where I learned of them, though they are both significantly older. In this section, I will try to put them in a unified context in an attempt to lend insight.

🔗

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 π / n

radian (or

360 / n

degrees). Since such an object will certainly look the same after doing this rotation

n

times (

2 π

360

°), we can call this a

n

-action, and call the initial rotation a basic

n

-rotation⁷.

This notation is not standard, and is only for use in this section.

🔗

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;

notice how the two cuts on the left are rotations of each other, while the others clearly are not.

I don't recommend using this at an actual party, since the three or four pieces will likely be quite unequal in size and shape.

Several configurations of two lines on a $7$-point circle — 🔗
Figure 7.8.1. Several configurations of two lines on a $7$ -point circle

🔗

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

k m

k .

But we also know that after

n

basic

n

-rotations the object is the same.

That such a number exists is guaranteed by the Well-Ordering Principle as usual.

🔗

Now use the Division Algorithm. We have that

n = k q + r

for some

0 \leq r < k .

Since we just noted the object is the same after

k q

basic

n

-rotations, then applying just

r

of them must also bring it back to its original configuration as well – except we said

r < k,

which is impossible by hypothesis unless

r = 0 .

k

must be a proper divisor of

n .

🔗

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,

not only

n = 6,

basic

6

-rotations.

Several configurations of two lines on a $6$-point circle — 🔗
Figure 7.8.2. Several configurations of two lines on a $6$ -point circle

🔗

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.

🔗

Fact 7.8.3.

If $p$ is prime, then the set of configurations which change non-trivially under a basic $p$ -rotation can be divided into subsets, each of size $p .$ So $p$ divides the size of this set.

🔗

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:

a^{p} \equiv a (mod p) .

🔗

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

Thanks to JSTOR, you can access the original publicly at https://www.jstor.org/stable/2309563. On a side note, it is amazing today to think that a professor at MIT was the editor of the classroom notes section of the Monthly in 1956. Times have changed.

It is worth noting that the case $n=2$ may be thought of stating a fact about musical chords on a $p$-note scale; see this excellent introduction if you know a little group theory.

🔗

Combinatorial proof of Theorem 7.5.3.

Suppose that at each of $p$ equally spaced points around a circle we have a different color bead, with $a$ colors available. “Since each of the beads can be chosen” in $a$ different ways, there are $a^p$ possible colorings.

However, if we use only one color of bead, then that coloring doesn't change under a basic $p$-rotation. So the total number of relevant configurations in Fact 7.8.3 is $a^p-a\text{,}$ which implies that $p\mid a^p -a$ or

\begin{equation*} a^p\equiv a\text{ (mod }p)\text{.} \end{equation*}

🔗

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.

The textbook it occurs in is now available freely via Project Gutenberg of Wilson's Theorem.

🔗

Combinatorial proof of Theorem 7.5.1.

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).

Figure 7.8.4. Connecting $7$ points on a circle various ways

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.

🔗

Remark 7.8.5.

For those who know a little graph theory, this proof may be streamlined. The number of directed cyclic graphs on these points is $(p - 1)!,$ and similarly there would be exactly $p - 1$ directed cyclic graphs which remain unchanged under a basic $p$ -rotation.

🔗

Remark 7.8.6.

As a note to instructors, though we do not define group actions in this text, of course a $n$ -action is really a $Z_{n}$ -action, using the terminology of Definition 8.1.1. Indeed, these computations are all just special cases of the Burnside Lemma/Cauchy-Frobenius Theorem, but without the annoyance of having to actually compute very many fixed points, and without the bother of determining the number of orbits.

🔗

These are certainly not the only combinatorial proofs of congruences. See [E.7.27] for a recent proof of Wilson's Theorem using two different ways of counting the functions of the set

{1, 2, \dots, p}

onto itself. Like many presentations of these two theorems, it uses Fermat's Little Theorem to prove Wilson's Theorem, rather than the other way around as we did it in Section 7.5.

🔗

Golomb only asks what we (and [E.2.11]) show explicitly; where did we use that

p

is prime? It is of course in the division algorithm, when finding how many basic

n

-rotations suffice to preserve the figure. The beauty of the proofs in this section is that they rely directly only on the division algorithm and primality, nothing more.