A congruence involving prime numbers This congruence appears in a textbook I'm reading anf it left the proof to the reader, however I cannot find my way around it.
$$(a+b)^ p \equiv a^p+b^p \pmod p\text{ when $p$ prime and }a,b\in\mathbb{Z}$$
There are a few things that I considered to find a solution: (1) Show that the remainder of dividing $(a+b)^p$ and $p$ is $a^p+b^p$, but this would imply messy operations with the binomial theorem, (2) A former proposition proved that $x\equiv y\pmod k$ then $x^n\equiv y^n \pmod k$, I thought that the reciprocal may work but doesn't seem to be necessarily true since there is no guarantee that $\sqrt{a^p+b^p}\in\mathbb{Z}$.
My principal question here is, why $p$ needs to be a prime?. I tried to come with a counterexample for $p$ no prime: $(2+3)^4\not\equiv2^4+3^4=81\pmod 4$ because $(2+3)^4=625\equiv1\pmod 4$ (here I'm using that $4\cdot151=624)$. So it isn't true for any number, but why is this true for primes?
 A: Hint
Prove using the Euclid's lemma that for all $k\in\{1,\ldots,p-1\}$ we have
$$p\;|{p\choose k}$$
and use the binomial theorem.
A: So the binomial theorem gives
\begin{equation}
(a + b)^p = \sum_{k=0} ^p \binom{p}{k} a^k b^{p-k}
\end{equation}
Note that the binomial coefficient $\binom{p}{k}$ is divisible by $p$ unless $k=0$ or $k=p$. If instead we look at $\binom{n}{k}$ where $n$ is composite then it's no longer true that $n$ divides $\binom{n}{k}$ for all $k$. Look at, for example, $\binom{4}{2} = 6$. 
The reason for this is simple: let $p$ be the smallest prime factor of $n$ and look at
\begin{equation}
\binom{n}{p} = \frac{n!}{p!(n-p)!} = \frac{n \times (n-1) \times \cdots \times (n-p+1)}{p\times(p-1)\times\cdots2 \times 1}
\end{equation}
then $n/p$ is an integer, call it $m$. So this equals
\begin{equation}
\frac{m \times(n-1) \times \cdots \times (n-p+1)}{(p-1) \times \cdots \times 2 \times 1}
\end{equation}
If this is divisible by $n$ then the numerator must be divisible by $n = m p$ and so $(n-1) \times \cdots \times (n-p+1)$ must be divisible by $p$. This cannot happen as $p \mid n$ and the next smallest multiple of $p$ is $n-p$. Therefore $n$ cannot divide $\binom{n}{p}$
A: This (obvious!) answer has already appeared in the comments to your question.
When $p$ is a prime, for any $a$ which is not divisible by $p$ we have
$$a^{p-1} \equiv 1 \pmod{p}$$
because the multiplicative group of units modulo $p$ is a group of order $p-1$. This is known as Fermat's little theorem (read more on link).
For any $a$ we have
$$a^p \equiv a \pmod{p}$$
(where $p$ is still our prime). If $a$ is a multiple of $p$, this is trivial (both sides are zero), otherwise it follows from $a^{p-1} \equiv 1 \pmod{p}$.
Therefore, your congruence is proved by:
$$(a+b)^p \equiv a+b \equiv a^p+b^p \pmod{p}$$

Of course, if the statement $(a+b)^p\equiv a^p+b^p$ was an intermediate lemma on the route to a proof of Fermat's little theorem, then this post is not useful for you. See also Freshman's dream.
A: For primes, just use the binomial theorem and the fact that $\binom{p}{k}\equiv 0\pmod{p}$ whenever $0<k<p$.
