This sheet introduces subgroups—the fundamental substructures of groups—and cyclic groups, the simplest class of groups.


Subgroups#

Definition 2.1. Let (G,∗)(G, *) be a group. A nonempty subset H⊆GH \subseteq G is called a subgroup of GG if HH is closed under the operation ∗* and, with the induced operation, HH itself forms a group. We denote this by H≤GH \leq G.

Theorem 2.2 (Subgroup Criterion). A nonempty subset HH of a group GG is a subgroup if and only if for all a,b∈Ha, b \in H, we have a∗b−1∈Ha * b^{-1} \in H.

Theorem 2.3 (Finite Subgroup Criterion). If HH is a finite nonempty subset of a group GG and HH is closed under the group operation (i.e., ab∈Hab \in H for all a,b∈Ha, b \in H), then HH is a subgroup of GG.

Proof2.3Proof 2.3
We first prove HH itself is a group.
Associativity: For all a,b∈Ha,b\in H, a,b∈Ga,b \in G, therefore (ab)c=a(bc)(ab)c=a(bc) holds.
Identity: Let a∈Ha \in H, considering sequence aka^k, where k∈Z+k \in Z_{+}. Since H is finite, there must exist a minimum k0k_{0} so that ak0=ea^{k_0}=e or aka^k would become a infinite sequence and thus H is infinite. Hence, e∈He \in H
Inverse: As mentioned above, for each a∈Ha \in H, there must exist a minimum k0k_{0} so that ak0=ea^{k_0}=e. Then ak0−1a=e→a−1=ak0−1a^{k_{0-1}}a=e \to a^{-1}=a^{k_{0-1}}.
Therefore HH itself is a group.
Given that it is an nonempty subset of GG and is closed under the group operation, by definition 2.1 it is the subgroup of GG.

Theorem 2.4. Let H≤GH \leq G. Then:

(a) The identity element of HH is the identity element of GG.

(b) The inverse of an element in HH is its inverse in GG.

This is also shown in proof 2.3.

Definition 2.5. The trivial subgroup of a group GG is the subgroup {e}\{e\} consisting only of the identity element. A subgroup HH is called a proper subgroup if H≠GH \neq G.

Example 2.6. The even integers 2Z2\mathbb{Z} form a subgroup of (Z,+)(\mathbb{Z}, +).

Example 2.7. The set of rotations in the dihedral group DnD_n forms a subgroup.

Dn={r,s∣rn=s2=e,rs=sr−1}D_{n}= \{ r,s|r^n=s^2=e , rs=sr^{-1}\}

Example 2.8. The set of permutations of a set AA that fix a particular element a∈Aa \in A forms a subgroup of SAS_A.

Theorem 2.10. The intersection of any collection of subgroups of a group GG is again a subgroup of GG.

Definition 2.11. Let SS be a nonempty subset of a group GG. The subgroup generated by SS, denoted ⟨S⟩\langle S \rangle, is the intersection of all subgroups of GG containing SS. Equivalently, ⟨S⟩\langle S \rangle consists of all finite products of elements of SS and their inverses. If G=⟨S⟩G = \langle S \rangle, we say that SS generates GG.

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 H≤GH \leq G and K≤GK \leq G. Prove that HK={hk∣h∈H,k∈K}HK = \{hk \mid h \in H, k \in K\} is a subgroup of GG if and only if HK=KHHK = KH.

Proof:

HK=KH→HKHK=KH\to HK is a subgroup of GG
Firstly, HKHK is non-empty since e∈H,e∈Ke \in H, e\in K, e=e ⋅e∈HKe=e\ \cdot e \in HK.
And identity is in HKHK.
Associativity is inheritant.
Inverse:
If HK=KHHK=KH then for all the hkhk, k−1h−1∈KHk^{-1}h^{-1} \in KH and thus k−1h−1∈HKk^{-1}h^{-1} \in HK.
Then HKHK is a group itself and a subset of GG. By definition 2.1, it's a subgroup of GG.

HKHK is a subgroup of G→G\to HK=KHHK=KH
HKHK is a group itself. Therefore for all hkhk, k−1h−1∈HKk^{{-1}}h^{-1} \in HK.
Evidently {k−1h−1∣k∈K,h∈H}\{ k^{-1}h^{-1}|k \in K, h \in H \} is equal to {kh∣k∈K,h∈H}\{ kh|k \in K, h \in H \}.
Therefore, all the elements in KHKH are in HKHK i.e. KH⊂HKKH \subset HK
Similarly, HK⊂KHHK \subset KH.
Hence, HK=KHHK=KH.∎


