Show that for any integer a and prime p, $(a+1)^p \equiv a^p+ 1 \pmod{p}$. I believe that this may require the use of Fermat's Little Theorem. I rewrote it as $(a+1)^p - a^p \equiv 1 \pmod{p}$ because the right-hand side looks similar to Fermat's Little Theorem, but I was unable to figure out how I can get the left-hand side to become $a^{(p-1)}$.  
 A: Hint: 
Expanding $(a+1)^p$ you get $\sum_{k=0}^{k=p}\binom{p}{k}a^k$. Now first prove that $p\mid\binom{p}{k}$, when $0<k\le p-1$ and $p$ is prime. After that you will left with $a^p+1\pmod{p}$. 
A: $$(a+1)^{p}=_{0}^{p}\textrm{C}(a)^{p}+_{1}^{p}\textrm{C}(a)^{p-1}.......+1$$
in each combination you will get "prime p" in multiplication,but you are working under mod(p) so all the terms became zero except $$a^{p}+1$$ and this is your answer
A: Hint 1:

 $$(a+1)^p=\sum_{i=0}^{p}a^i\binom{p}{i}$$

Hint 2:

 What is $\binom{p}{i}~\text{mod}~p$?

A: Hint $ $ Use little Fermat to show $\,\color{#c00}n^p \equiv \color{#c00}n\pmod{\!p}\, $ for all $\,n\,$ (separate into cases $\,n\equiv 0\,$ or not), then  use that to show $\,(a+1)^p$ and $\,a^p+1\,$ are both $\,\equiv a+1\pmod{\!p}\ $ [by specializing $\,\color{#c00}n \equiv a+1\,$ and $\,\color{#c00}n\equiv a,\,$ above, while using the Congruence Power Rule].
A: Note:  If $p$ is prime and $p|a$ then $a\equiv 0\pmod p$ and $a^p \equiv 0 \equiv a \pmod p$.
And if $p \not \mid a$ then $a^{p-1}\equiv 1 \pmod p$ by FLT.
So $a^p = a^{p-1}a \equiv a \pmod p$.
So for any integer $a^p \equiv a \pmod p$ whether or not $p\mid a$.
.....
So $(a+1)^p \equiv a+1 \pmod p$.
And $a^p + 1\equiv a+1 \pmod p$.
That's it.
