# 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}$.

-
"Move your mouse over the gray area for the complete answer", eh? What's the point then? –  Gigili Jul 8 '12 at 17:04
Whats the use of what? If the OP is interested in the complete answer, he will move the mouse over the gray area for the answer. –  user17762 Jul 8 '12 at 17:05
Please don't fight. :) I found the gray area useful because I'd like to prove it myself with the hint. –  laser295 Jul 8 '12 at 17:09
@Gigili I probably wouldn't have known that the gray area contained the answer as I do not frequent this website, so I guess it is helpful for the new people that come here? –  laser295 Jul 8 '12 at 17:18
@Gigili I do not understand what's your problem with the use of the gray area that Marvis employed in his answer. The OP has already said that he found it useful because he wanted to prove the result by himself before looking at the full answer. May I quote Abraham Lincoln here, "He has a right to criticize, who has a heart to help." –  Adrián Barquero Jul 8 '12 at 17:52