Fermat's Little Theorem
August 2, 2024
This is an oldie, but a cute little trick to solving Fermat’s Little Theorem that I came across back when I was an undergraduate. This is a well known proof and can be found in Wikipedia1, although I found this proof in an article posted by Fermat’s Library 2.
Theorem
(Fermat's Little Theorem)
If $p$ is a prime number and $p \nmid n$ for $n \in \mathbb{N}$, then $n^p \equiv n \mod p$.
Proof
Let’s say that you want to make as many distinct types of necklaces as you can with $p$ (colourless) beads at your disposal, and where you can colour each bead with $n$ different colours. Assume also you only want to make multi-coloured necklaces, and that $p$ is prime.
...