Proof by Necklaces

A proof of Fermat’s Little Theorem using necklaces.

\(a^{p-1} \equiv 1 \pmod p\),

where \(p\) is prime and \(a\) is any integer with gcd\((a,p) = 1\).

 

Multiply both sides of the congruence by \(a\) :

\(a\cdot a^{p-1} \equiv a \pmod p\)

Which gives :

\(a^p \equiv a \pmod p\)

Subtract \(a\) from both sides :

\(a^p-a \equiv 0 \pmod p\)

This says that \(p | a^p-a\),  that is,  \(p\) divides \(a^p-a\) exactly.

 

For a necklace of \(p\) beads with the choice of \(a\) colours, there are \(a^p\) permutations of which exactly \(a\) consist of only one colour and \(a^p-a\) consist of up to \(a\) colourings.

For example, when \(p = 5\) and \(a = 2\) :

OldTrout, Going Postal

We have one necklace of blue beads and one necklace of orange beads.

We can arrange the other \(a^p-a\) permutations into different necklaces by using \(p\) rotations.

OldTrout, Going Postal

Thus the number of different necklaces, \(n\), is :

\(\displaystyle n = \frac{a^p-a}{p} + a \)

From our example we have :

\(\displaystyle n = \frac{2^5-2}{5} + 2 = \frac{30}{5} + 2 = 8\)

Another example, for \(p = 7\) and \(a = 3\) :

\(\displaystyle n = \frac{3^7-3}{7} + 3 = \frac{2187-3}{7} + 3 = 312 + 3 = 315\)

 

This should come as no surprise since Fermat’s Little Theorem is a special case of Euler’s Totient Function.

The numbers may be checked using the cycle index polynomial given in The Cyclic Group of a Necklace.
 

© OldTrout \(2018\)
 

No Audio file – it does not translate well