A common form of Fermat's Little Theorem is: $a^{p}=a$ (mod $p$), for any prime $p$ and integer $a$. Prove this by induction on $a$.
I tried to prove that $(a+b)^p= a^p+b^p$ (modulo $p$) since it's a more general statement, but couldn't get further.
Best Answer
$(a+1)^P=a^p+ \binom{p}{1} a^{p-1} +\binom{p}{2}a^{p-2}+.....+ \binom{p}{p-1}a+1.$
Note that $p$ divides into any binomial coefficient of the form $\binom{p}{k}$ for $1 \le k\le p-1$
This follows by the definition of the binomial coefficient as $\binom{p}{k}= \left(\frac{p!}{k!(p-k)!}\right)$; since $p$ is prime, then $p$ divides the numerator but not denominator.
Taken mod $p$, all of the middle terms disappear, and we end up with
$(a+1)^p\equiv a^p +1$ (mod $p$). Since we also know that $a^p\equiv a$ (mod $p$)
$(a+1)^p\equiv a +1$ (mod $p$). As we needed