# 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. Commented Feb 28, 2013 at 4:14
• Ahhh, so obvious. Time for a forehead smack!
– ivan
Commented Feb 28, 2013 at 4:17

Try a direct proof with two cases: (1) $n$ is odd, (2) $n$ is even.
• Well, it occurred to me that $4$ certainly never divides an odd number, and $n^2-3$ is always odd when $n$ is even. Hence, all that's left is to consider what happens when $n$ is odd. Commented Jan 18, 2017 at 12:41
• So as a solution, would it be ok for each case of the proof to restate n^2-3 in the 2K+1 format of an odd-number and then state four (an even number) can not divide an odd number, stopping there as sufficient proof? Commented Jan 19, 2017 at 6:02
• I suspect it would be. It doesn't hurt, though, to outline a brief justification of why $n^2-3$ is odd in the case that $n$ is even. Commented Jan 19, 2017 at 7:35
• Sorry, what I meant is, both parity cases of n (n is even, n is odd) wind up with n^2-3 being odd. Do I need to take a further step to prove that 4 never divides an odd number, or is that taken as obvious? Commented Jan 19, 2017 at 10:01