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

You must log in to answer this question.

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