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

[SiddharthM]

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.

 

[matt grime]

{1,..,11} with * mod 12 isn't a group.

 

[cliowa]

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 ...

 

[SiddharthM]

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?

 

[SiddharthM]

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.

 

[cliowa]

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.

 

[cliowa]

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

 

[Hurkyl]

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. 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)

 

[SiddharthM]

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.

 

[Hurkyl]

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?

 

[mathwonk]

this reminds me of a paper titled, on groups of order one.

 

[SiddharthM]

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.

 

[Hurkyl]

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)