Power of Sum Modulo Prime

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $p$ be a prime number.

Then:

$\paren {a + b}^p \equiv a^p + b^p \pmod p$


Corollary

Let $p$ be a prime number.

Then:

$\paren {1 + b}^p \equiv 1 + b^p \pmod p$


Proof

From the Binomial Theorem:

$\ds \paren {a + b}^p = \sum_{k \mathop = 0}^p \binom p k a^k b^{p - k}$


Also note that:

$\ds \sum_{k \mathop = 0}^p \binom p k a^k b^{p-k} = a^p + \sum_{k \mathop = 1}^{p - 1} \binom p k a^k b^{p - k} + b^p$


So:

\(\ds \forall k: 0 < k < p: \, \) \(\ds \binom p k\) \(\equiv\) \(\ds 0\) \(\ds \pmod p\) Binomial Coefficient of Prime
\(\ds \leadsto \ \ \) \(\ds \binom p k a^k b^{p - k}\) \(\equiv\) \(\ds 0\) \(\ds \pmod p\) Definition of Modulo Multiplication
\(\ds \leadsto \ \ \) \(\ds \sum_{k \mathop = 1}^{p - 1} \binom p k a^k b^{p - k}\) \(\equiv\) \(\ds 0\) \(\ds \pmod p\) Definition of Modulo Addition
\(\ds \leadsto \ \ \) \(\ds \sum_{k \mathop = 0}^p \binom p k a^k b^{p - k}\) \(\equiv\) \(\ds a^p + b^p\) \(\ds \pmod p\) from above

$\blacksquare$


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Power_of_Sum_Modulo_Prime&oldid=593190"