[Math] Prove by contraposition help.

discrete mathematicselementary-number-theorymodular arithmeticnumber theoryproof-writing

I'm not very familiar with contraposition and so I am having some difficulties proving the statement.

If $n$ is a positive integer such that $n \equiv 2 \pmod{4}$ or $n \equiv 3 \pmod{4}$, then $n$ is not a perfect square.

What would be a good way to prove this?
Need help please.

Best Answer

In general, the contrapositive of a conditional:

'If P then Q'

is the statement:

'If not Q then not P'

Applied to your statement, we would thus get:

'If $n$ is a perfect square, then $n$ is not a positive integer such that $n \equiv 2 \pmod{4}$ or $n \equiv 3 \pmod{4}$'

... But somehow I doubt that's what they meant. In fact, the original statement was probably meant as:

'For any positive integer $n$, it holds that if $n \equiv 2 \pmod{4}$ or $n \equiv 3 \pmod{4}$, then $n$ is not a perfect square'

So then by taking the contrapositive of the contrapositive of the conditional that is part of that general statement about positive integers, we get:

'For any positive integer $n$, it holds that if $n$ is a perfect square, then it is not the case that $n \equiv 2 \pmod{4}$ or $n \equiv 3 \pmod{4}$'

...which makes a lot more sense.

Indeed, to prove this statement:

Take $n$ to be a positive integer and assume it is a perfect square. So, $n=k^2$ with $k$ an integer. $k$ is either even or odd. If $k$ is even, then $k=2m$ for some integer $m$, and so $n=(2m)^2=4m^2$. Hence, $n \equiv 0 \pmod{4}$. If $k$ is odd, then $k=2k+1$ for some integer $m$' and so $n=(2m+1)^2=4m^2+4m+1$, and hence $n \equiv 1 \pmod{4}$. So, it is not the case that $n \equiv 2 \pmod{4}$ or that $n \equiv 3 \pmod{4}$.