Cyclic Subgroups#

Definition 2.14. Let GG be a group and a∈Ga \in G. The cyclic subgroup generated by aa is
⟨a⟩={an∣n∈Z},\langle a \rangle = \{a^n \mid n \in \mathbb{Z}\},
where a0=ea^0 = e, an=a∗a∗⋯∗aa^n = a * a * \cdots * a (nn factors) for n>0n > 0, and an=(a−1)−na^n = (a^{-1})^{-n} for n<0n < 0.

Definition 2.15. A group GG is cyclic if G=⟨a⟩G = \langle a \rangle for some a∈Ga \in G. Such an element aa is called a generator of GG.

Example 2.16. (Z,+)(\mathbb{Z}, +) is cyclic; both 11 and −1-1 are generators.

Example 2.17. (Zn,+n)(\mathbb{Z}_n, +_n) is cyclic; 11 is a generator.

Example 2.18. The group of nnth roots of unity in C\mathbb{C} is cyclic under multiplication.

Definition 2.19. The order of an element a∈Ga \in G, denoted ∣a∣|a|, is the smallest positive integer nn such that an=ea^n = e. If no such nn exists, aa has infinite order.

Theorem 2.20. If aa has finite order nn, then:⟨a⟩={e,a,a2,…,an−1},\langle a \rangle = \{e, a, a^2, \ldots, a^{n-1}\},and these nn elements are distinct.

Proof:
By definition 2.19 𝑛 is the smallest positive integer nn such that an=ea^n = e.
Therefore,

  1. for all k∈Z,k<n,k \in \mathbb{Z},k<n, an+k=aka^{n+k}=a^k. By definition2.14 ⟨a⟩={an∣n∈Z} should equal to{e,a,a2,…,an−1},\langle a \rangle = \{a^n \mid n \in \mathbb{Z}\}\text{ should equal to} \{e, a, a^2, \ldots, a^{n-1}\},
  2. Suppose, for contradiction, there exists am=ap,where m is not euqal to p,m,p∈Z,m<p<na^m=a^p, \text{where m is not euqal to p}, m,p \in \mathbb{Z}, m<p<n. Then by multipling an−ma^{n-m} on both side we deduce e=an−m+p=ap−me=a^{n-m+p}=a^{p-m}, where 0<p−m<n0<p-m<n and ap−m=ea^{p-m}=e. It's contradict to that nn is the order of aa. Hence there n elements are distinct.
    Thus, we are done.

∎

Theorem 2.21. For any a∈Ga \in G, ∣a∣=∣⟨a⟩∣|a| = |\langle a \rangle|.

Proof:
By Theorem 2.20, If aa has finite order nn i.e. ∣a∣=n|a|=n, then:
⟨a⟩={e,a,a2,…,an−1}\langle a \rangle = \{e, a, a^2, \ldots, a^{n-1}\} consists n distinct elements.
Thus, For any a∈Ga \in G, ∣a∣=∣⟨a⟩∣|a| = |\langle a \rangle|.∎

Theorem 2.22. If ak=ea^k = e, then ∣a∣|a| divides kk.

Theorem 2.23 (Order of a Power). Let aa have order nn. Then for any integer kk:∣ak∣=ngcd⁡(n,k).|a^k| = \frac{n}{\gcd(n, k)}.

Proof:
Let k=pt,n=qt,t=gcd(n,k),gcd(p,q)=1k=pt,n=qt,t=gcd(n,k), gcd(p,q)=1.
Since by Theorem 2.21, for any a∈Ga \in G, ∣a∣=∣⟨a⟩∣|a| = |\langle a \rangle|, ∣ak∣=∣⟨ak⟩∣|a^k| = |\langle a^k \rangle|.
We now consider ⟨ak⟩={apt,a2pt,…,aqpt… }\langle a^k \rangle=\{ a^{pt}, a^{2pt},\dots,a^{qpt}\dots \}
Since gcd(p,q)=1gcd(p,q)=1, the smallest positive integer h such that (ak)h=e(a^k)^h=e is qq.
Therefore, ∣ak∣=∣⟨ak⟩∣=q=ngcd⁡(n,k).|a^k| = |\langle a^k \rangle|=q= \frac{n}{\gcd(n, k)}.
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. aka^k generates ⟨a⟩\langle a \rangle iff gcd⁡(n,k)=1\gcd(n, k) = 1.

