Prime Order Groups: Understanding Lagrange's Theorem and its Corollary

  • Context: Graduate 
  • Thread starter Thread starter SiddharthM
  • Start date Start date
  • Tags Tags
    Groups Prime
Click For Summary

Discussion Overview

The discussion revolves around Lagrange's theorem and its corollary regarding groups of prime order, specifically focusing on the properties of cyclic groups and the implications of group operations under modular arithmetic. Participants explore the conditions under which certain sets can be considered groups and the existence of inverses within those groups.

Discussion Character

  • Technical explanation
  • Conceptual clarification
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants assert that every group of prime order must be cyclic, as the order of any subgroup must divide the order of the group.
  • One participant presents a counterexample using the set {1,...,11} under multiplication mod 12, arguing that an element (3) does not generate the group, which raises questions about the validity of Lagrange's theorem in this context.
  • Another participant points out that the set {1,...,11} with multiplication mod 12 does not form a group, as it fails to meet the necessary group properties.
  • Several participants discuss the implications of the binary operation of multiplication mod n, particularly emphasizing that if n is not prime, the set cannot be a group due to the presence of zero in the product of its elements.
  • There is a proposal that if n is prime, the set {1,...,n-1} is closed under multiplication mod n, and thus could form a group.
  • Participants explore the existence of inverses in groups, referencing Lagrange's theorem and discussing the conditions under which inverses can be proven to exist.
  • One participant introduces a theorem regarding finite cancellation semigroups, suggesting it may apply to the current discussion about group properties.
  • Another participant provides a proof outline for showing that a finite cancellation monoid is a group, emphasizing the need to demonstrate the cancellation property.

Areas of Agreement / Disagreement

Participants express disagreement regarding the validity of using the set {1,...,11} under multiplication mod 12 as a group. While some agree on the implications of Lagrange's theorem for prime order groups, others challenge the application of the theorem based on the examples provided. The discussion remains unresolved regarding the specific properties of the set in question and the implications for group theory.

Contextual Notes

Limitations include the unclear status of the set {1,...,11} under multiplication mod 12 as a group, as well as the assumptions made about the closure and existence of inverses in non-prime cases. The discussion also highlights the need for clarity in definitions and operations when discussing group properties.

SiddharthM
Messages
176
Reaction score
0
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=9
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 because i can't see it.
 
Physics news on Phys.org
{1,..,11} with * mod 12 isn't a group.
 
SiddharthM said:
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=9
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 because i can't see it.
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 ...
 
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 because if (ab)c is congruent to r modn then so is a(bc).

How do I prove an inverse exists?
 
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.
 
SiddharthM said:
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 because if (ab)c is congruent to r modn then so is a(bc).

How do I prove an inverse exists?

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.
 
SiddharthM said:
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.

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?
regards...Cliowa
 
SiddharthM said:
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.
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:
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.

QED

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:
  • #10
SiddharthM said:
Say a and b are not equal, this means that (b-c)/n is not an integer
I assume you mean "b and c are not equal"? And furthermore, that you really meant "b and c are not equal modulo n"?

then [a(b-c)]/n isn't an integer either.
Why does that follow?
 
  • #11
this reminds me of a paper titled, on groups of order one.
 
  • #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.
 
  • #13
SiddharthM said:
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.
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)
 

Similar threads

MHB Is Every Group of Order 25 Cyclic?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Is G simple?Is G simple? A different approach using Sylow theorems
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad First Sylow Theorem: Group of Order ##p^k## & Cyclic Groups
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Groups of Prime Power Order
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
1K
Graduate Groups of prime order structurally distinct?
  • · Replies 4 ·
Replies
4
Views
2K
Graduate On the equivalent definitions for solvable groups
  • · Replies 3 ·
Replies
3
Views
3K
Graduate Question about normal subgroups/Lattice Isomorphism Theorem
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Questions about non existence of GCDs vs (coimages, cokernels)
  • · Replies 12 ·
Replies
12
Views
1K
MHB Why is the order of b equal to the order of G/H ?
  • · Replies 6 ·
Replies
6
Views
2K