# Proof for: $(a+b)^{p} \equiv a^p + b^p \pmod p$

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.

$(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!

-
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
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
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
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
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

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