Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 at 16:04
    
@HagenvonEitzen You meant $a^p\equiv a\pmod p$ (pointing it out to avoid confusion). –  mathh May 11 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$. –  mathh May 11 at 16:32
1  
Sometimes "messy operations" with the binomial theorem are the way to go! –  Geoff Robinson May 11 at 16:41
add comment

4 Answers 4

up vote 4 down vote accepted

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}$

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.