# A congruence involving prime numbers

This congruence appears in a textbook I'm reading anf it left the proof to the reader, however I cannot find my way around it.

$$(a+b)^ p \equiv a^p+b^p \pmod p\text{ when p prime and }a,b\in\mathbb{Z}$$

There are a few things that I considered to find a solution: (1) Show that the remainder of dividing $(a+b)^p$ and $p$ is $a^p+b^p$, but this would imply messy operations with the binomial theorem, (2) A former proposition proved that $x\equiv y\pmod k$ then $x^n\equiv y^n \pmod k$, I thought that the reciprocal may work but doesn't seem to be necessarily true since there is no guarantee that $\sqrt{a^p+b^p}\in\mathbb{Z}$.

My principal question here is, why $p$ needs to be a prime?. I tried to come with a counterexample for $p$ no prime: $(2+3)^4\not\equiv2^4+3^4=81\pmod 4$ because $(2+3)^4=625\equiv1\pmod 4$ (here I'm using that $4\cdot151=624)$. So it isn't true for any number, but why is this true for primes?

-
As long as you are in $\mathbb Z$, you even have $a^p\equiv p\pmod p$ (hence trivially $(a+b)^p\equiv a+b\equiv a^p+b^p$) –  Hagen von Eitzen May 11 '14 at 16:04
@HagenvonEitzen You meant $a^p\equiv a\pmod p$ (pointing it out to avoid confusion). –  user314 May 11 '14 at 16:25
As Hagen von Eitzen points out, this can simply be proved using the Fermat's Little Theorem twice. Someone should add this fact in their answer. And the OP should add that $a,b\in\mathbb Z$. –  user314 May 11 '14 at 16:32
Sometimes "messy operations" with the binomial theorem are the way to go! –  Geoff Robinson May 11 '14 at 16:41

So the binomial theorem gives $$(a + b)^p = \sum_{k=0} ^p \binom{p}{k} a^k b^{p-k}$$

Note that the binomial coefficient $\binom{p}{k}$ is divisible by $p$ unless $k=0$ or $k=p$. If instead we look at $\binom{n}{k}$ where $n$ is composite then it's no longer true that $n$ divides $\binom{n}{k}$ for all $k$. Look at, for example, $\binom{4}{2} = 6$.

The reason for this is simple: let $p$ be the smallest prime factor of $n$ and look at $$\binom{n}{p} = \frac{n!}{p!(n-p)!} = \frac{n \times (n-1) \times \cdots \times (n-p+1)}{p\times(p-1)\times\cdots2 \times 1}$$ then $n/p$ is an integer, call it $m$. So this equals $$\frac{m \times(n-1) \times \cdots \times (n-p+1)}{(p-1) \times \cdots \times 2 \times 1}$$ If this is divisible by $n$ then the numerator must be divisible by $n = m p$ and so $(n-1) \times \cdots \times (n-p+1)$ must be divisible by $p$. This cannot happen as $p \mid n$ and the next smallest multiple of $p$ is $n-p$. Therefore $n$ cannot divide $\binom{n}{p}$

-

Hint

Prove using the Euclid's lemma that for all $k\in\{1,\ldots,p-1\}$ we have $$p\;|{p\choose k}$$ and use the binomial theorem.

-

When $p$ is a prime, for any $a$ which is not divisible by $p$ we have $$a^{p-1} \equiv 1 \pmod{p}$$ because the multiplicative group of units modulo $p$ is a group of order $p-1$. This is known as Fermat's little theorem (read more on link).

For any $a$ we have $$a^p \equiv a \pmod{p}$$ (where $p$ is still our prime). If $a$ is a multiple of $p$, this is trivial (both sides are zero), otherwise it follows from $a^{p-1} \equiv 1 \pmod{p}$.

Therefore, your congruence is proved by: $$(a+b)^p \equiv a+b \equiv a^p+b^p \pmod{p}$$

Of course, if the statement $(a+b)^p\equiv a^p+b^p$ was an intermediate lemma on the route to a proof of Fermat's little theorem, then this post is not useful for you. See also Freshman's dream.

-

For primes, just use the binomial theorem and the fact that $\binom{p}{k}\equiv 0\pmod{p}$ whenever $0<k<p$.

-