Blog | Anvar A.

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 Wikipedia¹, although I found this proof in an article posted by Fermat’s Library ².

Theorem (Fermat's Little Theorem)

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.

...