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!

  • 3
    $\begingroup$ 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. $\endgroup$
    – Clayton
    Commented Feb 28, 2013 at 4:14
  • 2
    $\begingroup$ Ahhh, so obvious. Time for a forehead smack! $\endgroup$
    – ivan
    Commented Feb 28, 2013 at 4:17

1 Answer 1


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

  • $\begingroup$ This is an old question, but I'm wondering where the intuition for trying parity cases comes from in solving this? My initial approach was an indirect proof, but that left me with 'n = sqrt(4k+3)' trying to show that n is not an integer. That seemed like a dead end. $\endgroup$ Commented Jan 18, 2017 at 5:53
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 18, 2017 at 12:41
  • $\begingroup$ 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? $\endgroup$ Commented Jan 19, 2017 at 6:02
  • $\begingroup$ 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. $\endgroup$ Commented Jan 19, 2017 at 7:35
  • $\begingroup$ 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? $\endgroup$ Commented Jan 19, 2017 at 10:01

You must log in to answer this question.

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