# Contradiction or Contrapositive divides proof?

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:

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}$$?

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$$.
• I don't know much about the modulus - How do we know that $n^{2} \equiv 0,1 (mod 4)$ for all $n$? Jan 13, 2021 at 21:06
• 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. Jan 13, 2021 at 21:12