7
$\begingroup$

I am working on this question

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

prove by contradiction

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!

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Mar 2, 2015 at 5:01
  • 2
    $\begingroup$ Your proof is valid! Although a direct proof is easier and arguably more elegant. $\endgroup$ Mar 2, 2015 at 5:11
  • $\begingroup$ @RobertCardona I think the proof by contraposition is actually the most elegant in this particular instance (see my answer). $\endgroup$
    – user220080
    Mar 2, 2015 at 6:40
  • $\begingroup$ 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$... $\endgroup$ Mar 16, 2015 at 0:55

5 Answers 5

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – user142198
    Mar 2, 2015 at 5:08
2
$\begingroup$

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.

Contradiction: See your own answer (it's correct, but it could be written up much more neatly).

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.).

$\endgroup$
4
  • $\begingroup$ Contraposition is my first idea, but I get stuck at $n^2\ne 2l$ , thanks your work $\endgroup$
    – Simple
    Mar 2, 2015 at 6:53
  • $\begingroup$ 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. $\endgroup$ Mar 2, 2015 at 7:17
  • $\begingroup$ @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. $\endgroup$
    – user220080
    Mar 2, 2015 at 7:28
  • $\begingroup$ @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. $\endgroup$
    – user220080
    Mar 2, 2015 at 7:32
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
0
0
$\begingroup$

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.

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

You must log in to answer this question.

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