Proof:
When gcd⁡(n,k)=1\gcd(n, k) = 1,
applying Theorem 2.23, ∣ak∣=ngcd⁡(n,k)=n=∣a∣|a^k| = \frac{n}{\gcd(n, k)}=n=|a|
By Theorem 2.21, ∣a∣=∣⟨a⟩∣=∣ak∣=∣⟨ak⟩∣|a| = |\langle a \rangle|=|a^k| = |\langle a^k \rangle|
Since by definition ak∈⟨a⟩a^k \in \langle a \rangle, ⟨ak⟩⊂⟨a⟩\langle a^k \rangle \subset\langle a \rangle and both of them have order n (have the same number of elements),
⟨a⟩=⟨ak⟩\langle a \rangle=\langle a^k \rangle.

When aka^k generates ⟨a⟩\langle a \rangle.
ngcd⁡(n,k)=∣ak∣=∣⟨a⟩∣=n\frac{n}{\gcd(n, k)}=|a^k| =|\langle a \rangle|= n
Therefore gcd(n,k)=1gcd(n,k)=1∎

Exercise 2.25. Find the order of each element in Z6\mathbb{Z}_6.

∣Z6∣=6|\mathbb{Z}_6|=6 and it is generated by 1.
The order of 1 is 6.
The order of 2, 121^2 here, is 6gcd⁡(6,2)=3\frac{6}{\gcd(6, 2)}=3
The order of 3, 131^3 here, similarly, is 22
The order of 4, 141^4 here, similarly is 33
The order of 5, 151^5 here, similarly is 66
The order of 0, 161^6 here, similarly is 1.

Exercise 2.26. Find the order of each element in S3S_3.

Exercise 2.27. Let aa have order 1212. Find the orders of a2,a3,a4,a5,a6a^2, a^3, a^4, a^5, a^6.
For a2a^2, order is 122=6\frac{12}{2}=6
For a3a^3, order is 123=4\frac{12}{3}=4
For a4a^4, order is 124=3\frac{12}{4}=3
For a5a^5, order is 121=12\frac{12}{1}=12
For a6a^6, order is 126=2\frac{12}{6}=2


Subgroups of Cyclic Groups#

Theorem 2.28. Every subgroup of a cyclic group is cyclic.

Proof:
Take a subgroup HH of a cyclic group G=⟨a⟩G=\langle a \rangle with order n.
The elements of HH must all have the form ak,k∈{0,1,2,…n−1}a^k, k\in \{ 0,1,2,\dots n-1 \} .
In non-trivial case, i.e. the subgroup is not {e}\{ e \}, which is cyclic, there must exist 1≤k0≤n−11\leq k_{0} \leq n-1 such that k0k_{0} is the smallest among all the kk.
Then HH must also contain a2k0,a3k0,…a∣a0k∣=ea^{2k_{0}},a^{3k_{0}},\dots a^{|a^k_{0}|}=e, where ∣a0k∣=ngcd(n,k0)|a^k_{0}|= \frac{n}{gcd(n,k_{0})}.
That is, ⟨ak0⟩⊂H\langle a_{k_{0}}\rangle \subset H.
Suppose there exists ata^t in HH where t is not a multiple of k0t \text{ is not a multiple of } k_{0}.
Suppose gcd(t,k0)=m≤k0gcd(t,k_{0})=m \leq k_{0}. By Bézout's lemma, there exists p,q∈Zp,q \in \mathbb{Z} such that pt+qk0=mpt+qk_{0}=m.
Therefore, similarly, there exists apt+qk0=m=ama^{pt+qk_{0}=m}=a^m . Since k0≤mk_{0} \leq m and m≤k0m \leq k_{0}, then m=k0m=k_{0}, which contradicts the supposition t is not a multiple of k0t \text{ is not a multiple of } k_{0}.
Hence, for all the aka^k in HH, k is the multiple of k0k \text{ is the multiple of } k_{0}, that is H⊂⟨ak0⟩H \subset \langle a^{k_{0}}\rangle.
Therefore, in conclusion, H=⟨ak0⟩H = \langle a^{k_{0}}\rangle.

