Proof of n^2 not congruent to 2 modulo 3

[foxjwill]

Homework Statement

I'd like to know if my proof that $$\forall n \in \mathbb{Z},\ n^2 \not\equiv 2 \mod 3.$$

Homework Equations

The Attempt at a Solution

Start by guessing that for some $$n=k$$,

$$k^2 \not\equiv 2 \mod 3.$$​

Since the theorem is obviously true for $$n=1$$, all we need to show is that it is also true for some $$n=k+1$$. If $$k^2 \equiv 0 \mod 3$$, then so is $$k$$, and it follows first that $$2k+1 \equiv 1 \mod 3$$ and then that $$k^2+2k+1 = (k+1)^2 \equiv 1 \mod 3.$$ Using a similar process for $$k^2 \equiv 1 \mod 3$$, it follows that $$(k+1)^2 \equiv 0 \mod 3.$$ Therefore $$(k+1)^2$$ must be congruent to either $$0$$ or $$1$$ modulo 3, and the theorem is proven. Q.E.D.

 

[dynamicsolo]

I'm not sure I see why your first sentence has anything to do with the argument that follows. Would you have known to ignore $$k^2 \not\equiv 2$$ if the proposition hadn't mentioned it?

The thrust of the argument itself is probably reasonable. Why not consider the three possible cases for integers in mod-3 (3p, 3p+1, 3p+2, p integral) and see what happens to their squares?

 

[will.c]

This works. I'm not sure what level class this is for, but you might also want to include proof of the fact that $$k^2 \equiv 0 mod3 \Rightarrow k \equiv 0 mod3$$.

dynamic solo, this is an example of inductive proof. You assume that a proposition on a natural number implies the truth of the proposition on the next higher natural number. Showing the truth of some base case then proves the proposition for all natural numbers.

 

[dynamicsolo]

I know what a proof by induction is: I didn't find myself satisfied by the way it was carried out.

 

[will.c]

Ah, I didn't read the first sentence too carefully, I can see how the wording kind of undermines what's actually going on.

 

[HallsofIvy]

Homework Statement

I'd like to know if my proof that $$\forall n \in \mathbb{Z},\ n^2 \not\equiv 2 \mod 3.$$

Homework Equations

The Attempt at a Solution

Start by guessing that for some $$n=k$$,

$$k^2 \not\equiv 2 \mod 3.$$​

Since the theorem is obviously true for $$n=1$$, all we need to show is that it is also true for some $$n=k+1$$.

No, you want to prove that If it is true for k then it is also true for k+1.

If $$k^2 \equiv 0 \mod 3$$, then so is $$k$$, and it follows first that $$2k+1 \equiv 1 \mod 3$$ and then that $$k^2+2k+1 = (k+1)^2 \equiv 1 \mod 3.$$ Using a similar process for $$k^2 \equiv 1 \mod 3$$, it follows that $$(k+1)^2 \equiv 0 \mod 3.$$ Therefore $$(k+1)^2$$ must be congruent to either $$0$$ or $$1$$ modulo 3, and the theorem is proven. Q.E.D.

In other words, you are saying that if k^2] is NOT contruent to 2 mod 3, it must be either congruent to 0 or congruent to 1. I notice that you assert, without proof, that if k² is contruent to 0 mod 3 then so is k. Have you proved that previously?

Are you required to use induction? It seems to me that a direct proof, looking at the three cases:
1) if n= 3k then n²= 9k² = 3(3k) and so is congruent to 0 mod 3.
2) If n= 3k+ 1 then (3n+1)²= 9n²+ 6n+ 1= 3(3n²+ 2n)+1
3) if n= 3k+ 2 then (3n+2)²= 9n²+ 12n+ 4= 3(3n²+ 4n+ 1)+ 1.
would be simpler.

 

[dynamicsolo]

It seems to me that a direct proof, looking at the three cases: ...

... which is what I proposed. The induction approach doesn't seem to save any trouble for this proposition and the offered proof seemed incomplete.

 

[foxjwill]

Actually, I was just trying to work out some proofs on my own (since I'm planning on majoring in math, I've decided it'd probably be a good idea to become more fluent in conducting proofs). It's not for a class or anything.

I like hallsofivy's method for solving this much better, though. I hadn't really thought about having to prove that $$n^2 \equiv a \mod 3 \Rightarrow n \equiv a \mod 3$$ (which I haven't -- actually, could anyone give me a hint on how to do so?)

p.s. HallsOfIvy, did you get the p.m. I sent you about the Linear ODE article?

edit: would I use a method similar to HallsOfIvy's to prove $$n^2 \equiv a \mod 3 \Rightarrow n \equiv a \mod 3$$?

1)If n^2=9k, then n = 3k (where k is an arbitrary constant)
So, that proves it for n^2 congruent to 0 modulo 3. But what about 1 and 2 modulo 3?

 

[will.c]

That statement is wrong. If n^2 is congruent to a mod 3, n is not necessarily...

If, however, n^2 is congruent to 0 mod 3, then n^2 is divisible by 3... Why would this imply the same is true for n?

 

[HallsofIvy]

Actually, I was just trying to work out some proofs on my own (since I'm planning on majoring in math, I've decided it'd probably be a good idea to become more fluent in conducting proofs). It's not for a class or anything.

I like hallsofivy's method for solving this much better, though. I hadn't really thought about having to prove that $$n^2 \equiv a \mod 3 \Rightarrow n \equiv a \mod 3$$ (which I haven't -- actually, could anyone give me a hint on how to do so?)

You can't prove it- it's not true. If n is equivalent to either 0 or 1 mod 3, then n² is equivalent to 2 mod 3. So if n² is equivalent to 1 mod 3, n is NOT necessarily equivalent to 1 mod 3.

p.s. HallsOfIvy, did you get the p.m. I sent you about the Linear ODE article?

Yes, I did but the LaTex does not show. Where is the article posted?

edit: would I use a method similar to HallsOfIvy's to prove $$n^2 \equiv a \mod 3 \Rightarrow n \equiv a \mod 3$$?

1)If n^2=9k, then n = 3k (where k is an arbitrary constant)
So, that proves it for n^2 congruent to 0 modulo 3. But what about 1 and 2 modulo 3?

As I said before, it's not true for 1 and 2. Also, "f n^2=9k, then n = 3k (where k is an arbitrary constant)" is obviously incorrect. if n²= 9k, then $9= 3\sqrt{k}$ and, if k is "an arbitrary constant", $\sqrt{k}$ may not be an integer. Saying $n\equiv 0$ mod 3 only tells you, directly. that n²= 3k. Since the square root of 3 is not an integer it is true that if n² is a multiple of 3 it must also be a multiple of 9 but you have to prove that.

 

[foxjwill]

As I said before, it's not true for 1 and 2. Also, "f n^2=9k, then n = 3k (where k is an arbitrary constant)" is obviously incorrect. if n²= 9k, then $9= 3\sqrt{k}$ and, if k is "an arbitrary constant", $\sqrt{k}$ may not be an integer. Saying $n\equiv 0$ mod 3 only tells you, directly. that n²= 3k. Since the square root of 3 is not an integer it is true that if n² is a multiple of 3 it must also be a multiple of 9 but you have to prove that.

hmm. I guess I didn't think it through all that well. Thanks.