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

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!

• Try taking the cases as when $n$ is even and when $n$ is odd. Commented Feb 4, 2023 at 4:24
• check $x \in \{1,3,5,7\}.$ Commented Feb 4, 2023 at 5:38

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?
• Also, there's little Gauß: $$1+2+3+\dots +n=\dfrac {n(n+1)}2.$$ Or, one of $n,n+1$ is even. Commented Feb 4, 2023 at 6:24
$$\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.$$