Welcome to our community

Be a part of something great, join today!

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

Status
Not open for further replies.
  • Thread starter
  • Moderator
  • #1

Chris L T521

Well-known member
Staff member
Jan 26, 2012
995
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!
 
Last edited:
  • Thread starter
  • Moderator
  • #2

Chris L T521

Well-known member
Staff member
Jan 26, 2012
995
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.