# Prove: $n \in \mathbb{Z} \implies 4 \nmid (n^2-3)$

I'm trying to write a contrapositive proof. What I have seems somewhat legit, but it uses proof by contradiction couched within a contrapositive proof. Since this problem is presented before the chapter on proof by contradiction (in the text I'm self-studying), I suspect there's a cleaner way that I'm missing.

Prove that if $n \in \mathbb{Z}$, then $4 \nmid (n^2-3)$

Proof: Suppose $4$ divides $(n^2-3)$. Then, $4a=n^2-3$ for some $a\in\mathbb{Z}$. We see that $n^2-3=4a=2\cdot 2a$ is an even integer, so $n^2$ is an odd integer.

If we further suppose that $\sqrt{n^2}\in\mathbb{Z}$, then $\sqrt{n^2}=n$ must be odd, since odd times odd equals odd, while even times even equals even. Thus, $n=2k + 1$ for some $k\in\mathbb{Z}$. We can then rewrite the original equation: $$(2k+1)^2-3=4a \\ 4k^2 + 4k - 2 = 4a \\ 4k^2 + 4k - 4a = 2 \\ k^2 + k - a = 2/4 = 1/2 \notin \mathbb{Z}$$ Since $a,k \in \mathbb{Z}$ (and thus $k^2\in\mathbb{Z}$), this is a contradiction. It seems to me it falsifies the second supposition, that $\sqrt{n^2}\in\mathbb{Z}$. I wonder, though, if there's a cleaner way that doesn't rely on that second supposition at all.

Doh! I see I should've dumped the contrapositive stuff and just done a direct proof by cases. Thanks for straightening me out :) Here we go...

Case: $n$ is an even integer. Thus, $n^2$ is even and $n^2-3$ is odd, so $4$ cannot divide $n^2-3$.

Case: $n$ is an odd integer. Then, $n=2k+1$ for some integer $k$, and $n^2-3=4k^2+4k-2$. Since $4$ divides the first two terms but not the third term, $4$ cannot divide the sum. Thus, $4\nmid (n^2-3)$.

Thanks for clarifying that!

-
If you do it directly, supposing $n$ is even, then $n^2-3$ is odd, so $4$ can't divide it. On the other hand, if $n$ is odd, then you get $4k^2+4k-2$. If $4$ divided this sum, then since $4$ divides the first two terms, it'd have to divide the last term, but it doesn't. –  Clayton Feb 28 '13 at 4:14
Ahhh, so obvious. Time for a forehead smack! –  ivan Feb 28 '13 at 4:17

Try a direct proof with two cases: (1) $n$ is odd, (2) $n$ is even.