7
$\begingroup$

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!

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

2 Answers 2

5
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ Also, there's little Gauß: $$1+2+3+\dots +n=\dfrac {n(n+1)}2.$$ Or, one of $n,n+1$ is even. $\endgroup$
    – i can try
    Commented Feb 4, 2023 at 6:24
1
$\begingroup$

$\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.$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .