# $2d^2=n^2$ implies that $n$ is multiple of 2

I'm reading a proof of the irrationality of $\sqrt 2$. In a step it states that $2d^2=n^2$ implies that $n$ is multiple of 2. How?

• If $n$ is odd then its square is also odd. But the left-hand side is even. – njguliyev Sep 2 '13 at 12:18
• If prime $p$ divides $a^2,p$ must divide $a$ – lab bhattacharjee Sep 2 '13 at 12:19
• related to my earlier question (why this only works for prime numbers): math.stackexchange.com/q/162119/29313 – KutuluMike Sep 2 '13 at 14:23

If $n^2 = 2d^2$, then $n^2$ is a multiple of $2$ hence even.

We now prove: $n^2$ even implies $n$ even.

Proof: We tackle the contrapositive, i.e., $n$ odd implies $n^2$ odd.

Since $n$ is odd, we can write $n = 2k+1$ for some integer $k$.

Then $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which is an odd number.

(It's of the form $2m + 1$ for an integer $m = 2k^2 + 2k$.)

This completes the proof, and the contrapositive is the statement you asked about. QED

$\;2\;$ is a prime and divides the left side in $\,2d^2=n^2\;$ , so by the fundamental theorem of arithmetic it also divides the right hand side...

• The FTA seems like overkill to me... – Benjamin Dickman Sep 2 '13 at 12:24
• Perhaps so, @BenjaminDickman, yet do you know any other, inequivalent and formal way to prove the statement? – DonAntonio Sep 2 '13 at 12:25
• Yes; I have already provided one. – Benjamin Dickman Sep 2 '13 at 12:26
• That doesn't look so formal to me, @BenjaminDickman: how can you prove any integer is either odd or even, as you implicitly assumed? You may want to go to Peano axioms and/or induction, which would imply more or less the same work as the FTA. After all, someone asking such a basic question may want to axiomatically base things... – DonAntonio Sep 2 '13 at 12:32
• I would accept also your answer now that I've understood, but actually my question was basic just because they didn't teach me very well (at all?) how to make demostrations at university or college. – bigstones Sep 2 '13 at 13:13

Since $d$ is an integer, $2d^2$ must be even. For any odd integer $n$, $n^2$ must also be odd. Therefore, $n$ must be even, and thus a multiple of 2.

It works for any prime $p$: $$p|n^2 \Rightarrow p|n$$ This is because of the uniqueness of prime factor decomposition.

square of even numbers are even, so $n$ is even

• This is a logical fallacy. "If $n$ is even, then $n^2$ is even," does not mean that "If $n^2$ is even, then $n$ is even." – Thomas Andrews Sep 2 '13 at 12:30
• @ThomasAndrews: yes you are right my answer was so quick and it wasn't well-considered. – Ömer Sep 2 '13 at 13:10