1
$\begingroup$

I'm just working through the Book of Proof and have come up against the following question:

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

It's in the section for either direct or contrapositive proof. I have a proof by contradiction that I think works:

Proof (Contradiction):

Suppose that there is some $n\in \mathbb{Z}$ where $4\mid(n^{2}-3)$. By definition, therefore, $n^{2}-3 = 4x$ where $x\in \mathbb{Z}$.

Case 1: $n$ is even. Therefore $n = 2a, a\in \mathbb{Z}$. Therefore, $(2a)^{2} - 3 = 4x \Leftrightarrow 4a^{2} - 3 = 4x$. Therefore, $2b + 1 = 2c$ where $b=2a^{2} - 2, b\in \mathbb{Z}$ and $c = 2x, c\in \mathbb{Z}$. Therefore we have a contradiction - LHS Odd, RHS even.

Case 2: $n$ is odd. Therefore $n = 2d + 1, d\in \mathbb{Z}$. Therefore, $(2d +1)^{2} - 3 = 4x \Leftrightarrow 4d^{2} + 4d - 2 = 4x \Leftrightarrow 2(2d^{2} + 2d - 1) = 2(2x)$. Dividing both sides by 2 we get $2e + 1 = 2x$ where $e=d^{2}+d-1, e\in \mathbb{Z}$. Therefore we have a contradiction - LHS Odd, RHS even.

Both cases result in a contradiction therefore $(n\in \mathbb{Z})\Rightarrow (4\nmid (n^{2}-3))$ $\blacksquare$

My question is how would I approach a contrapositive proof? Maybe I can factor the $n^{2}$ term somehow to show that it's values must be from $\mathbb{Q}$ or $\mathbb{R}$?

$\endgroup$

1 Answer 1

1
$\begingroup$

The proof by contrapositive would be the following:

Prove $4 \mid n^{2}-3 \implies n \notin \mathbb{Z}$.

Suppose $4 \mid n^{2}-3$. Then $n^{2}-3 = 4k \implies n^{2}-3 \equiv0 \pmod 4 \implies n^{2} \equiv 3\pmod 4 $.

But this has no solution as $n^{2} \equiv 0,1 \pmod 4$ for all $n$.

This means that our initial equivalence has no solution, i.e., no integer solution. We have proved that if there is one, then it must be a non-integer.

$\endgroup$
2
  • $\begingroup$ I don't know much about the modulus - How do we know that $n^{2} \equiv 0,1 (mod 4)$ for all $n$? $\endgroup$ Jan 13, 2021 at 21:06
  • 1
    $\begingroup$ Do you know by the divison algorithm that any integer $n$ can be written as $n=4k+r $ where $0\leq r <4$? Shorthand for this is $n \equiv 0,1,2,3 \pmod 4$. Squaring n for these 4 different remainders r, one finds that $n$ can only be written as $4j+0$ or $4m+1$, where in shorthand modular arithmetic this means $n^{2}$ can only be either $0$ or $1$, not $3$ as would be required in this problem case. $\endgroup$
    – Derek Luna
    Jan 13, 2021 at 21:12

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.