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.

a, b are integers. p is prime.
I want to prove:
$(a+b)^{p} \equiv a^p + b^p \pmod p$

I know about Fermat's little theorem, but I still can't get it
I know this is valid:
$(a+b)^{p} \equiv a+b \pmod p$
but from there I don't know what to do.

Also I thought about
$(a+b)^{p} = \sum_{k=0}^{p}\binom{p}{k}a^{k}b^{p-k}=\binom{p}{0}b^{p}+\sum_{k=1}^{p-1}a^{k}b^{p-k}+\binom{p}{p}a^{p}=b^{p}+\sum_{k=1}^{p-1}\binom{p}{k}a^{k}b^{p-k}+a^{p}$
Any ideas?

Thanks!

share|improve this question
8  
By Fermat's Theorem, $a^p\equiv a$, $b^p\equiv b$, so with your observation that $(a+b)^p\equiv a+b$, you are finished. If we don't want to use Fermat, show that the binomial coefficients are divisible by $p$. –  André Nicolas Dec 17 '12 at 21:41
2  
both techniques almost work. And generally, when you offer money for a solution, most people think you are taking a test. Not sure if it is a terms of service thing. –  Thomas Andrews Dec 17 '12 at 21:42
1  
I think people here prefer reputation points to small amount of money. Setting bounties is a better idea but it comes with a small caveat.... You should garner some reputation points before you can give it away ;) –  Isomorphism Dec 17 '12 at 21:44
5  
Why on earth do people downvote this so heavily? He's confused, but shows work, etc. Not cool. –  gnometorule Dec 17 '12 at 21:48
3  
Thanks. I edited out. The test is tomorrow, is why I gave 12hs. (thought none would answer) I didn't know about the dynamic behind the site, now that makes sense ^^. Thanks André! Didn't remembered about the transitive property of congruence relations. $(a+b)^{p} \equiv a+b$ and $a+b \equiv a^{p}+b^{p}$ so $(a+b)^{p} \equiv a^{p}+b^{p}$. =) Apologies if someone got offended by the bounty. –  Florencia Hoffmann Dec 17 '12 at 22:06

1 Answer 1

up vote 6 down vote accepted

Your second idea is good, so let's work a little bit on it: We have that $(a+b)^p=a^p+b^p+\sum\limits_{k=1}^{p-1}{p\choose k}a^{k}b^{p-k}$. Obviously it is enough to show that each term of this sum is divisible by $p$ in order to get that the whole sum is $\equiv 0\mod p$.

So why is that the case? For $1\leq k\leq p-1$ we have that ${p\choose k}=\frac{p\cdot (p-1)!}{k!(p-k)!}$ and since $p$ is prime, no factor in the denominator divides $p$, so the denominator does not divide $p$ at all: Hence we have that already $\frac{(p-1)!}{k!(p-k)!}$ is integer and so $p\mid{p\choose k}$. Of course then ${p\choose k}a^kb^{p-k}$ is divisible by $p$ and hence the whole sum is too.

share|improve this answer
2  
Note that this is really much better than using Fermat because $(a+b)^p=a^p+b^p$ holds in all fields of characteristic $p$, hence even in cases where Fermat itself would not apply. –  Hagen von Eitzen Dec 17 '12 at 21:54

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.