# 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$$ :

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