Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Best way is to prove by induction?

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


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

share|cite|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
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|cite|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

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|cite|improve this answer

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|cite|improve this answer
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. – ILoveMath 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( 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|cite|improve this answer

Your Answer


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.