0

If $n$ is an integer and $n^2$ is even, then $n$ is even

I am reading a book on proofs and the above statement motivates the author to introduce Proof by Contradiction. I am a little confused as to why this proof motivates the introduction of a new proof strategy.

The previous method that the author has been using (which he claims "fails us" for this proof), is something he refers to as the Forward-Backward Method. As far as I can tell, the Forward-Backward Method is still valid and works like so:

  1. if $n$ is even, then there exists an integer $k$ such that $n=2*k$
  2. if $n^2$ is even, then there exists an integer $m$ such that $n^2=2*m$

now, my objective is to show that I can rewrite $n^2$ in the form of $n=2*k$, which the author claims I cannot do using the forward-backwards method. However, I would proceed as such:

  1. take the square root of $n^2$ to generate: $n=\sqrt{2*m}$

  2. this can be rewritten as $n = \sqrt{2*2*\frac{m}{2}}$

  3. then we have $n=2*\sqrt{\frac{m}{2}}$

  4. so let's have $k = \sqrt{\frac{m}{2}}$

  5. however, recall that $k$ has been defined as an integer...so, keeping in mind that $m$ must also be an integer, let's let $m$ be defined as: $m = 2*(\mathbb N^2)$. ...where the fancy $N$ is any natural number

Step 7 guarantees that $m$ and $k$ will always be integers which therefore let's us confirm that:

  1. $n = 2k$

If anyone could confirm that this is logically valid, and that I am correct in thinking that I do not need to utilize Proof By Contradiction in order to prove this statement, I would greatly appreciate it!

Edit: Upon further reflection, I think this proof may only be valid for $n$ greater than or equal to $0$.

S.C.
  • 4,984
  • 1
    I have no idea what you mean at step 7. – Angina Seng Sep 10 '19 at 16:06
  • Step 7 is my way of constructing a very specific $m$ such that $m$ will always be an integer (which I assumed to be true) and that $k$ will always be an integer(which I assumed to be true). The fancy $N$ was my way of denoting "Natural Number". This ensure that $n$ ranges from 0 to infinity at integer intervals. Is there a more clear way of conveying "Natural Number"? – S.C. Sep 10 '19 at 16:11
  • 1
    A direct proof should at some point use (that $n$ is an integer and) the uniqueness of a multiplicative decomposition in prime factors (and the fact that $2$ is prime in $\Bbb Z$). – dan_fulea Sep 10 '19 at 16:14
  • 3
    What do you mean by "$k$ has been defined as an integer"? The only definition of $k$ is $k=\sqrt{m/2}$ Why should this be an integer? It's equal to $n/2$. Saying that it's an integer is asserting that $n$ is even. You are assuming what you need to prove. – saulspatz Sep 10 '19 at 16:15
  • in Step 1, I say "then there exists an integer k" – S.C. Sep 10 '19 at 16:15
  • That is to say, $n$ is even. Why not stop right there? – saulspatz Sep 10 '19 at 16:16
  • At the beginning of the proofs, part of the definitions of $k$ and $m$ that I impose are that they are integers. – S.C. Sep 10 '19 at 16:19
  • 7
    $n^2-n = n(n-1)=\text{even}$ – Blue Sep 10 '19 at 16:19
  • 1
    @Blue That is so wonderfully elegant. I will keep that for further teaching reference. – Rushabh Mehta Sep 10 '19 at 16:20
  • 1
    You can't take as an principle that $n$ is even, since you are trying to prove that... @Blue - I deleted my other comment, because it was stupid! – Martigan Sep 10 '19 at 16:24
  • 1
    @Blue Now that's cute and slick as well. – Michael Hoppe Sep 10 '19 at 16:53
  • @DonThousand. As usual, I gave an A that's longer & more complicated. – DanielWainfleet Sep 10 '19 at 18:49

2 Answers2

1

There exist integers $m, r$ with $r\in \{0,1\}$ and $n=2m+r.$ Therefore $$n^2/2\in \Bbb Z \iff$$ $$\iff r^2/2=n^2/2-(2m^2+2mr)\in \Bbb Z \iff$$ $$\iff r^2/2\in \Bbb Z \iff$$ $$\iff [(r=1\land r^2/2\in \Bbb Z)\lor (r=0\land r^2/2\in Z)] \iff$$ $$\iff [(r=1\land 1^2/2\in \Bbb Z)\lor (r=0\land 0^2/2\in \Bbb Z)]\iff$$ $$\iff [r=0\land 0\in \Bbb Z] \iff r=0 \iff$$ $$ \iff n/2=(2m+r)/2=m\in \Bbb Z \iff$$ $$\iff n/2\in \Bbb Z.$$

DanielWainfleet
  • 57,985
  • sorry if I misunderstood what the tag, "Proof Verification", entailed...but I just wanted to know whether or not my proof is accurate. Thank you for the supplementary proof nonetheless. – S.C. Sep 10 '19 at 20:47
  • 1
    You didn't misunderstand. Sometimes I just post an alternate proof. – DanielWainfleet Sep 11 '19 at 00:20
1

If $n=0$ we are done! Without loss of generality, assume $n>0$.

The integer $n$ has a unique prime factorization of the form: $$n=p_1^{k_1} \cdot p_2^{k_2} \cdots p_L^{k_L} \quad (\textrm{ with } p_1<p_2<\cdots < p_L).$$

So $$n^2=p_1^{2k_1} \cdot p_2^{2k_2} \cdots p_L^{2k_L}$$

Since $n^2$ is even, $p_1=2$. Thus $n$ is even.

mjw
  • 8,647
  • 1
  • 8
  • 23