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

Groups of prime order

  1. Oct 27, 2007 #1
    Ok, well a corollary to Lagrange's theorem is that every group of prime order, call it G, must be cyclic. Consider the cyclic subgroup of G generated by a (a not equal to e), the order of the subgroup must divide the order of p, since the only number less than or equal to p that divides p is p, the cyclic subgroup of G is G and ANY element of G that is not the identity generates G.

    Now, looking at the finite group of {1,....,11} whose multiplication is ab reduced mod12.

    Take 3, by the corollary above, 3 must generate the entire group because 11 is a prime number.

    3*3*3=3 (because 27 = 3mod12)
    3*3*3*3= 9 (because 81 =9mod12)
    (3*3*3*3)*3=9*3 = 3

    and so on and so forth, so 3 does NOT generate the group {1,...,11}.

    Clearly Lagrange's theorem is not false and neither is it's corollary above. So I must be missing something pretty simple and i feel retarded cuz i can't see it.
  2. jcsd
  3. Oct 27, 2007 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    {1,..,11} with * mod 12 isn't a group.
  4. Oct 27, 2007 #3
    Your mod-calculations are a bit odd. When you talk about taking {1,...,11} with multiplication mod 12, you identify all mupltiples of 12 with 1, etc, i.e. you identify 24 and 1, 25 and 2, 26 and 3, 27 and ...
  5. Oct 27, 2007 #4
    yeah, i think i got confused, tell me if i am wrong here regarding the binary operation of ab reduced modm.

    given ab we can write ab=mq +r with r less than m (division algorithm) so

    so ab reduced modm is equal to r.

    I get why there is a problem with there being a problem with the set {1,...n-1} and the binary operation of ab reduced modn. If n is NOT prime then the set {1,...,n-1} contains it's prime decomposition, whose product is then ZERO which is NOT contained in our set. Hence it is not a group if n is not prime.

    Now if it n is prime then no combination of elements in {1,...,n-1} can multiply to get a multiple of n. So if we use the binary operation ab reduced modn we will always obtain a nonzero natural number less than n. It is therefore closed under our operation.

    associativity is obvious cuz if (ab)c is congruent to r modn then so is a(bc).

    How do I prove an inverse exists?
  6. Oct 27, 2007 #5
    I think i can prove inverses exist.

    A corollary to lagrange's theorem is that if a group has order m, for any element a in G. a^m=e.

    so if our finite group under multiplication has order m=n-1 then a^m-1 is an iverse, and since we already proved closure, a^m-1 is in G.
  7. Oct 27, 2007 #6
    So it should be clear to you that in your case (where n=12) you don't have a group with respect to the usual mod operation. If you consider an additive group {0,...,n-1}, where 0 is the identity, taking mod n works. Notice that the crucial point is that for 2 numbers to be identified mod n can yield value 0, whereas if you state that you identify multiples of n with 1 etc. you don't have that problem.
  8. Oct 27, 2007 #7
    You don't even need Lagrange for that. Say you have a cyclic group G of order m, then for any a in G the order of a is at most n, right? Do you know what to do next?
  9. Oct 27, 2007 #8


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Of course, you can't apply Lagrange's theorem if you don't already know it's a group!

    There is a general theorem:
    Theorem: Let M be a finite cancellation semigroup. Then M is a group.​
    (A cancellation semigroup is one where ac = bc implies a = b, and likewise for ca = cb)

    The proof is left as an exercise. :wink: Can you apply this theorem to your case?

    (Incidentally, there is a very straightforward algorithm for inversion. Maybe if you unrolled the definition of "equivalent modulo p" it will give you a hint)
    Last edited: Oct 27, 2007
  10. Oct 27, 2007 #9
    Theorem: Let M be a finite cancellation monoid. Then M is a group.

    Proof: We show any element has an inverse, call the arbitrary element of M, c. Since M is finite the integer powers of c have a finite # of distinct elements. So we can find an integer m so that (c)^m=(c)^n with n<m. (this is b/c the integer powers of c must repeat if M is finite)

    This is another way of writing (c)^(m-n) *(c)^n = e * (c)^n and since M is a cancellation monoid this implies that

    (c)^(m-n)=e. WLOG m-n>1 b/c if m-n=1 then c is the identity and trivially has an inverse.

    Now if m-n>1 then (c)*(c)^(m-n-1)=e. Put b=(c)^(m-n-1). Then
    cb=e implies that b(cb)=b*e=b. Since M is associative this means (bc)b=e*b and by cancellation: bc=e. So b is an inverse of c.


    Now back to the concrete example. My burden of proof is to show that G has the cancellation property - because i have shown it is associative and contains the identity. Note also that in this example, the binary operation is abelian, so it suffices to prove the cancellation law from one side.

    We prove the cancellation law by contraposition. Say a and b are not equal, this means that (b-c)/n is not an integer then [a(b-c)]/n isn't an integer either. If r=ab=ac then
    (ab-r)/n and (r-ab)/n would be integers, then there sum would be integers as well. But we have established that their sum is not an integer, so ab can't be equal to ac.

    Hence {1,...,n-1} is a group under multiplication modn if n is prime. Moreover this is a, if and only if, relationship because if n is not prime we've established that we don't have closure.
    Last edited: Oct 27, 2007
  11. Oct 27, 2007 #10


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I assume you mean "b and c are not equal"? And furthermore, that you really meant "b and c are not equal modulo n"?

    Why does that follow?
  12. Oct 28, 2007 #11


    User Avatar
    Science Advisor
    Homework Helper

    this reminds me of a paper titled, on groups of order one.
  13. Oct 28, 2007 #12
    yes, i mean b and c are not equal modulo n. Since n is prime and doesn't divide b-c, if n divides the value a(b-c), it must divide a - which is impossible because if a is in G its decomposition cannot contain the prime n.

    Sorry I should have been clearer.

    I really appreciate you looking over my proof for me.
  14. Oct 28, 2007 #13


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Not all numbers x have the property that if x divides yz then x divides at least one of y and z...

    (Of course, it's true if n is prime, or if y is relatively prime to n)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook