<s>[INST] 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!
 [/INST] 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?
</s>