# Prove that if $x$ is odd then $x^2 -1$ is divisible by $8$.

If $x$ is odd then prove that $x^2-1$ is divisible by $8$.

I start by writing: $x = 2k+1$ where $k\in\mathbb{N}$.

Then it follows that: $(2k+1)^2 -1 = 4k^2 +4k + 1 -1$

Therefore: $$\frac{4k^2 +4k}{8} = \frac{k(k+1)}{2}$$ At the end part I can see that for what $k$ is, the number on top is divisible by 2. I was expecting the end result to be a number, not a fraction. Or is it "divisible" from the definition $\text{even} = 2k$ that completes the proof?

-
Yes, your proof is good enough. In the product $k(k+1)$, exactly one of $k$ and $k+1$ is always even. Thereby, the product is divisible by 2. – TenaliRaman Nov 22 '12 at 10:31
If you want a more "convincing answer", notice that all odd numbers are of the form $4k + 1$ or $4k + 3$. Substitute, these into $x^2 - 1$ and you should get expressions which would be directly multiples of 8. – TenaliRaman Nov 22 '12 at 10:33
If $k$ is odd $=2m+1$(say), $\frac{k(k+1)}2=(2m+1)(m+1)$. If $k$ is even$=2m$(say), $\frac{k(k+1)}2=m(2m+1)$ – lab bhattacharjee Nov 22 '12 at 13:19

An easier way to approach this would be to observe: If x is odd, either x-1 or x+1 is divisible by 4. Then their product is divisible by 8.

-
+1 Nice answer, but perhaps you should rephrase it as "If $x$ is odd, then exactly one of $x-1$ and $x+1$ is divisible by $4$ and the other is divisible by $2$ but not by $4$." – Dilip Sarwate Nov 22 '12 at 17:25
Correct. But he got the hint. – Gautam Shenoy Nov 23 '12 at 11:18

Are you familiar with the mod operator?

We want to show

$x^2 - 1 \equiv 0\mod8$

$x^2 \equiv 1\mod8$ for $x = 2k+1$ for some $k$

$(2k+1)^2 \equiv 1 \mod 8$

$4k^2 + 4k + 1 \equiv 1 \mod 8$

$4k^2 + 4k \equiv 0 \mod 8$

$4 (k^2 + 4k) \equiv 0 \mod 8$

This is what we want to show.

If $k$ is odd then $k^2$ is odd. And $k^2 + k$ is even. If $k$ is even then $k^2 + k$ is even

Hence $k^2 + k$ is always of the form $2a$, And hence

$4 (k^2 + 4k) \equiv 4(2a) \equiv 8a \equiv 0 \mod 8$

-

Alternatively, you could prove this by induction on $x$.

Base case: Consider the case where $x = 1$. Clearly, $(1)^2 - 1 = 0$ is divisible by 8. Hence, the base case is true

Inductive Hypothesis: Assume that the statement is true for some $x = k$ where $k$ is an odd integer greater than 1.

Inductive Step: Since $k$ is odd, we must show that the statement holds for the next odd integer, $k + 2$. Plugging $x = k + 2$ into $x^2 - 1$,

$$(k + 2)^2 - 1 = k^2 + 4k + 3 = (k^2 - 1) + 4(k + 1)$$

$k^2 - 1$ was divisible by 8 by the inductive hypothesis. Thus, the statement holds for $k + 2$ if and only if $4(k + 1)$ is divisible by 8. Observe that since $k$ is odd, is can be written as $k = 2q + 1$ for some integer $q$. This gives us

$$4(k + 1) = 4((2q + 1) + 1) = 4(2q + 2) = 8q + 8 = 8(q + 1)$$

Thus, we have shown that 8 divides $4(k + 1)$ which means that it also divides $(k + 2)^2 - 1$, completing the proof.

-

If $x$ is odd, then there exists $k \in \mathbb{Z}$, such that $x = 2k + 1$. Therefore: $$x^2 − 1 = (2k + 1)^2 − 1 = 4k^2 + 4k + 1 − 1 = 4k^2 + 4k = 8 \times \frac{k(k+1)}{2}$$ $\displaystyle k(k+1)$ is even, since either $k$ or $k + 1$ is even. Thus we can write it as $2n$ where $n\in\mathbb{Z}$, so now we obtain: $$x^2-1=8\frac{\rlap{\color{red}/}2n}{\rlap{\color{red}/}{2}}=8n$$

Therefore $x^2-1$ is divisible by $8$. $\,\blacksquare$

-