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

Status
Not open for further replies.

Chris L T521

Well-known member
Staff member
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.

Last edited:

Chris L T521

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

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

Status
Not open for further replies.