5
$\begingroup$

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.

  • 1
    Have you tried some examples for small values of $p$?2012-07-08
  • 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}$.2012-07-08

1 Answers 1

3

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

  • 0
    "Move your mouse over the gray area for the complete answer", eh? What's the point then?2012-07-08
  • 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.2012-07-08
  • 0
    Would it be possible to prove it if I said something along the lines of "x^p+y^p would cancel by subtraction when k=o and k=p and ("k choose p") in the summation are multiples of p, therefore p would be a divisor" ?2012-07-08
  • 4
    Please don't fight. :) I found the gray area useful because I'd like to prove it myself with the hint.2012-07-08
  • 0
    @laser295 Each of the term $$\dbinom{p}k = p \times M_k$$ where $M_k \in \mathbb{Z}$. Hence, we get that $$\sum_{k=0}^p \dbinom{p}k x^{p-k} y^k = x^p + y^p + \sum_{k=1}^{p-1} \dbinom{p}k x^{p-k} y^k = x^p + y^p + \sum_{k=1}^{p-1} p M_k = x^p + y^p + p \times \left( \sum_{k=1}^{p-1} M_k\right) = x^p + y^p + p M$$ where $M \in \mathbb{Z}$. Hence, $(x+y)^p - x^p - y^p$ is a multiple of $p$.2012-07-08
  • 0
    @Marvis: That's what I am saying, If the OP is interested will hover over the grey part eventually, I don't see the point of saying to do so explicitly. It's a bit weird.2012-07-08
  • 0
    Sorry for being a little slow, but I'm confused as to what "M" is defined as.2012-07-08
  • 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?2012-07-08
  • 0
    Nevermind, I understand it now. Thanks so much for the help Marvis.2012-07-08
  • 0
    @Marvis: Funny, so as a new user you'd say "uh, what a nice large grey area at the end of the answer"? Your mouse will be there anyway and it'd be more exciting to find out on your own.2012-07-08
  • 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."2012-07-08
  • 0
    @AdriánBarquero: I have no problem with the use of grey area as a hint, I was just saying that sentence "Move your mouse over the gray area for the complete answer" sounded kind of killjoy. And you are making a mountain out of a molehill, I guess we all should think more before opening our mouth.2012-07-08