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.

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} \binom{p}{k} 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$. Dec 17, 2012 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. Dec 17, 2012 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 ;) Dec 17, 2012 at 21:44
• Why on earth do people downvote this so heavily? He's confused, but shows work, etc. Not cool. Dec 17, 2012 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. Dec 17, 2012 at 22:06

2 Answers

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. Dec 17, 2012 at 21:54

First of all, $$a^p \equiv a \pmod p$$ and $$b^p \equiv b \pmod p$$ implies $$a^p + b^p \equiv a + b \pmod p$$.

Also, $$(a+b)^p \equiv a + b \pmod p$$.

By transitivity of modulo, combine the above two results and get $$(a+b)^p \equiv a^p + b^p \pmod p$$.

Done.

• This is a pretty cool proof to be honest! Feb 5, 2022 at 9:44