When G=⟨a⟩G=\langle a \rangle is infinite.
Take a subgroup HH consisting of ak,k∈Za^k, k\in \mathbb{Z}, there must exist ak0a^{k_{0}} such that k0k_{0} is the smallest among all the kk. Then ⟨ak0⟩(which is also infinite)⊂H\langle a^{k_{0}}\rangle \text{(which is also infinite)} \subset H.
Similarly:
Suppose there exists ata^t in HH where t is not a multiple of k0t \text{ is not a multiple of } k_{0}.
Suppose gcd(t,k0)=m≤k0gcd(t,k_{0})=m \leq k_{0}. By Bézout's lemma, there exists p,q∈Zp,q \in \mathbb{Z} such that pt+qk0=mpt+qk_{0}=m.
Therefore, similarly, there exists apt+qk0=m=ama^{pt+qk_{0}=m}=a^m . Since k0≤mk_{0} \leq m and m≤k0m \leq k_{0}, then m=k0m=k_{0}, which contradicts the supposition t is not a multiple of k0t \text{ is not a multiple of } k_{0}.
Hence, for all the aka^k in HH, k is the multiple of k0k \text{ is the multiple of } k_{0}, that is H⊂⟨ak0⟩H \subset \langle a^{k_{0}}\rangle.
Therefore, H=⟨ak0⟩H= \langle a^{k_{0}}\rangle∎

Theorem 2.29. Let G=⟨a⟩G = \langle a \rangle be a cyclic group of order nn.

(a) For each divisor dd of nn, there is exactly one subgroup of order dd, namely ⟨an/d⟩\langle a^{n/d} \rangle.

Proof:
Suppose, for contradiction, that there exists another subgroup of order dd generated by ap,p<n,dp is not equal to na^p,p<n,dp \text{ is not equal to n}
⟨ap⟩={ap,…,adp}\langle a^p \rangle=\{a^p, \dots, a^{dp} \}, and adp=e=akn,k∈Z+,k is not equal to 1a^{dp}=e=a^{kn}, k\in \mathbb{Z_{+}},k \text{ is not equal to 1}.
dp=kn  ⟹  p=knddp=kn \implies p=k\frac{n}{d}.
Then ⟨ap⟩=⟨aknd⟩={aknd,…,adp}\langle a^p \rangle=\langle a^{k\frac{n}{d}}\rangle=\{a^{k\frac{n}{d}}, \dots, a^{dp} \}, which is a subgroup of ⟨an/d⟩\langle a^{n/d} \rangle.
Since both of them have order dd, ⟨ap⟩=⟨an/d⟩\langle a^p \rangle=\langle a^{n/d} \rangle.
Therefore, the supposition fails: there only exists exactly one subgroup of order dd, namely ⟨an/d⟩\langle a^{n/d} \rangle.

(b) The subgroups of GG are precisely ⟨ad⟩\langle a^d \rangle for each divisor dd of nn.∎

Proof:
On the one hand, by (a), we deduce that all ⟨ad⟩\langle a^d \rangle for each divisor dd of nn are subgroups of G.G.

On the other hand, suppose, for contradiction, there exists another subgroup(cylic, by theorem2.28) ⟨am⟩\langle a^m \rangle, where mm is not a divisor of nn, gcd(m,n)=tgcd(m,n)=t, and tt does not equal to mm or m would be a divisor of nn.
By Bezout's lemma, there must exists p,q∈Zp,q \in \mathbb{Z}, pm+qn=tpm+qn=t.
Then in ⟨am⟩\langle a^m \rangle, there must exists apm+qn=apm⋅e=apm=ata^{pm+qn}=a^{pm}\cdot e=a^{pm}=a^t, where t≤mt \leq m.
However, since the subgroup is generated by mm, t≥mt\geq m.
Therefore, t=mt=m, which contradicts to the supposition.
Thus, there does not exist another subgroup(cylic, by theorem2.28) ⟨am⟩\langle a^m \rangle, where mm is not a divisor of nn.

So the subgroups of GG are precisely ⟨ad⟩\langle a^d \rangle for each divisor dd of nn.

(c) If H=⟨ak⟩H = \langle a^k \rangle, then ∣H∣=n/gcd⁡(n,k)|H| = n / \gcd(n, k).∎

Theorem 2.30. Let G=⟨a⟩G = \langle a \rangle be infinite cyclic. Then every nontrivial subgroup is infinite cyclic, and the subgroups are precisely ⟨ak⟩\langle a^k \rangle for k∈Z+k \in \mathbb{Z}^+.

