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: Abstract Algebra question regarding coprimes

  1. Aug 28, 2012 #1
    1. The problem statement, all variables and given/known data

    For any integer n>2, show that there are at least two elements in U(n) that satisfy x2=1.


    2. Relevant equations

    In my book I found a definition: Define U(n) to be the set of all positive integers less than n and relatively prime to n.


    3. The attempt at a solution

    I think I simply just don't understand exactly what is being asked. My first instinct is to just look at an integer greater than 2, say 3. Now I think, "What are some numbers in the set U(3)?" Well, I can only think of 1 and 2, since both 1 and 2 are positive numbers and co-prime to 3. Clearly 1 is a solution, but certainly not 2. Any other number greater than 3 yields the same conclusion, i.e. 1 as the only answer.
     
  2. jcsd
  3. Aug 28, 2012 #2
    Remember, our group operation is multiplication mod n. Thus, 22=4 mod 3 = 1. Hence, 2 is indeed a solution. As you said, the identity is clearly one solution. Create a few more examples for yourself. See what you notice. :)
     
  4. Aug 28, 2012 #3
    I see, thanks!
    Would induction be the best way to proceed for a complete proof?
     
  5. Aug 28, 2012 #4
    No, induction is not needed here.

    Take n=2,3,4,5,6,... and each time calculate the elements x such that [itex]x^2=1[/itex]. Do you notice something?
     
  6. Aug 28, 2012 #5
    Yes, I do notice that if I write the solutions out in rows, one under another, that the first column is all 1's, the 2nd column increases by 1, i.e. is the set {4,5,6...}, the 3rd column starts with 7 and increases by 2, i.e. {7,9,11,... } and so on.

    As you move along rows of course the solutions are every 3 numbers, for 3, or every 4th Number, for 4.


    So How could I use these observations to make a concise rigorous argument?

    Would I be able to incorporate that 1 and n are both relatively prime to any other number in the sequence?
     
  7. Aug 28, 2012 #6
    Notice that modulo 3, we have that 1=4=7. So you have just found two solutions.

    When n=3, the solutions are 1 and 2.
    When n=4, what are the solutions then?? Notice that 1=5=9 again.
     
  8. Aug 28, 2012 #7
    ok, I see the pattern now...

    For n=4, two solutions to x2=1, are 1 and 3.

    For n=5, two solutions to the equation are 1 and 4.

    For n=6, two solutions to the equation are 1 and 5.

    Is that enough proof to establish that the answers are always, at least, 1 and (n-1) ?
     
  9. Aug 28, 2012 #8
    No, that's not enough proof. You just found the pattern! Now you need to prove that 1 and n-1 are always solutions to x2=1.
     
  10. Aug 28, 2012 #9
    ok, so proving for 1 is trivial:

    12=1.

    Then I plugged in (n-1) to the equation and noticed:

    (n-1)2=1, (1)

    n2-2n+1=1. (2)


    I factored out to n(n-1)=0, but something tells me (2) is where I should be making my argument. If we "mod out" n2-2n, then we essentially have 0+1=1.

    Or if we note that (n2-2n)/n = n-2, and n-2+1=1 is n-1=1.

    Any of this getting closer?
     
  11. Aug 28, 2012 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    You 'noticed' what you want to prove. That's making it a little confusing. Just start with (n-1)^2=n^2-2n+1. Which terms in that expression are equal to 0 mod n?
     
  12. Aug 28, 2012 #11
    Certainly 2n mod n is equal to 0.

    And n^2 mod n is equal to 0, since both 2n and n^2 are divisible by n.

    So we would have (n-1)^2=0+0+1, or (n-1)^2=1, our solution?
     
  13. Aug 28, 2012 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Sure. You've got it.
     
  14. Aug 28, 2012 #13
    Great! Thanks everyone for your help and patience, Much better understanding of these concepts now!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook