Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Need descrete math help

  1. Nov 9, 2008 #1
    1. The problem statement, all variables and given/known data
    Show that n2 [tex]\neq[/tex]2 (mod6) for all n in Z



    2. Relevant equations



    3. The attempt at a solution

    0 1 2 3 4 5
    0 0 0 0 0 0 0
    1 0 1 2 3 4 5
    2 0 2 4 0 2 4
    3 0 3 0 3 0 3
    4 0 4 2 0 4 2
    5 0 5 4 3 2 1

    I did only the table for mod 6 and then I don't have an idea what to do.
    I am not even sure if I understand what exactly I have to do with this problem.
    Please help me if you can.
     
    Last edited: Nov 9, 2008
  2. jcsd
  3. Nov 9, 2008 #2

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    Hmmm....have you tried proof by contradiction? That is, assume that [itex]n^2 \equiv 2 \pmod{6}[/itex]....what does that imply?
     
  4. Nov 9, 2008 #3
    I did not attempt a solution but you might want to rewrite the statement.

    n2 congruent to 2 mod 6 is the same as n2 - 2 is a multiple of 6. So you might want to define f(n) = n2 - 2 and show what happens when you divide f(n) by 6.
     
  5. Nov 9, 2008 #4
    I think the only hint I get for this was the reminder needs to be [tex]\neq[/tex]2.

    I am gessing that has something to do with division Algorithm. I will try the above ideas.
     
  6. Nov 9, 2008 #5

    Mark44

    Staff: Mentor

    VeeEight said that "n[tex]^2[/tex] congruent to 2 mod 6 is the same as n[tex]^2[/tex] - 2 is a a multiple of 6."

    That's also the same as saying that n[tex]^2 - 2 \equiv[/tex] 0 mod 6.

    This one is ripe for a proof by induction.
     
  7. Nov 10, 2008 #6
    I don't think I know how to do it by induction. Thank you. I will try and I will come back again.
     
  8. Nov 10, 2008 #7

    Mark44

    Staff: Mentor

    Pick a value of n for which your statement is true, such as n = 2.

    Assume that for n = k, your statement is true. IOW, assume that k^2 != 2 mod 6.
    Now show that for n = k + 1, (k + 1)^2 != 2 mod 6, using the induction hypothesis (the thing you assumed in the previous step).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Similar Discussions: Need descrete math help
  1. Math Help needed (Replies: 13)

Loading...