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