# Showing a congruence

How do we show that $(a_1+...+a_n)^2=(a_1^2+...+a_n^2)\mod 2$?

I can see that this works when there are two terms, but I have trouble visualizing the left hand expansion with infinite terms. I guess this could call for a proof by induction, but once I assume this is true for some $k$, I have no clue how to proceed for the $k+1$ case.

Just some tips or ideas would be appreciated.

-
You could simply note that $x\equiv x^2 \mod 2$. – Alex Becker Sep 27 '12 at 0:33

Two cases to check:

(i) The number of odd $a_i$ is even.

(ii) The number of odd $a_i$ is odd.

Both cases are straightforward. In case (i), the sum of the $a_i$ is even, as is the sum of the $a_i^2$. This is because $x^2$ is odd iff $x$ is odd. Case (ii) is similar.

More algebraically, square the left-hand side. The "cross" terms are of the form $2a_ia_j$, so are congruent to $0$ modulo $2$.

-
took me a little to properly understand the odd and even arguments, but i think they are much more elegant than the binomial expansion method! thanks for the insight. – MSEoris Sep 27 '12 at 1:06

Use $(\sum a_i)^2=\sum a^2_i+2\sum_{i<j} a_ia_j$.

-

You don’t have to worry about an infinite number of terms: that’s not allowed. You mean that you don’t know how to deal with an arbitrary finite number of terms.

You can do it by induction:

\begin{align*} (a_1+\ldots+a_n+a_{n+1})^2&=\Big((a_1+\ldots+a_n)+a_{n+1}\Big)^2\\\\ &=(a_1+\ldots+a_n)^2+2a_{n+1}(a_1+\ldots+a_n)+a_{n+1}^2\\\\ &\equiv a_1^2+\ldots+a_n^2+a_{n+1}^2\pmod2\;, \end{align*}

by the induction hypothesis that $(a_1+\ldots+a_n)^2\equiv a_1^2+\ldots+a_n^2\pmod2$, since $2a_{n+1}(a_1+\ldots+a_n)\equiv0\pmod2$.

-