Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Have you tried some examples for small values of $p$? –  Qiaochu Yuan Jul 8 '12 at 17:51
2  
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
add comment

1 Answer

up vote 3 down vote accepted

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.

Move your mouse over the gray area for the complete answer.

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

share|improve this answer
    
"Move your mouse over the gray area for the complete answer", eh? What's the point then? –  Gigili Jul 8 '12 at 17:04
7  
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
4  
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
3  
@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
4  
@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
show 7 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.