1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

N^2 vs. mod 3 proof

  1. Jun 30, 2008 #1
    1. The problem statement, all variables and given/known data
    I'd like to know if my proof that [tex]\forall n \in \mathbb{Z},\ n^2 \not\equiv 2 \mod 3.[/tex]


    2. Relevant equations



    3. The attempt at a solution
    Start by guessing that for some [tex]n=k[/tex],
    [tex]k^2 \not\equiv 2 \mod 3.[/tex]​
    Since the theorem is obviously true for [tex]n=1[/tex], all we need to show is that it is also true for some [tex]n=k+1[/tex]. If [tex]k^2 \equiv 0 \mod 3[/tex], then so is [tex]k[/tex], and it follows first that [tex]2k+1 \equiv 1 \mod 3[/tex] and then that [tex]k^2+2k+1 = (k+1)^2 \equiv 1 \mod 3.[/tex] Using a similar process for [tex] k^2 \equiv 1 \mod 3[/tex], it follows that [tex](k+1)^2 \equiv 0 \mod 3.[/tex] Therefore [tex](k+1)^2[/tex] must be congruent to either [tex]0[/tex] or [tex]1[/tex] modulo 3, and the theorem is proven. Q.E.D.
     
  2. jcsd
  3. Jun 30, 2008 #2

    dynamicsolo

    User Avatar
    Homework Helper

    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 [tex]k^2 \not\equiv 2[/tex] 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?
     
  4. Jun 30, 2008 #3
    This works. I'm not sure what level class this is for, but you might also want to include proof of the fact that [tex]k^2 \equiv 0 mod3 \Rightarrow k \equiv 0 mod3[/tex].

    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.
     
  5. Jun 30, 2008 #4

    dynamicsolo

    User Avatar
    Homework Helper

    I know what a proof by induction is: I didn't find myself satisfied by the way it was carried out.
     
  6. Jun 30, 2008 #5
    Ah, I didn't read the first sentence too carefully, I can see how the wording kind of undermines what's actually going on.
     
  7. Jun 30, 2008 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

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

    In other words, you are saying that if k2] 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 k2 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 n2= 9k2 = 3(3k) and so is congruent to 0 mod 3.
    2) If n= 3k+ 1 then (3n+1)2= 9n2+ 6n+ 1= 3(3n2+ 2n)+1
    3) if n= 3k+ 2 then (3n+2)2= 9n2+ 12n+ 4= 3(3n2+ 4n+ 1)+ 1.
    would be simpler.
     
  8. Jun 30, 2008 #7

    dynamicsolo

    User Avatar
    Homework Helper

    ... which is what I proposed. The induction approach doesn't seem to save any trouble for this proposition and the offered proof seemed incomplete.
     
  9. Jun 30, 2008 #8
    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 [tex]n^2 \equiv a \mod 3 \Rightarrow n \equiv a \mod 3[/tex] (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 [tex]n^2 \equiv a \mod 3 \Rightarrow n \equiv a \mod 3[/tex]?

    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?
     
    Last edited by a moderator: Jul 1, 2008
  10. Jun 30, 2008 #9
    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?
     
  11. Jul 1, 2008 #10

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

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

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

    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 n2= 9k, then [itex]9= 3\sqrt{k}[/itex] and, if k is "an arbitrary constant", [itex]\sqrt{k}[/itex] may not be an integer. Saying [itex]n\equiv 0[/itex] mod 3 only tells you, directly. that n2= 3k. Since the square root of 3 is not an integer it is true that if n2 is a multiple of 3 it must also be a multiple of 9 but you have to prove that.
     
  12. Jul 1, 2008 #11
    hmm. I guess I didn't think it through all that well. Thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?