# prove that if n is a positive integer and 2 divides $n^2$ then 4 divides $n^2$

Best way is to prove by induction?

So base case, $n=2$ then $2^2 =4$ which $2$ and $4$ divides $4$

Induction

Suppose $2$ divides $n^2$ then $2$ divides $(n+1)^2$?

-
Isn't there something that says if $p$ is a prime and $p|ab$, then $p|a$ or $p|b$? –  Mike Oct 23 '12 at 23:35
no, everything that i was given is in the title –  Jack F Oct 23 '12 at 23:38

If $2$ divides $n$ (resp. $n^2$), then $2$ does not divide $n+1$ (resp. $(n+1)^2$). Thus, your inductive step should go from $n$ to $n+2$.

Also, you should be assuming that $4$ divides $n^2$.

After these corrections, your inductive proof will work.

-
but then how to prove it? –  Jack F Oct 23 '12 at 23:53
Originally, you wrote "Suppose 2 divides n^2 then 2 divides (n+1)^2?"; once these corrections are made it will become "Suppose 4 divides n^2, then (n+2)^2=..., which is divisible by 4." –  Douglas S. Stones Oct 23 '12 at 23:55

If $n^2$ is even then $n$ must be even (if $n$ were odd, $n^2$ would be odd), so that $n=2k$ for some integer $k$, so that $n^2=4k^2$.

-

Suppose $4$ does not divide $n^2$, then $4t = n^2 +k$ for some integer $t$. Now this implies $2(2t) = n^2 + k$. Therefore, $2$ does not divide $n^2$

-
proof by contradiction the best way to solve it? –  Jack F Oct 23 '12 at 23:37
wait, i'm confused, do you actually do proof by contradiction or is it a proof by contradiction in inductive step? because I don't get where did you get +1 –  Jack F Oct 23 '12 at 23:41
by contradiction or proving the contrapositive of the statement. –  FromCuba Oct 23 '12 at 23:42
from what did the +1 come from in both equations, as for contradiction you are not going to the next element –  Jack F Oct 23 '12 at 23:44
How do you get from the "Now this implies" to the "Therefore" if $k = 0 \mod 2$? That is, if $k = 2$(assuming you also meant $0 \leq k < 4$). –  Michael Burge Oct 24 '12 at 0:12

I found a name for what I was looking for. It's called Euclid's Lemma( http://en.wikipedia.org/wiki/Euclid%27s_lemma). As mentioned before, it states that that for any prime number $p$,

$$\text{if }p|ab\text{ then }p|a\text{ or }p|b$$

or potentially both. In this case, we have $p=2$ and $a=b=n$. Therefore, by Euclid's Lemma, $2|n$. So $n=2k$ for some integer $k$ and $n^2=4k^2$. Therefore, $4|n^2$.

-