Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
3  
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
2  
Ahhh, so obvious. Time for a forehead smack! –  ivan Feb 28 '13 at 4:17
add comment

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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