Problem of the Week #61 - May 27th, 2013

[Chris L T521]

Thanks again to those who participated in last week's POTW! Here's this week's problem!

-----

Problem: Let $a,b\in\mathbb{Z}$, and let $p\in\mathbb{Z}^+$ be prime. Prove the "freshman's binomial theorem"; i.e. show that $(a+b)^p\equiv a^p+b^p\pmod{p}$.

-----

EDIT: I overlooked the fact that it isn't true for all positive integers (thanks Opalg). I've corrected the statement for this week's problem.

Remember to read the POTW submission guidelines to find out how to submit your answers!

 

[Chris L T521]

This week's problem was correctly answered by Bacterius, Opalg, and Sudharaka. You can find Bacterius' solution below:

Spoiler

Trivially, by Fermat's Little Theorem which states that for any prime $p$ and $x \in \mathbb{Z}$, $x^p \equiv x \pmod{p}$, it follows that:
$$(a + b)^p \equiv a + b \equiv a^p + b^p \pmod{p}$$
Alternatively, a combinatoric argument would go as follows:
$$(a + b)^p = \sum_{k = 0}^p \binom{p}{k} a^{p - k} b^k$$
Each term of the sum except $k = 0$ and $k = p$ is a multiple of $p$ due to the binomial term, therefore:
$$(a + b)^p \equiv \binom{p}{0} a^p b^0 + \binom{p}{p} a^0 b^p \equiv a^p + b^p \pmod{p}$$