1. Limited time only! Sign up for a free 30min personal 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!

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:


    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


    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


    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