4
$\begingroup$

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!

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

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

$\endgroup$
  • $\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$ – tuple_linear Jan 18 '17 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$ – Cameron Buie Jan 18 '17 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$ – tuple_linear Jan 19 '17 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$ – Cameron Buie Jan 19 '17 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$ – tuple_linear Jan 19 '17 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.