Proof by contradiction to show a number is not a perfect square

Question

If n mod 4 leaves a remainder of 2 or 3, then n cannot be expressed as a perfect square. How can we prove this by Contradiction?

Thanks in advance.

Answer 1

Suppose $n$ is a perfect square i.e. $\exists m \in \mathbb{N}: n=m^2$.

$$m \equiv_4 0 \implies m^2 \equiv_4 0 \\ m \equiv_4 1 \implies m^2 \equiv_4 1 \\ m \equiv_4 2 \implies m^2 \equiv_4 0 \\m \equiv_4 3 \implies m^2 \equiv_4 1 $$

so $\forall m \in \mathbb{N}$ we have that $m \not\equiv_4 2$ and $m \not\equiv_4 3.$

Answer 2

Well a number $n$ can be written as $n = 4k + i$ where $i=0,1,2$ or $3$. (Correct?) So $n^2 = (4k + i)^2 = 16k^2 + 8ki + i^2$. Since $4$ will divide $16k^2 + 8ki$ the remainder of $n^2$ when divided by $4$ will be the same as $i^2$ divided by $4$. (Correct)

So what are the remainders of $0^2, 1^2, 2^2$ or $3^2$ when divided by $4$.

Note: this is not the slickest or must efficient or most sophisticated proof. But it is a direct proof a novice student should be capable of coming up with on one's own.

.....

I suppose if one had no insight at all how to do this at all one could think:

$n^2 = 4k + 3$

$n = \sqrt {4k + 3}$

$n = 2 \sqrt {k+\frac 3/4}$

So $\sqrt{k+\frac 34}$ is rational is either any integer $j = \sqrt{k+\frac 34}$ or $\sqrt{k+\frac 34} = \frac j2$. But $\sqrt{k+\frac 34}\in \mathbb Z$ is only possible if $k + \frac 34 \in \matbb Z$ which is impossible if $k$ is and integer.

So $\sqrt{k+ \frac 34} = \frac j2$. So $\sqrt{k + \frac 34} = \frac {\sqrt{\frac k4 + 3}}2 = \frac j2$ and $\sqrt{\frac k4 + 3}$is an integer. Which puts us back where we started in an infinite regress.

Hopefully it would have occurred that since $\sqrt{k+\frac 34}$ can't be in integer that if $\sqrt{k+\frac 34} = \frac j2$ that $j$ can not be even.

So $j = 2m+1$ for some $m$ and $k +\frac 34 = \frac {(2m+1)^2}4 = \frac {4m^2 + 4m + 1}4 = m^2 + m + \frac 14$ so $k = m^2 + mm -\frac 12$ which is not an integer.

But if the hapless student has gone this far, hopeful s/he it would have occured to him/her that $n^2 = 4m + 3$ could have two cases; $n = 2k$ and is even and $n= 2k+1$ and is odd. $n =2k \implies n^2 = 4k^2 \ne 4m + 3$ and $n=2k + 1\implies n^2 = 4k^2 + 4k + 1 \ne 4m + 3$, for a far simpler proof.

Answer 3

For a full proof by contradiction, start with $n \equiv_4 2$ so that $n=4k+2$ for some $k$.

Now suppose that $n = m^2$

Since $n$ is even, we have $m^2$ is even. If you don't have $m^2$ is even implies $m$ is even, then prove it (by contradiction).

Since $m$ is even, $m= 2j$, so $m^2 = 4j^2 \equiv_4 0$ contradicting $m^2 = n \equiv_4 2$.

Reject the supposition that $n = m^2$.

The other case involves a square that is odd, so the number squared is odd. You should be able to show that $n \equiv_4 3$ and $n \equiv 1$ which is a contradiction.