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!

Multiplication groups

  1. Aug 16, 2011 #1
    1. The problem statement, all variables and given/known data
    Let U(n) be the set of all positive integers less than n and relatively prime to n. Prove that U(n) is agroup under multiplication modulo n


    2. Relevant equations



    3. The attempt at a solution

    n [itex] | [/itex] a-a' implies n[itex] |[/itex] b(a-a') =ab-a'b
    and n[itex] |[/itex]b-b' implies n[itex] |[/itex]a'(b-b') =a'b-a'b'
    implies n[itex] |[/itex]ab-a'b+a'b-a'b'
    =ab-a'b'
    ie ab=a'b'modn

    have i done enough with this?
     
    Last edited: Aug 16, 2011
  2. jcsd
  3. Aug 16, 2011 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Groups

    You need to state precisely what each of those is showing. In order that a set, together with an operation, be a group you must show:
    1) The set is closed under the operation.
    2) The operation is associative.
    3) There is an identity for the operation in the set.
    4) There is an inverse for every member of the set.

    Exactly which of your "implications" does each of those?
     
  4. Aug 16, 2011 #3
    Re: Groups

    if ac[itex]\equiv[/itex]ab mod n
    then n [itex]|[/itex] ac.ab =a(c-b) by Euclids Therom as gcd(n,a) = 1
    so we must have n [itex]|[/itex] c-b
    ie c[itex]\equiv[/itex] b mod n
     
  5. Aug 16, 2011 #4

    fzero

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Re: Groups

    For any [itex]a\in U(n)[/itex], [itex]a<n[/itex], so [itex]n|a[/itex] is false. If it were true, you'd find that [itex]ab\mod n=0[/itex].

    You need to explicitly show that [itex] ab \mod n[/itex] is both less than [itex]n[/itex] and relatively prime to [itex]n[/itex]. As a general suggestion, a good proof includes some text to explain the assumptions and logic behind the steps. You'd have caught your mistake if you actually tried to translate the properties stated into the equations you were using.
     
  6. Aug 16, 2011 #5

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Groups

    That is not at all relevant. It shows that the "cancelation" law applies to this operation but does NOT show that every member has an inverse. The set of all integers with the operation of multiplication satisfies "cancelation" but is not a group.

    (This was in response to gtfitzpatrick's post. fzero got his in while I was typing.)
     
  7. Aug 16, 2011 #6
    Re: Groups

    first i need to show that multiplication mod n is a binary operation on U(n)

    suppose a,b [itex]\in[/itex] U(n) then a has multiplicative inverse [itex]a^{-1}[/itex] and b similarly has [itex]b^{-1}[/itex]

    now
    [itex](b^{-1}a^{-1})(ab) = (b^{-1}(a^{-1}a)b) = (b^{-1}(1)b) = 1 [/itex]
    and
    [itex](ab)(b^{-1}a^{-1}) = (a(bb^{-1})(a^{-1}) = (a(1)a^{-1}) = 1 [/itex]
    so [itex](b^{-1}a^{-1})[/itex] is the multiplicative inverse of ab and ab is a unit. Therefore multiplication mod n is abinary op on U(n)

    Next assocativity

    choose a,b,c [itex]\in[/itex] U(n)

    we want to show (ab mod n)c mod n = a(bc mod n) mod n

    ab mod n = ab + mn
    then (ab + mn)c mod n = (ab + mn)c + ln = abc + (mc + l)n for m,l [itex]\in[/itex] Z
    likewise a(bc mod n) mod n = a(bc + pn) + qn = (abc + (ap+q)n for p,q [itex]\in[/itex] Z
    but clearly abc + (mc+l)n [itex]\equiv[/itex] mod n abc + (qp+q)n

    identity e=1 works since 1a = a1 = a for a [itex]\in[/itex] U(n)

    next inverses
     
  8. Aug 16, 2011 #7
    Re: Groups

    inverses
    a [itex]\in[/itex] U(n) gcd (a,n) = 1 => sa+tn=1
    working on mod n we see that sa [itex]\equiv[/itex] mod n 1. But we have thus found our inverse to a, s mod n. We should verify that gcd(s,n) = 1 to see that this inverse is actually in the group, but the equality sa+tn=1 infact inplies gcd(s,n)=1

    this seems to be a very dragged out proof, is it correct?
     
  9. Aug 16, 2011 #8

    fzero

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Re: Groups

    You still haven't proven that [itex]U(n)[/itex] is closed under the product. This step should actually be done first, as the other group properties depend on it being true.
     
  10. Aug 16, 2011 #9
    Re: Groups

    a,b [itex]\in[/itex] U(n) => gcd(a,n)=gcd(b,n)=1

    assume gcd(ab,n) = 1
    =>x(ab)+y(n)=1
    gives (xa)b+(y)n=1 => gcd(b,n)=1
    also (xb)a+(y)n = 1 => gcd(a,n)=1

    let x be a prime integer such that x[itex]|[/itex]ab and x[itex]|[/itex]n
    then x[itex]|[/itex]a or x[itex]|[/itex]b , given gcd(a,n)=gcd(b,n)=1 =>x=[itex]\pm[/itex]1
    therefore gcd (ab,n) = 1
    ie ab [itex]\in[/itex] U(n)
     
  11. Aug 16, 2011 #10

    fzero

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Re: Groups

    This part technically doesn't contribute to closure, but is a nice consistency check.

    It is obvious, but you should also remark that [itex]ab \mod n < n[/itex] for completeness.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook