Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

4 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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$

share|improve this answer
1  
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. –  Euler 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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.