Fermat’s Little Theorem

Math NT

Fermet’s Little Theorem

If $p$ is a prime integer:

$$\begin{gathered} a^{p-1}\equiv 1\mathrm{mod}p \\ {a}^p\equiv a\mathrm{mod}p \end{gathered}$$ $$\begin{gathered} a^{p-1}\equiv 1\mathrm{mod}p \\ {a}^p\equiv a\mathrm{mod}p \end{gathered}$$

Proof

Let $p$ be a prime integer. Say a necklace has $p$ beads and $a$ possible colors per bread. Except for a necklace with only one color, each combination of necklace colors has $p$ permutations. Therefore:

$$a^p\equiv a\mathrm{mod}p$$