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!

Proving U(n) is a group mod n

  1. Jan 30, 2016 #1
    1. The problem statement, all variables and given/known data
    Show that the set U(n) = {x < n : gcd(x, n) = 1} under multiplication modulo n is a group.
    2. Relevant equations
    3. The attempt at a solution

    I know that it is important to have the gcd=1 other wise you would eventually have an element that under the group operation would be a multiple of n which would have a remainder of 0 and could generate nothing new after that under multiplication. NumberedEquation4.gif xr+bn=gcd(x,n)=1 .
     
  2. jcsd
  3. Jan 30, 2016 #2

    ChrisVer

    User Avatar
    Gold Member

    how do you show that a set of elements is/forms a group?
     
  4. Jan 30, 2016 #3
    To make sure that inverse exist we need to have 2 group elements a,b such that ab=cn+1 , gcd(a,n)=1 and gcd(b,n)=1 and c is a multiple of n.
    so ab-cn=1. im trying to figure out a way to prove that 2 element multiplied together will get me one more than a multiple on n.
     
  5. Jan 30, 2016 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If a and b are relatively prime then there exist integers k and l such that ak+bl=1. Use that.
     
  6. Jan 30, 2016 #5
    if ab-cn=1 then gcd(ab,cn)=1 because these are consecutive natural numbers. if they shared common factors then it should divide their difference but their difference is 1.
    let a be a natural number such that gcd(a,n)=1 and a<n, now we need to look for a natural number b such that ab-cn=1, by the euclidean algorithm integers should exist.
    we know that gcd(b,cn)=1 otherwise if they shared a common factor this could be factored out and then we would have a product of 2 integers equallying one. but we just factored out their common factor that is larger than 1 so this is a contradiction. for the moment I am going to look at the case where ab-n=1.
    ab=n+1, let a and b <n, claim b< n, assume for contradiction that b>n-1, if b were at least n and a was >2 then ba=2n which is larger than n+1, so this is a contradiction therefore b<n, so such a b exists, there exists a,b such that ab=n+1,
     
  7. Jan 30, 2016 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    If you know there are integers b and c such that ab-cn=1, then you have pretty much shown that a has an inverse, haven't you? I don't know what you are trying to say with the rest of that argument.
     
  8. Jan 30, 2016 #7

    ChrisVer

    User Avatar
    Gold Member

    take the concrete example of [itex]U(8) = \{ 1, 3,5, 7 \}[/itex]..
    what do you get by trying some of the multiplications?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Proving U(n) is a group mod n
Loading...