# If $p$ is a prime and $x,y \in \mathbb{Z}$, then $(x+y)^p \equiv x^p+y^p \pmod{p}$

I want to prove that if $p$ is a prime and $x,y \in \mathbb{Z}$, then $$(x+y)^p \equiv x^p+y^p \pmod{p}$$

So far I know that $$(x+y)^p = \sum_{k=0}^{p} \dbinom{p}k x^{p-k} y^k$$

A part of the above equation is supposed to cancel, I think, but I can't figure out a way how to make it cancel.

-
Have you tried some examples for small values of $p$? –  Qiaochu Yuan Jul 8 '12 at 17:51
The result you are after is one standard way to prove Fermat's Theorem. But there are other ways o prove Fermat's Theorem. If one already has such a proof, then the result is an easy consequence, for $(x+y)^p\equiv x+y\equiv x^p+y^p\pmod{p}$. –  André Nicolas Jul 8 '12 at 18:08

HINT

If $p$ is a prime, then $p$ divides $\dbinom{p}{k}$ for all $k \in \{1,2,\ldots,p-1\}$.

The identity you have i.e. $(x+y)^p = x^p + y^p$, is referred to as Freshman's dream.

Note that $$\dbinom{p}{k} = \dfrac{p \times (p-1) \times (p-2) \times \cdots \times (p-k+2) \times (p-k+1)}{k \times (k-1) \times (k-2) \times \cdots \cdots \times 2 \times 1}$$ is an integer. Since $k \in \{1,2,\ldots,p-1\}$, and $p$ is a prime, none of $k, k-1, k-2, \ldots, 2$ divide $p$. Hence, we can factor $p$ from the numerator to get that $$\dbinom{p}{k} = \dfrac{p \times (p-1) \times (p-2) \times \cdots \times (p-k+2) \times (p-k+1)}{k \times (k-1) \times (k-2) \times \cdots \cdots \times 2 \times 1} = p \times M$$ where $M \in \mathbb{Z}$.