Definition 2.4.1 (Subgroup). A subgroup of a group is a nonempty subset such that:
- Closure: ;
- Inverses: .
We write (or if , a proper subgroup).
If and , then . So , with the operation of restricted to it, is a group in its own right; associativity holds in because it holds in . Every group has the trivial subgroup and the subgroup itself.
Example 2.4.2 (First examples of subgroups).
- , and .
- For each , the multiples of , , form a subgroup of .
- The rotations form a subgroup of .
- If for , then . For a family of abelian groups, .
- , granting the multiplicativity of the determinant (Theorem 5.4.7).
Proposition 2.4.3 (Subgroup criterion). A nonempty subset is a subgroup iff .
Proof. () If and , then (inverses) and (closure).
() Assume the condition. Since , pick . Then . For any , . For , we have , so . ∎
Proposition 2.4.4 (Intersections of subgroups). Let be a nonempty family of subgroups of . Then is a subgroup of . In particular, if and are subgroups of , so is .
Proof. Each contains , so the intersection is nonempty. If and lie in every , then so do and , since each is a subgroup; so and lie in the intersection. ∎
Unions, on the other hand, are almost never subgroups: is a subgroup only when one of , contains the other. Indeed, suppose neither contains the other, and pick and . If , then , a contradiction; and if , then , also a contradiction. So . For example, contains and but not , so it is not a subgroup of , while is a subgroup.
Theorem 2.4.5 (Subgroups of ). Let be a subgroup of . Then either or , where is the smallest positive element of .
Proof. If , we’re done. Otherwise, contains some nonzero element ; then too, so contains a positive element. Let be the smallest positive element of .
We show . First, , since is closed under addition and negation: , and .
For : take any . By the division algorithm, with . Then (since ). By minimality of , we must have , so . ∎
So the subgroups of are exactly the with (where ). Some of them form chains, , but not all subgroups are comparable: neither of and contains the other. The theorem gives a quick route to the basic facts about greatest common divisors.
Proposition 2.4.6 (Greatest common divisor). Let , not both zero, and let be their greatest common divisor. Then:
- ;
- if divides both and , then divides ;
- there exist such that (Bézout’s identity).
Proof. The set is a subgroup of : it contains , and . It contains and , not both zero, so , and by Theorem 2.4.5, , where is the smallest positive element of . Since and lie in , divides both and . Since , we have for some ; so if divides and , then divides , and in particular . Thus is a common divisor of and that is at least as large as every other one, that is, . This proves (a) and (c), and (b) was shown along the way. ∎
Corollary 2.4.7 (Coprimality criterion). Integers and are coprime (i.e., ) iff with .
Proof. If , this is Bézout’s identity. Conversely, if , every common divisor of and divides , so . ∎
Corollary 2.4.8 (Euclid’s lemma). Let be integers with and . Then . In particular, if is prime and , then or .
Proof. By Bézout’s identity, for some . Multiplying by gives , and divides both terms on the right, so . For the second statement, suppose . Since the only positive divisors of are and , we have , and the first statement gives . ∎
As an application we obtain a multiplicative group of integers mod . For and , let be the remainder of on division by (multiplication mod ). As for addition, and are both the remainder of , so multiplication mod is associative, and is an identity for it.
Proposition 2.4.9 (Units mod ). Let . The set forms a group under multiplication mod . Its order is , the number of integers coprime to (Euler’s totient function).
Proof. Closure: Let , and let , so that for some . If a prime divided both and , it would divide , hence or by Euclid’s lemma, contradicting coprimality. Since every integer greater than has a prime divisor, .
Identity: is coprime to .
Inverses: If , then by Bézout’s identity there are with . Write with . Then , so is coprime to by Corollary 2.4.7, and is one more than a multiple of , that is, . So is an inverse of .
The elements of are the integers coprime to (neither nor is coprime to ), so there are of them. ∎
2.4.1 Generated Subgroups and Cyclic Groups
Given a subset , what is the smallest subgroup of containing ? There is at least one subgroup containing , namely itself, and by Proposition 2.4.4 the intersection of all of them is again a subgroup.
Definition 2.4.10 (Subgroup generated by a set). For , the subgroup generated by is It is a subgroup of that contains and is contained in every subgroup containing ; so it is the smallest subgroup of containing . If , we say that generates . For we write .
Proposition 2.4.11 (Elements of a generated subgroup). For , where the empty product () is . In particular, for , .
Proof. Let be the set on the right. It contains ; the product of two such words is again a word; and the inverse of a word is a word, since by Proposition 2.1.5 and induction on . So is a subgroup containing , and hence . Conversely, a subgroup containing contains every with and all products of these, so it contains ; hence . When , a word in and equals , where is the number of factors minus the number of factors . ∎
Definition 2.4.12 (Cyclic groups). A group is cyclic if for some . The element is called a generator. For any , the subgroup is the cyclic subgroup generated by .
Example 2.4.13 (Cyclic groups and generators). and are cyclic, as is . By Theorem 2.4.5, every subgroup of is cyclic: . The rotation subgroup of is , and by Proposition 2.2.15. By contrast, , the group of integer matrices with under multiplication, is not cyclic (it is not even abelian: the matrices and of Example 2.2.18 lie in it and do not commute), but it can be generated by two elements (a fairly hard exercise without a hint; we return to this group in Section 12.4).
Definition 2.4.14 (Order of an element). The order of , denoted or , is the smallest positive integer such that , or if no such exists; in the latter case we say that has infinite order.
Do not confuse the order of an element with the order of a group. The two are related: , as we prove in Proposition 2.6.1.