# How to prove $\frac{(a_1 a_2\cdots a_n)^2-1}{8}\equiv\sum_{i=1}^n\frac{a^2_i -1}{8}\pmod 8$

Let $a_1,a_2,\cdots,a_n$ be odd numbers, show that

$$\frac{(a_{1}a_{2}\cdots a_{n})^2-1}{8}\equiv\sum_{i=1}^{n}\dfrac{a^2_{i}-1}{8} \pmod 8$$

Special cases

$n=1$: It is obvious that

$$\frac{a^2_{1}-1}{8}\equiv\dfrac{a^2_{1}-1}{8}\pmod 8$$

$n=2$

$$\dfrac{a^2_{1}a^2_{2}-1}{8}\equiv\dfrac{(2k-1)^2(2m-1)^2-1}{8}\equiv\frac{4k^2-4k+4m^2-4m}{8}=\dfrac{a^2_{1}+a^2_{2}-2}{8}\pmod 8?$$

where $a_{1}=2k-1,a_{2}=2m-1$ because $$(2k-1)(2m-1)^2-1=(4km-2k-2m+1)^2-1=(16k^2m^2-16k^2m-16km^2+8km+8km)+4k^2+4m^2-4k-4m+1-1$$ But in general I can't prove it.

-
Have you tried replacing $a_2$ by $a_2 \cdots a_n$ and do the same argument? – Patrick Da Silva Feb 9 '14 at 15:47
Yup, $n = 2$ is all you need. Then induction does the rest. – Daniel Fischer Feb 9 '14 at 15:47
If you write (\mod 8) you get $(\mod 8)$, but if you write \pmod 8 you get $\pmod 8$. (If there's more than one character after "mod", then you need braces: \pmod83 yields $\pmod83$, so write \pmod{83}, yielding $\pmod{83}$.) I edited the question accordingly. – Michael Hardy Feb 9 '14 at 18:31
You should probably mention that $a_1,a_2,\dots,a_n>1$. – barak manos Oct 5 '14 at 12:34

We prove the congruence by induction on the number of odd factors.

For $n = 1$, the congruence is even an equality, so the base case is settled.

Now assume that $n > 1$ and, as the induction hypothesis, that the congruence

$$\frac{\left(\prod_{k=1}^{n-1}a_k\right)^2 - 1}{8} \equiv \left(\sum_{k=1}^{n-1} \frac{a_k^2-1}{8}\right) \pmod{8}$$

holds for products of $n-1$ odd integers $a_k$.

The induction step then goes:

\begin{align} \frac{\left(\prod_{k=1}^n a_k\right)^2-1}{8} - \frac{a_n^2-1}{8} &= \frac{\left(\prod_{k=1}^n a_k\right)^2 - a_n^2}{8}\\ &= a_n^2\frac{\left(\prod_{k=1}^{n-1} a_k\right)^2-1}{8}\\ &\equiv \left(a_n^2\sum_{k=1}^{n-1} \frac{a_k^2-1}{8}\right) \pmod{8}\tag{IH}\\ &\equiv \left(\sum_{k=1}^{n-1} \frac{a_k^2-1}{8}\right) \pmod{8}, \tag{S} \end{align}

where IH denotes the induction hypothesis, and S the congruence $a_n^2\equiv 1 \pmod{8}$ holding for all odd integers. Rearranging yields the congruence in the desired form

$$\frac{\left(\prod_{k=1}^n a_k\right)^2-1}{8} \equiv \left(\sum_{k=1}^n \frac{a_k^2-1}{8}\right) \pmod{8}.$$

-
Can you explain between step 2 and 3 - turning the product $\prod$ into sum $\sum$? – john mangual Oct 6 '14 at 17:47
That's the induction hypothesis. We assume the congruence is satisfied for $n-1$ odd factors as the induction hypothesis. I'll add more explanation. – Daniel Fischer Oct 6 '14 at 17:50