1
$\begingroup$

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

  • 0
    no, everything that i was given is in the title2012-10-23

4 Answers 4

0

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

5

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

3

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.

  • 0
    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."2012-10-23
1

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$

  • 0
    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).2012-10-24