# Statement For any **prime number** $p$ and any integer $a$ we have $a^p \equiv a \text{ mod }p$ # Proof 1: By induction on $a$ (Proof written by Matt Jackson) **Lemma 1** For $1<i<p$, $\binom{p}{i} \text{ mod }p \equiv 0$ $\binom{p}{i} = \frac{p!}{i!(p-i)!}$ and the factor of $p$ in $p!$ cannot be dived out unless $i=0$ or $i=p$. Since $i\neq0$ or $p$, $\binom{p}{i} \text{ mod }p = 0$ and Lemma 1 is proven. **Lemma 2** $\left( (a+1)^p - (a+1) \right) \text{ mod }p \equiv \left( a^p -a \right)\text{ mod }p$ $(a+1)^p = \sum_{i=0}^p \binom{p}{i} a^{p-i}$ due the binomial expansion theorem. Due to Lemma 1, every term in the expansion is divisible by $p$ except for $a^p + 1$. $\therefore (a+1)^p \text{ mod }p = \left(a^p + 1\right)\text{ mod }p$ So $\left( (a+1)^p - (a+1) \right) \text{ mod }p \equiv \left( a^p + 1 -(a+1) \right)\text{ mod }p$. Condensing the previous statement, $\left( (a+1)^p - (a+1) \right) \text{ mod }p \equiv \left( a^p -a \right)\text{ mod }p$ $\therefore$ Lemma 2 is proven, and the statement of Fermat's little theorem is true for $a+1$ so long as it is true for $a$ **Lemma 3**. The statement Fermat's Little Theorem is true for $a=1$ $a^p - a = 0$ for $a=1$ $\therefore (a^p - a)\text{ mod }p\equiv 0$ and thus, Fermat's Little Theorem is true, for $a=1$, and Lemma 3 is proven. Due to a proof by induction for a base case of $a=1$ (proven by Lemma 3), and having proven the theorem for $a+1$ using Lemma 2, Fermat's Little Theorem is true for all $a\in\mathbb{N}$. (Note: Great job with this proof, Matt! --Mihai) # Proof 2: By combinatorics of the number of ways to make bracelets with $p$ beads in $a$ different colors.