Proof:
Apparently all the ⟨ak⟩\langle a^k \rangle for k∈Z+k \in \mathbb{Z}^+ are infinite subgroups of G=⟨a⟩G = \langle a \rangle.
By theorem2.28, all of the subgroup of a cyclic group are cyclic.
Thus, they must all have the form ⟨ak⟩\langle a^k \rangle for k∈Z+k \in \mathbb{Z}^+.
Therefore, the subgroups are precisely ⟨ak⟩\langle a^k \rangle for k∈Z+k \in \mathbb{Z}^+.∎

Theorem 2.31 (Subgroup Lattice of Cyclic Groups). For a cyclic group G=⟨a⟩G = \langle a \rangle of order nn, the subgroups form a lattice under inclusion, ordered by divisibility: ⟨ad⟩⊆⟨ae⟩\langle a^d \rangle \subseteq \langle a^e \rangle iff e∣de \mid d.

Proof:
If e∣de \mid d, d=ke,k∈Zd=ke,k\in \mathbb{Z}, ⟨ad⟩=⟨ake⟩⊆⟨ae⟩\langle a^d \rangle=\langle a^{ke} \rangle \subseteq \langle a^e \rangle.
If ⟨ad⟩⊆⟨ae⟩\langle a^d \rangle \subseteq \langle a^e \rangle, then ad∈⟨ae⟩  ⟹  ad=ake,k∈{1,2,…e−1}a^d\in \langle a^e \rangle \implies a^d=a^{ke},k\in \{ 1,2,\dots e-1 \}. Therefore, e∣de \mid d.

Thus, ⟨ad⟩⊆⟨ae⟩\langle a^d \rangle \subseteq \langle a^e \rangle iff e∣de \mid d.∎

Exercise 2.32. Find all subgroups of Z12\mathbb{Z}_{12}.

generators: 1 2 3 4 6 12

Exercise 2.33. Find all subgroups of Z18\mathbb{Z}_{18}.

generators: 1 2 3 6 9 18

Exercise 2.34. How many subgroups does Z24\mathbb{Z}_{24} have? List them.

generators: 1 2 3 4 6 8 12

Exercise 2.35. Let G=⟨a⟩G = \langle a \rangle be cyclic of order nn. Prove that aka^k generates GG if and only if gcd⁡(k,n)=1\gcd(k, n) = 1.


Generators of Cyclic Groups#

Definition 2.36. The Euler phi-function φ(n)\varphi(n) is the number of integers kk with 1≤k≤n1 \leq k \leq n such that gcd⁡(k,n)=1\gcd(k, n) = 1.

Theorem 2.37. A cyclic group G=⟨a⟩G=\langle a\rangle of order nn has exactly φ(n)\varphi(n) generators.

By theorem 2.23, ∣ak∣=ngcd⁡(n,k)|a^k| = \frac{n}{\gcd(n, k)}. The generator of GG should have order nn. Then that requires gcd(n,k)gcd(n,k) to be 11.
By definition 2.36, φ(n)\varphi(n) is the number of all integers kk with 1≤k≤n1 \leq k \leq n such that gcd⁡(k,n)=1\gcd(k, n) = 1, and thus the number of generators of GG.

Example 2.38. Z12\mathbb{Z}_{12} has φ(12)=4\varphi(12) = 4 generators. They are 1,5,7,111, 5, 7, 11.

Exercise 2.39.
(a) Find all generators of Z20\mathbb{Z}_{20}.
1, 3, 5,7,9,11,13,17,19

(b) Find all generators of Z15\mathbb{Z}_{15}.
1,2,4,7,8,11,13,14

(c) How many generators does Z100\mathbb{Z}_{100} have?
25

(d) For which nn does Zn\mathbb{Z}_n have exactly 2 generators? Exactly 4 generators?
3, 4, 6; 5, 8, 10, 12

Exercise 2.40. Prove that if GG is cyclic of order nn, then GG has exactly one subgroup of each order dividing nn.

Exercise 2.41. Let GG be a cyclic group of order nn. How many elements of order dd does GG have for each d∣nd \mid n? Express your answer in terms of φ\varphi.


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: ∥ak∥=n/gcd⁡(n,k)\|a^k\| = n / \gcd(n, k)
  • Classification of subgroups of cyclic groups
  • Subgroup lattice of cyclic groups
  • Euler's phi-function and counting generators
  • The Fundamental Theorem of Cyclic Groups