3
$\begingroup$

I am having trouble proving that any prime number $p$ and integers $a$ and $b$,

$(a+b)^{p} \equiv a^{p} + b^{p} \pmod{p}$

$\endgroup$
2
  • 1
    $\begingroup$ Do you know binomial expansion? $\endgroup$ Dec 1, 2014 at 9:44
  • $\begingroup$ Freshman's dream. It is difficult to answer this suitably without knowing your approximate level. High school? Freshman? $\endgroup$ Dec 1, 2014 at 10:40

2 Answers 2

7
$\begingroup$

The binomial theorem says that $$(a + b)^n = \sum_{k=0}^n \binom{n}{k}a^k b^{n-k}.$$ When $n$ is prime, then for every $0 < k < n$ we have $$\binom{n}{k} = \frac{n!}{k!(n-k)!} = n\frac{(n-1)!}{k!(n-k)!}$$ because nothing in the denominator divides $n$. So all of the middle terms in the expansion of $(a + b)^p$ vanish modulo $p$, and you're left with the two ends: $a^p + b^p$.

$\endgroup$
7
$\begingroup$

By Fermat's Little Theorem, if $c\in \mathbb{Z}$ and $p$ is prime, then $c^p\equiv c \mod p$.

So, since $(a+b)\in \mathbb{Z}$ and $p$ is prime, $(a+b)^p\equiv (a+b) \mod p$

Also, since $a\equiv a^p \mod p$ and $b \equiv b^p \mod p$ (by Fermat's Little Theorem), we know that $a+b\equiv a^p+b^p \mod p$.

Thus $(a+b)^p \equiv a^p +b^p \mod p$.

$\endgroup$

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