Proof by contraposition. Let $x$ be an integer. If $8$ does not divide $x^2-1$, then $x$ is even.

Question

Prove by contraposition: Let $x$ be an integer. If $8$ does not divide $x^2-1$, then $x$ is even.

Assume $x$ is odd. Prove $8|x^2-1$

So, $x=2n+1$ for some integer $n$. Then $x^2-1=4(n^2+n)$ for some $n^2+n$ integer by closure of Z. By algebra, multiply through by $2$ to get $2(x^2-1)=8(n^2+n)$. Then, $x^2-1=8(\frac{n^2+n}{2})$

I get stuck here, because I cannot say that the fraction is an integer because $\mathbb{Z}$ isn't closed for division. Help!

Answer 1

How many ways are there to choose two people from $n+1$ people? It is $${n+1 \choose 2} = \frac{n(n+1)}{2} = \frac{n^2 +n}{2} $$

This is the quantity you are interested in. But the number of ways to choose two people from $n+1$ people is an integer. Can you use this to conclude that your expression is an integer?

Answer 2

$\pmod 8$ we have $$0^2\equiv 0\\1^2\equiv 1\\2^2\equiv 4\\3^2\equiv 1\\4^2\equiv 0\\5^2\equiv 1\\6^2\equiv 4\\7^2\equiv 1$$

So we have $0,2,4,$ or $6 \pmod8.$