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?
Best Answer
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.