This sheet introduces subgroups—the fundamental substructures of groups—and cyclic groups, the simplest class of groups.
Subgroups#
Definition 2.1. Let be a group. A nonempty subset is called a subgroup of if is closed under the operation and, with the induced operation, itself forms a group. We denote this by .
Theorem 2.2 (Subgroup Criterion). A nonempty subset of a group is a subgroup if and only if for all , we have .
Theorem 2.3 (Finite Subgroup Criterion). If is a finite nonempty subset of a group and is closed under the group operation (i.e., for all ), then is a subgroup of .
We first prove itself is a group.
Associativity: For all , , therefore holds.
Identity: Let , considering sequence , where . Since H is finite, there must exist a minimum so that or would become a infinite sequence and thus H is infinite. Hence,
Inverse: As mentioned above, for each , there must exist a minimum so that . Then .
Therefore itself is a group.
Given that it is an nonempty subset of and is closed under the group operation, by definition 2.1 it is the subgroup of .
Theorem 2.4. Let . Then:
(a) The identity element of is the identity element of .
(b) The inverse of an element in is its inverse in .
This is also shown in proof 2.3.
Definition 2.5. The trivial subgroup of a group is the subgroup consisting only of the identity element. A subgroup is called a proper subgroup if .
Example 2.6. The even integers form a subgroup of .
Example 2.7. The set of rotations in the dihedral group forms a subgroup.
Example 2.8. The set of permutations of a set that fix a particular element forms a subgroup of .
Theorem 2.10. The intersection of any collection of subgroups of a group is again a subgroup of .
Definition 2.11. Let be a nonempty subset of a group . The subgroup generated by , denoted , is the intersection of all subgroups of containing . Equivalently, consists of all finite products of elements of and their inverses. If , we say that generates .
Exercise 2.12. Show that the union of two subgroups is a subgroup if and only if one is contained in the other.
Exercise 2.13. Let and . Prove that is a subgroup of if and only if .
Proof:
is a subgroup of
Firstly, is non-empty since , .
And identity is in .
Associativity is inheritant.
Inverse:
If then for all the , and thus .
Then is a group itself and a subset of . By definition 2.1, it's a subgroup of .
is a subgroup of
is a group itself. Therefore for all , .
Evidently is equal to .
Therefore, all the elements in are in i.e.
Similarly, .
Hence, .∎
Cyclic Subgroups#
Definition 2.14. Let be a group and . The cyclic subgroup generated by is
where , ( factors) for , and for .
Definition 2.15. A group is cyclic if for some . Such an element is called a generator of .
Example 2.16. is cyclic; both and are generators.
Example 2.17. is cyclic; is a generator.
Example 2.18. The group of th roots of unity in is cyclic under multiplication.
Definition 2.19. The order of an element , denoted , is the smallest positive integer such that . If no such exists, has infinite order.
Theorem 2.20. If has finite order , then:and these elements are distinct.
Proof:
By definition 2.19 𝑛 is the smallest positive integer such that .
Therefore,
- for all . By definition2.14
- Suppose, for contradiction, there exists . Then by multipling on both side we deduce , where and . It's contradict to that is the order of . Hence there n elements are distinct.
Thus, we are done.
∎
Theorem 2.21. For any , .
Proof:
By Theorem 2.20, If has finite order i.e. , then:
consists n distinct elements.
Thus, For any , .∎
Theorem 2.22. If , then divides .
Theorem 2.23 (Order of a Power). Let have order . Then for any integer :
Proof:
Let .
Since by Theorem 2.21, for any , , .
We now consider
Since , the smallest positive integer h such that is .
Therefore,
Remark: gcd is the "viable" step size for k to finish the "run" at length n. By "viable", we mean that it actually contributes reaching the multple of n.∎
Corollary 2.24. generates iff .
Proof:
When ,
applying Theorem 2.23,
By Theorem 2.21,
Since by definition , and both of them have order n (have the same number of elements),
.
When generates .
Therefore ∎
Exercise 2.25. Find the order of each element in .
and it is generated by 1.
The order of 1 is 6.
The order of 2, here, is
The order of 3, here, similarly, is
The order of 4, here, similarly is
The order of 5, here, similarly is
The order of 0, here, similarly is 1.
Exercise 2.26. Find the order of each element in .
Exercise 2.27. Let have order . Find the orders of .
For , order is
For , order is
For , order is
For , order is
For , order is
Subgroups of Cyclic Groups#
Theorem 2.28. Every subgroup of a cyclic group is cyclic.
Proof:
Take a subgroup of a cyclic group with order n.
The elements of must all have the form .
In non-trivial case, i.e. the subgroup is not , which is cyclic, there must exist such that is the smallest among all the .
Then must also contain , where .
That is, .
Suppose there exists in where .
Suppose . By Bézout's lemma, there exists such that .
Therefore, similarly, there exists . Since and , then , which contradicts the supposition .
Hence, for all the in , , that is .
Therefore, in conclusion, .
When is infinite.
Take a subgroup consisting of , there must exist such that is the smallest among all the . Then .
Similarly:
Suppose there exists in where .
Suppose . By Bézout's lemma, there exists such that .
Therefore, similarly, there exists . Since and , then , which contradicts the supposition .
Hence, for all the in , , that is .
Therefore, ∎
Theorem 2.29. Let be a cyclic group of order .
(a) For each divisor of , there is exactly one subgroup of order , namely .
Proof:
Suppose, for contradiction, that there exists another subgroup of order generated by
, and .
.
Then , which is a subgroup of .
Since both of them have order , .
Therefore, the supposition fails: there only exists exactly one subgroup of order , namely .
(b) The subgroups of are precisely for each divisor of .∎
Proof:
On the one hand, by (a), we deduce that all for each divisor of are subgroups of
On the other hand, suppose, for contradiction, there exists another subgroup(cylic, by theorem2.28) , where is not a divisor of , , and does not equal to or m would be a divisor of .
By Bezout's lemma, there must exists , .
Then in , there must exists , where .
However, since the subgroup is generated by , .
Therefore, , which contradicts to the supposition.
Thus, there does not exist another subgroup(cylic, by theorem2.28) , where is not a divisor of .
So the subgroups of are precisely for each divisor of .
(c) If , then .∎
Theorem 2.30. Let be infinite cyclic. Then every nontrivial subgroup is infinite cyclic, and the subgroups are precisely for .
Proof:
Apparently all the for are infinite subgroups of .
By theorem2.28, all of the subgroup of a cyclic group are cyclic.
Thus, they must all have the form for .
Therefore, the subgroups are precisely for .∎
Theorem 2.31 (Subgroup Lattice of Cyclic Groups). For a cyclic group of order , the subgroups form a lattice under inclusion, ordered by divisibility: iff .
Proof:
If , , .
If , then . Therefore, .
Thus, iff .∎
Exercise 2.32. Find all subgroups of .
generators: 1 2 3 4 6 12
Exercise 2.33. Find all subgroups of .
generators: 1 2 3 6 9 18
Exercise 2.34. How many subgroups does have? List them.
generators: 1 2 3 4 6 8 12
Exercise 2.35. Let be cyclic of order . Prove that generates if and only if .
Generators of Cyclic Groups#
Definition 2.36. The Euler phi-function is the number of integers with such that .
Theorem 2.37. A cyclic group of order has exactly generators.
By theorem 2.23, . The generator of should have order . Then that requires to be .
By definition 2.36, is the number of all integers with such that , and thus the number of generators of .
Example 2.38. has generators. They are .
Exercise 2.39.
(a) Find all generators of .
1, 3, 5,7,9,11,13,17,19
(b) Find all generators of .
1,2,4,7,8,11,13,14
(c) How many generators does have?
25
(d) For which does have exactly 2 generators? Exactly 4 generators?
3, 4, 6; 5, 8, 10, 12
Exercise 2.40. Prove that if is cyclic of order , then has exactly one subgroup of each order dividing .
Exercise 2.41. Let be a cyclic group of order . How many elements of order does have for each ? Express your answer in terms of .
Summary#
We have introduced:
- Subgroups and the subgroup criterion
- Finite subgroup criterion (closure under operation suffices for finite subsets)
- The subgroup generated by a set
- Cyclic subgroups and generators
- The order of an element
- The order of a power:
- Classification of subgroups of cyclic groups
- Subgroup lattice of cyclic groups
- Euler's phi-function and counting generators
- The Fundamental Theorem of Cyclic Groups