3
$\begingroup$

Use induction to prove that if $p$ is prime and $a_1, a_2, . . . , a_n$ are integers, then $$(a_1 + a_2 + \cdots + a_n)^p\equiv a_1^p + a_2^p + \cdots + a_n^p \pmod p .$$

So I have proved before that $(a + b)^p\equiv a^p + b^p\pmod p$. I know I need to use this theorem and induction to prove the statement.

So for $n=1$, I can show that $(a_1)^p\equiv a_1^p \pmod p$. We assume for $n=k$ that the statement is true and we want to prove that the statement is true for $n=k+1$. So we have, $(a_1 + a_2 + \cdots + a_k + a_{k+1})^p$.

And this is where I'm stuck. I don't know how to apply the theorem for more than two terms. Thanks in advance for your help!

$\endgroup$
  • 5
    $\begingroup$ Hint: write $(a_1 + a_2 + \cdots + a_n)$ as $(a_1 + a_2 + \cdots + a_{n-1}) + a_n$. $\endgroup$ – Simon Marynissen Mar 7 '17 at 16:56
  • 3
    $\begingroup$ This should be straightforward. For instance, $(a+b+c)^p=((a+b)+c)^p\equiv (a+b)^p+c^p\pmod p$. $\endgroup$ – Andrés E. Caicedo Mar 7 '17 at 16:57
2
$\begingroup$

Consider two pieces of information that you have.

First, if $a$ and $b$ are integers, then $$(a+b)^p\equiv a^p+b^p\pmod p$$

Second, by the induction hypothesis, if $a_1,a_2,\dots,a_k$ are integers, then $$(a_1+a_2+\dots+a_k)^p\equiv a_1^p+a_2^p+\dots+a_k^p\pmod p$$

How can you arrange it so that you can apply one statement and then the other, given $$(a_1+a_2+\dots+a_k+a_{k+1})^p?$$

$\endgroup$
2
$\begingroup$

We have that $$(a_1 + a_2 + \ldots+ a_k + a_{k+1})^p = ((a_1 + a_2 + \ldots + a_k) + a_{k+1})^p$$ because of associativity of the addition. Since you already have that $(a+b)^p \equiv a^p + b^p \mod p$, you have that \begin{align} (a_1 + a_2 + \ldots+ a_k + a_{k+1})^p &\equiv ((a_1 + a_2 + \ldots + a_k) + a_{k+1})^p\\ & \equiv (a_1 + a_2 + \ldots + a_k)^p + a_{k+1}^p\\ & \equiv a_1^p + a_2^p + \ldots + a_k^p + a_{k+1}^p \mod p \end{align} where the last congruence follows from the induction hypothesis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.