Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
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

1 Answer 1

up vote 5 down vote accepted
+50

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}.$$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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