# Homework Help: Number Theory with modular arithmetic

1. Sep 21, 2010

### CornMuffin

1. The problem statement, all variables and given/known data
When a is odd, show $$\frac{a^2-1}{8}$$ is an integer. Then prove by induction $$n \geq 2$$ that for all odd numbers $$a_1,a_2,...,a_n,$$

$$\frac{(a_1a_2...a_n)^2 - 1}{8} \equiv \frac{a^2_1 - 1}{8} + \frac{a^2_2 - 1}{8} + ... + \frac{a^2_n - 1}{8} \ mod \ 2$$

2. Relevant equations

3. The attempt at a solution
I proved that $$\frac{a^2-1}{8}$$ is an integer for odd a without much difficulty, but I am having trouble even proving the base case, n=2 for this.

From a previous problem, I already proved $$\frac{(a_1a_2...a_n) - 1}{2} \equiv \frac{a_1 - 1}{2} + \frac{a_2 - 1}{2} + ... + \frac{a_n - 1}{2} \ mod \ 2$$ for odd a. So I thought I might be able to use that and separate it into $$\frac{(a_1a_2...a_n) - 1}{2}$$ and $$\frac{(a_1a_2...a_n) + 1}{4}$$ but that didn't get me anywhere. I also tried representing the a's as 2k+1 for an integer k. But I just can't get anywhere.

Also, I figure that if I can prove that the left and right hand sides are both odd or both even, then I am done.

2. Sep 21, 2010

### Hurkyl

Staff Emeritus
Isn't

$$\frac{(a_1a_2...a_n)^2 - 1}{8} \equiv \frac{a^2_1 - 1}{8} + \frac{a^2_2 - 1}{8} + ... + \frac{a^2_n - 1}{8} \ mod \ 2$$

$$\frac{(b_1b_2...b_m) - 1}{2} \equiv \frac{b_1 - 1}{2} + \frac{b_2 - 1}{2} + ... + \frac{b_m - 1}{2} \ mod \ 2$$