A congruence involving prime numbers

Question

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?

Answer 1

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

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 \begin{equation} \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} \end{equation} then $n/p$ is an integer, call it $m$. So this equals \begin{equation} \frac{m \times(n-1) \times \cdots \times (n-p+1)}{(p-1) \times \cdots \times 2 \times 1} \end{equation} 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}$

Answer 2

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.

Answer 3

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

Answer 4

This (obvious!) answer has already appeared in the comments to your question.

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.