3
$\begingroup$

How would I go about proving that for all $a, b \in \mathbb{Z} \pmod p$ where $p$ is prime, $$(a+b)^p = a^p + b^p$$

Also I was wondering if there was an intuitive way to think about and visualize exponentiation in modular arithmetic.

$\endgroup$
1
  • $\begingroup$ The binomial-coefficients appearing in the formula for $(a+b)^p$ are all divisible by $p$ except $\binom{p}{p}=1$ and $\binom{p}{0}=1$. To see that consider that the numerator is always $p!$ and the denominator is a product of factorials of numbers smaller than $p$, hence the denominator cannot be divisible by $p$ $\endgroup$
    – Peter
    Oct 9, 2017 at 20:10

3 Answers 3

9
$\begingroup$

If you use $n^p\equiv n\bmod p$ you can write $$(a+b)^p\equiv a+b\equiv a^p+b^p$$ and all you need is Fermat's little theorem.

$\endgroup$
4
  • $\begingroup$ Yeah, also good to use Fermat's little theorem since $p$ is prime. $\endgroup$
    – Zhuoran He
    Oct 9, 2017 at 20:16
  • $\begingroup$ Much better than using the binomial theorem. $\endgroup$ Oct 9, 2017 at 20:34
  • $\begingroup$ Thank you! I was unaware of this theorem until now. $\endgroup$ Oct 9, 2017 at 21:17
  • $\begingroup$ Nice and simple proof! Is there the equivalent for $\mathbf F_{p^r}$? $\endgroup$
    – Bernard
    Oct 9, 2017 at 21:44
5
$\begingroup$

Use the binomial theorem to expand the left-hand side. All other terms except $a^p$ and $b^p$ are multiples of $p$. So $(a+b)^p$ and $a^p+b^p$ are congruent in $\mathbb{Z}_p$. You can see this from

$$(a+b)^p=a^p+pa^{p-1}b+{p\choose 2}a^{p-2}b^2+\cdots+{p\choose p-1}ab^{p-1}+b^p.$$

To know why $p\choose r$ for all $r\in[1,p-1]$ are multiples of $p$, see Lucas's theorem: https://en.wikipedia.org/wiki/Lucas%27s_theorem

$\endgroup$
1
  • $\begingroup$ This is another interesting approach, thank you! $\endgroup$ Oct 9, 2017 at 21:19
1
$\begingroup$

Hint:

The binomial formula is valid in any commutative ring, so all you have to prove is that $$\forall k, \;0<k<p\implies \binom pk\equiv 0\mod p.$$ Remember the recursion formula: $$\forall k,\; k>0\implies\binom nk=\frac nk\binom{n-1}{k-1}$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .