Proving that if n is an odd positive integer, then $n^2$ ≡ 1 (mod 8) by contradiction?

Question

I am wondering if this statement can be proven by contradiction. I know the direct proof, but am trying to prove this by contradiction:

Assume $n^2$ $\not\equiv$ 1 (mod 8). Then $8\nmid (n^2 - 1)$, so $8\nmid (n+1)(n-1).$ This implies that $8\nmid (n + 1)$ or $8\nmid (n-1).$ Now, since n is odd, we can write n = 2k + 1 for integer k. So, $8\nmid (2k + 2)$ or $8\nmid 2k$. Is this a contradiction?

Thanks for any help.

** As I come back to look at this I am noticing that I think I should have written that $8\nmid (n+1)(n-1)$ implies that $8\nmid (n + 1)$ AND $8\nmid (n-1).$ And now, since n is odd, $8\nmid (2k + 2)$ AND $8\nmid 2k$. Choosing, k = 8, for example, makes the former false and the latter true, hence we have a contradiction. Is this correct?

Answer 1

You should prove it for every $k$, not just for $k=8$.

Try this: If $n=2k+1$ then $n^2-1=\left (2k+1\right )^2-1=4k^2+4k=4\left (k^2+k\right )$. Since $k$ and $k^2$ are both odd or both even then $k^2+k$ is even.

EDIT: What I tried to say is that if you want to prove it by contradiction, you just have to notice that if $n^2-1$ is NOT divisible by $8$ then $k^2+k$ is odd, which is impossible. Sorry if it was not explicit enough.

Answer 2

This is not a contradiction. $2k$ and $2k+2$ are consecutive even numbers, so we know $2$ divides one and $4$ divides the other (although we don't know which). For instance, for $k=9$, $2 \mid 18$ and $4 \mid 20$ and no higher power of $2$ divides either. Then $8 \nmid 18$ and $8 \nmid 20$, so by itself, this is not a contradiction that completes your proof.

But you do have what you need. From $2$ divides one and $4$ divides the other, you can conclude that $8$ divides their product, contradicting that $8$ does not divide their product.

To show unambiguously that $2$ divides one and $4$ divides the other:

• Case $k$ is even: then $4|2k$ and $2|2(k+1)$ are evident.
• Case $k$ is odd: then $2|2k$ and $4|2(k+1)$.

Answer 3

"8∤(2k+2) or[/and] 8∤2k. Is this a contradiction?"

Why would it be? If $k = 2$ then $8\not \mid 2k + 2$ and $8\not \mid 2k$

$k = 4j + i$ so $2k + 2 = 8j + 2i + 2$ and $2k = 8j + 2i$ and $i\ne 0$ and $i\ne 2$ then $8\not \mid 2k +2$ and $8\not \mid 2k$. In other words, $8\mid 2k$ or $8\mid 2k+2$ only if $k \equiv 0$ or $2 \mod 4$.

The contradiction has to be that $4\not \mid 2k$ AND $4 \not \mid 2k+2$.

Try this:

$n^2 \not \equiv 1 \mod 8$

$(n + 1)(n-1) \not \equiv 0\mod 8$ and

$2k(2k+2) \not \equiv 0 \mod 8$

$8\not \mid 2k(2k+2)=4k*(k+1)$ so

$2 \not \mid k(k+1)$ which means $2\not \mid k$ and that $2\not \mid k+1$

Which means $k$ and $k + 1$ are both odd and... well...