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

Homework Help: 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).
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook