# Prove if $n^2$ is even, then $n^2$ is divisible by 4

I am working on this question

Prove for every integer n if $n^2$ is even, then $n^2$ is divisible by 4.

Proof:

Since there exists an integer $n$ such that $n^2$ is even, and $n^2$ is not divisible by 4,

when $n$ is odd integer, we have $n = 2k + 1$ where $k \in \mathbb{Z}$,

then $n^2 = 4k^2 + 4k + 1$, because $n^2$ is odd which is a contradiction;

when $n$ is even integer, we have $n = 2j$ where $j \in\mathbb{Z}$,

then $n^2 = 4j^2 \Rightarrow n^2 | 4$, because $n^2$ is divisible by $4$, this is a contradiction; therefore, for every integer $n$, if $n^2$ is even, then $n^2$ is divisible by $4$.

Is my proof valid or can anyone give me hint or suggestion to write a better proof?

Thanks!

• Don't prove this by contradiction, it's silly. $2\mid n^2\to (2\mid n\lor 2\mid n)\to 2^2\mid n^2$ because $2$ is prime. Mar 2, 2015 at 5:01
• Your proof is valid! Although a direct proof is easier and arguably more elegant. Mar 2, 2015 at 5:11
• @RobertCardona I think the proof by contraposition is actually the most elegant in this particular instance (see my answer).
– user220080
Mar 2, 2015 at 6:40
• I agree, in this particular instance, proof by contradiction obfuscates rather than clarifies. Unless you've been specifically instructed to do it by contradiction, better to use a different method of proof. I would probably start with $n = 2m$ so $n^2 = 4m^2$... Mar 16, 2015 at 0:55

$$n^2\text{ even }\implies \text{n is even, hence:}$$$$n=2m,m\in\Bbb Z, n^2=4m^2\implies 4|n^2$$

• Also, I generally dislike contradiction proofs(like Mario Carneiro above), they just don't seem as clean to me(in terms of difficulty to follow).
– user142198
Mar 2, 2015 at 5:08

Proof: Suppose $n,m\in\mathbb{Z}$. Then $$n^2\neq [4m = 2(2m)].\;\blacksquare\tag{1}$$

There are really three "core methods" of proof one is likely to use in order to prove your statement: direct, contradiction, and contraposition. You will most often see such a proof proceed directly because this is generally the most natural (i.e., "direct") way of going about it, but let's check out the options:

Direct: See the answer provided by @Committingtoachallenge.

Contraposition: See $(1)$. I'm surprised no one gave this answer because I think it is definitely the easiest / most elegant way of proving it. The idea behind a proof by contraposition is to show that if $n^2$ is not divisible by $4$, then $n^2$ is not even (recall that $p\to q\equiv \neg q\to \neg p$; that is, $\neg q\to\neg p$ is the contrapositive of $p\to q$, where these two statements are equivalent. Hence, if we can prove the contrapositive, then we will have proven your original statement.).

• Contraposition is my first idea, but I get stuck at $n^2\ne 2l$ , thanks your work Mar 2, 2015 at 6:53
• I don't think the "contraposition proof" is valid. You wrote "$n^2\ne 4m$, where $m\in\Bbb Z$" - I assume that means $\forall m\in\Bbb Z,n^2\ne 4m$, so far so good. Then you rewrite this into $\forall m\in\Bbb Z,n^2\ne 2(2m)\implies \forall \ell\in\Bbb Z,n^2\ne 2\ell$, which is not valid (you have only proved this for even $\ell$). I think you forgot that this is a $\forall$ not $\exists$ quantifier given the unusual way you wrote it. Note that the same argument would give $4\mid n^2\implies 4^2\mid n^2$ which is false. Mar 2, 2015 at 7:17
• @MarioCarneiro I should have just written $n^2\neq 2(2m)$, where $m$ ranges over all of $\mathbb{Z}$, showing that $n^2$ can never be even, despite the value of $m\in\mathbb{Z}$. Good spot--I was trying to be cute, but that obviously didn't work. Thanks for pointing out the error.
– user220080
Mar 2, 2015 at 7:28
• @Simple Please see Mario's comment; he noted a flaw in my original argument, where I tried to clean up notation and make things clearer but only muffed it up.
– user220080
Mar 2, 2015 at 7:32

Suppose $n^2$ is even and $n^2$ is not divisible by $4$. Then $n^2 = 4k+2$ for some integer $k$.

But every square of an integer is of the form $4k$ or $4k+1$. This is the desired contradiction.

A direct proof is more appropriate here. As $n$ is even, we can write $n=2k$ for some integer $k$. Then, $n^2 = (2k)^2 = 4k^2$, which is clearly divisible by $4$.

A proof by contradiction isn't needed, here. Just know that if $n^2$ is even, $n$ is even (easily provable), and that an even number $n$ follows the form $2k$, so $n^2$ is... which is clearly divisible by...

edit: Yes, your proof is very much valid.

• Beat ya ;P(by 13 seconds)
– user142198
Mar 2, 2015 at 5:06
• @Committingtoachallenge gah! Well-played (though I believe the OP asked for a hint...) Mar 2, 2015 at 5:08
• Yes I realised that afterwards and I feel ashamed(but it's out there now)
– user142198
Mar 2, 2015 at 5:08
• Unrelated note: I just hit 1000 rep :)
– user142198
Mar 2, 2015 at 5:09
• @Committingtoachallenge Nice! (and what's past is past ;) ) Mar 2, 2015 at 5:12