Is there a misprint in this group theory exercise?

[pdelong]

I'm currently making my way through "Groups and Symmetry", by M. A. Armstrong [ISBN 0387966757], and I'm stuck on what seems like it should be a very simple exercise. Page 14, problem 3.8, states:

Show that if a subset of {1, 2, ..., 21} contains an even number, or contains the number 11, then it cannot form a group under multiplication modulo 22.

However, I can't make this work unless I change the "or" to an "and". So, is this a misprint, or am I missing something blindingly obvious?

Later,
Paul.

 

[fourier jr]

edit: never mind, maybe you're right. Anyway, there's a theorem that says the only cyclic multiplicative groups are the ones with prime order, which solves this problem. I think it's "and" because you need to have an even multiple of 11 to get 0 (mod22), which has no inverse and also isn't even in the group.

 

[Muzza]

Well... Suppose that A is a subset of {1, 2, ..., 21} that contains at least one even number, and suppose that A forms a group (where the operation is multiplication modulo 22). Let 2k $$\in$$ A. 2k has to have an inverse, i.e a number x $$\in$$ A such that 2k * x = 1 (mod 22). But this is equivalent to saying that there exists a number y $$\in \mathbb{N}$$ such that 2kx - 1 = 22y. We see that 2 divides the right-hand side of the equation, but not the LHS, so we can never have equality (in the integers). Contradiction.

You can easily extend this argument to cover 11 as well.

This is basically a small special case of a more general theorem that says that only those numbers coprime to n, will have a multiplicative inverse modulo n (hope I phrased that correctly).

 

[fourier jr]

edit: I thought about this problem again last night & forgot the stuff about the totient function. argh

 

[AKG]

Well... Suppose that A is a subset of {1, 2, ..., 21} that contains at least one even number, and suppose that A forms a group (where the operation is multiplication modulo 22). Let 2k $$\in$$ A. 2k has to have an inverse, i.e a number x $$\in$$ A such that 2k * x = 1 (mod 22). But this is equivalent to saying that there exists a number y $$\in \mathbb{N}$$ such that 2kx - 1 = 22y. We see that 2 divides the right-hand side of the equation, but not the LHS, so we can never have equality (in the integers). Contradiction.

You can easily extend this argument to cover 11 as well.

This is basically a small special case of a more general theorem that says that only those numbers coprime to n, will have a multiplicative inverse modulo n (hope I phrased that correctly).

But does 1 have to be the identity? For the numbers x = 1, 11, and 12, we have x*x = x(mod22). We might be able to form a very small group with some number other than 1 as its identity. I'm sure there's a reason why that's wrong though.

 

[Muzza]

Damn, that's true. I simply figured that "1 is the identity" went without saying, but I guess it doesn't.

 

[matt grime]

If as you say 12 satisfies 12*12=12 mod(22) then {12,*} is a group under multiplication. i think we are supposed to assume that 1 is the identity.

 

[matt grime]

Anyway, there's a theorem that says the only cyclic multiplicative groups are the ones with prime order

no there isn't, in fact there isn't one even remotely like it. there's a cyclic group of every order. the simple ones have prime order.

 

[fourier jr]

no there isn't, in fact there isn't one even remotely like it. there's a cyclic group of every order. the simple ones have prime order.

lol maybe i should look these things up before posting. i was pretty sure i would make an ass of myself by responding in any way. maybe i was thinking of something to do with finite fields or something.

 

[matt grime]

There is a finite field of order q iff q is a prime power.

 

[Hurkyl]

Also, abelian groups of prime order are necessarily cyclic.

 

[pdelong]

But does 1 have to be the identity? For the numbers x = 1, 11, and 12, we have x*x = x(mod22).

But that isn't sufficient to make x an identity (is it?). Unless you're dealing with the degnerate case of a group consisting of one element.

 

[matt grime]

There's nothing degenerate about a group with one element.

 

[AKG]

But that isn't sufficient to make x an identity (is it?). Unless you're dealing with the degnerate case of a group consisting of one element.

No it's not sufficient. I didn't check that 11 and 12 worked for any other numbers, but I was only provoking a proof that 1 must be the identity, otherwise the problem is rather simple. And I believe the set {1,11} works. 11 has two inverses, but I don't know if inverses have to be unique.

 

[matt grime]

identities must be unique, inverses must be unique, you've demonstrated that the one element set {11} with mult mod 22 is the trivial group, as is {12}

in your example {1,11} there are two identities by your reasoning, that is not allowed, identities must be unique.

 

[pdelong]

But does 1 have to be the identity? For the numbers x = 1, 11, and 12, we have x*x = x(mod22).

But that isn't sufficient to make x an identity (is it?). Unless you're dealing with the degnerate case of a group consisting of one element.

 

[AKG]

identities must be unique, inverses must be unique, you've demonstrated that the one element set {11} with mult mod 22 is the trivial group, as is {12}

in your example {1,11} there are two identities by your reasoning, that is not allowed, identities must be unique.

I was looking for something like this. At Mathworld.com, I don't see it explicitly stating that inverses and identites have to be unique, but I would naturally assume they are. At wikipedia.com, there is an article on group(mathematics) where some "Simple Theorems" are listed, including:

• A group has exactly one identity element.
• Every element has exactly one inverse.

But no proof for these. This seems like somthing that would arise more from definition than deduction, but if not, can you provide a proof or a link that has a proof?

 

[matt grime]

Double posts? A group with one element is still a group it is not degenerate and is perfectly admissible.

 

[pdelong]

Double posts? A group with one element is still a group it is not degenerate and is perfectly admissible.

Oh, whoops. I guess the network error didn't completely trash my first attempt.

I didn't think "degenerate" implied "inadmissible". In any case, I didn't mean to imply that a group of one element somehow isn't a group.

 

[matt grime]

AKG's proof: Suppose e and f are identity elements in a group G, then e=ef since f is an identity, and f=ef since e is an identity hence e=f, now the proof for the uniqueness of inverses is left as an easy exercise, and an important one.

 

[AKG]

AKG's proof: Suppose e and f are identity elements in a group G, then e=ef since f is an identity, and f=ef since e is an identity hence e=f, now the proof for the uniqueness of inverses is left as an easy exercise, and an important one.

For a, b, and c in G, let ab = I = ba, and ac = I = ca, prove b = c.
ab = I
c(ab) = c(I)
(ca)b = c
(I)b = c
b = c, QED.

Let a = 11, b = 11, I = 11, c = 1. By the same argument, I can prove 1 = 11. What does this mean? I suppose by contradiction it shows some combination of the following:

• 11 is not the identity
• 1 is not an element of the group
• 11 is not an element of the group

 

[matt grime]

It means that the set {1,11} with multiplication mod 22 is not a group that is all. However the set {11} with multiplication mod 22 is a group, it is canonically isomorphic to the group {1} with multiplication mod 22 (canonical means that there is an isomorphism and that isomorphism is unique).

From reading the question and thinking about my initial reaction to it, then we were supposed to assume that 1 is supposed to be the identity element and show by Muzza's reasoning that we didn't have a group. However that isn't the only way of reading the question.

 

[mathwonk]

maybe what Fourier jr was referring to was the theorem expressing the structure of the multiplicative group of units in the ring of integers mod n, since that is the example given here.

I.e. in Z mod n, the group of units is cyclic if n is prime, but also if n is a power of an odd prime, and also if n = 2 or 4.

again the problem here is merely to describe the elements of that multiplicative group of units, not its structure.

perhaps the problem should have been stated as finding subgroups of the multiplicative group oif units, since that would specify the identity for multiplication.