16
$\begingroup$

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!

$\endgroup$
6
  • 14
    $\begingroup$ 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$. $\endgroup$ Dec 17, 2012 at 21:41
  • 2
    $\begingroup$ 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. $\endgroup$ Dec 17, 2012 at 21:42
  • 1
    $\begingroup$ 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 ;) $\endgroup$ Dec 17, 2012 at 21:44
  • 6
    $\begingroup$ Why on earth do people downvote this so heavily? He's confused, but shows work, etc. Not cool. $\endgroup$ Dec 17, 2012 at 21:48
  • 3
    $\begingroup$ 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. $\endgroup$ Dec 17, 2012 at 22:06

2 Answers 2

16
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ 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. $\endgroup$ Dec 17, 2012 at 21:54
8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is a pretty cool proof to be honest! $\endgroup$
    – Denis
    Feb 5, 2022 at 9:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .