Use induction to prove that if p is prime and $a_1, a_2, . . . , a_n$ are integers, then ...

Question

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!

Answer 1

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

Answer 2

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.