Definition 2.2.1

A non-empty subset $H$ of a group $G$ is called a subgroup if $H$ is itself a group with the group operation inherited from $G$. We write $H \leq G$ to indicate that $H$ is a subgroup of $G$.

The necessary conditions for a subset (H) of (G) to be a subgroup of (G) are:

Closed under multiplication. That is, for all elements $h_1$ and $h_2$ of $H$, the products $h_1h_2$ is also an element of $H$
Closed under inverses. For all $h \in H$, the inverse $h^{-1}$ is an element of $H$

By $(2)$ we know for any $h \in H$, $h^{-1} \in H$ and by (1), we know that $hh^{-1}=e \in H$. So the identity element is in $H$. Associativity is inherited from $GG$. From this we see that these two conditions are sufficient for $H$ to be a subgroup of $G$. Sometimes, it is easier to prove that a set is a subgroup rather than proving that it is a group since we only need to check these two conditions.

Proposition 2.2.8 (Uniqueness of the identity)

Let $G$ be a group and let $H_1, H_2,...,H_n$ be subgroups of $G$. Then $H_1 \cap H_2 \ \cap ... \cap \ H_n $ is a subgroup of $G$. More generally, if $\{H_{\alpha}\}$ is any collection of subgroups, then $\cap_{\alpha}$ is a subgroup.

Proof
TODO

Generated Subgroups

For any subset $S \subseteq G$, the subgroup generated by $S$ is the smallest subgroup in $G$ that contains $S$ and is denoted $\langle S \rangle$.
If $S$ contains a single element, $S = \{a\}$, then the subgroup generated by $S$ is denoted by $\langle a \rangle$.
If $G = \langle S \rangle$, then $G$ is generated by $S$ or $S$ generates $G$

One way to describe $\langle S \rangle$ is that it contains all the possible products $g_1g_2...g_n$ where $g_i \in S$ or $g_i^{-1} \in S$.
Another way to describe $\langle S \rangle$ is that it is the intersection of the family of all subgroups of $G$ that contain $S$. This family can’t be empty since $G$ is a group.

Cyclic Groups and Cyclic Subgroups

Proposition 2.2.9

Let $a$ be an element of a group $G$. The subgroup $\langle a \rangle$ generated by $a$ is $\{a^k \ : \ k \in \mathbf{Z}\}$.

Proof
Let $H = \{a^k \ : \ k \in \mathbf{Z}\}$. We will show that $\langle a \rangle = H$ as follows:

$\langle a \rangle \subseteq H$: We know that $G$ is a group and $H$ is subset of $G$. We claim that it is a subgroup of $G$. It is closed under multiplication because for any $a^k$ and $a^l$ in $H$, $a^{k+l} \in H$. It is closed under inverses because for any $a^k \in H$, $(a^{k})^-1 = a^{-k} \in H$. Furthermore, $H$ contains $a$ and since $H$ is a subgroup, then $H$ contains all the powers of $a$. Therefore, $\langle a \rangle \subseteq H$.

$H \subseteq \langle a \rangle$: We showed that $H = \{a^k \ : \ k \in \mathbf{Z}\}$ is a subgroup above. It is closed under multiplication and so it contains all powers of $a$. Therefore, $H \subseteq \langle a \rangle$. $\ \blacksquare$

Definition 2.2.10

Let $a$ be an element of a group $G$. The set $\langle a \rangle = \{a^k \ : \ k \in \mathbf{Z}\}$ of powers of $a$ is called the cyclic subgroup generated by $a$. If there is an element $a \in G$ such that $\langle a \rangle = G$, we say that $G$ is a cyclic group. We say that $a$ is a generator of the cyclic group

Examples

Suppose $G = \mathbf{Z}$ with the addition operator. For any element $d \in \mathbf{Z}$, the set of powers of $d$ is the set of all multiples of $d$ since the group operation is addition. So $d+d+d+d+d$ is the fifth power for example. We see here that $\langle d \rangle = d \mathbf{Z} = \{nd \ : \ n \in \mathbf{Z}\}$ is a cyclic subgroup of $\mathbf{Z}$. In fact, $\mathbf{Z}$ itself is cyclic.

The Order of a Cyclic Subgroup

A cyclic subgroup could be infinite or finite. When the powers of $a$ are all distinct, it’s infinite. Otherwise, it is not. The following definition formalizes this.

Definition 2.2.16

The order of the cyclic subgroup generated by $a$ is called the order of $a$. We denote the order of $a$ by $o(a)$.

When the order of $a$ is finite, then two powers of $a$ will coincide at some point. Suppose that $k < l$, and $a^k = a^l$, then $a^{l-k} = e$. This implies that some positive integer of $a$ is the identity element. Let $n$ be the least positive integer such that $a^n = e$. This means that $e, a, a^2,...a^{n-1}$ are all distinct (Why? TODO). Write $k = mn + r$. Therefore,

$$ \begin{align*} a^{k} &= a^{mn+r} \\ &= a^{mn}a^r \\ &= e^{m}a^r \\ &= a^r \end{align*} $$

This means that $a^k = a^l$ if and only if $k$ and $l$ have the same remainder upon division of $n$, that is $k \equiv l \mod n$. This leads to the following proposition

Proposition 2.2.17

If the order of $a$ is finite, then it is the least positive integer $n$ such that $a^n = e$. Furthermore, $\langle a \rangle = \{a^k \ : \ 0 \leq k < o(a)\}$

Examples

What is the order of $[5]$ in $\phi(14)$? We know $[5]^2 = [11]$, $[5]^3 = [13]$ because $5^3 = 125 \mod 14 = 13$. $[5]^4 = [9]$, $[5]^5 = 3$ and finally $[5]^6 = [1]$. So the order of $[5]$ is 6.

The following result shows that in fact any two cyclic groups of the same order are isomorphic!

Proposition 2.2.20

Let $a$ be an element of a group $G$.

If $a$ has infinte order, then $\langle a \rangle$ is isomorphic to $\mathbf{Z}$
If $a$ has finite order, then $\langle a \rangle$ is isomorphic to the group $\mathbf{Z}_n$

Proof
For $(a)$, we want to show this by finding an example of a isomorphism. So define the map $\varphi \ : \ \mathbf{Z} \rightarrow \langle a \rangle$ by $\varphi(k) = a^k$. To show that this map is an isomorphism, we need to show that it is a bijection and also that for any two elements $a, b \in \mathbf{Z}$, $\varphi(ab) = \varphi(a)\varphi(b)$ (Definition 2.1.13).

To show that it is a bijection, observe that this map is surjective or onto by the definition of $\langle a \rangle$. (Recall that that $\langle a \rangle$ is of infinite order). It is also injective or 1-1 because all the elements of $\langle a \rangle$ (powers of $a$) are distinct. Furthermore, see that $\varphi(k + l) = a^{k+l} = a^ka^k$. So $\varphi$ is an isomorphism.

Similarly for $(b)$, we want to define an isomorphism. Note here that both $\mathbf{Z}_n$ and $\langle a \rangle$ have $n$ elements so define the map $\varphi \ : \ \mathbf{Z}_n \rightarrow \langle a \rangle$ by $\varphi([k]) = a^k$ where $0 \leq k \leq n-1$. In $\mathbf{Z}_n$, the addition of $[k]$ and $[l]$ is $[r]$ where $r$ is the remainder after dividing $k+l$ by $n$. While the multiplication in $\langle a \rangle$ is given by $a^ka^l = a^{k+l} = a^r$ where $r$ is also the remainder after dividing $k+l$ by $n$ as we saw earlier. Therefore $\varphi$ is an isomorphism.

Subgroups of Cyclic Groups

Every cyclic group is isomorphic to $\mathbf{Z}$ or $\mathbf{Z}_n$. Therefore, we’ll determine the subgroups of $\mathbf{Z}$ and $\mathbf{Z}_n$ to determine all the subgroups of cyclic groups.

Proposition 2.2.21

Let $H$ be a subgroup of $\mathbf{Z}$. Then either $H = \{0\}$ or there is a unique $d \in \mathbf{N}$ such that $H = \langle d \rangle = d\mathbf{Z}$
If $d \in \mathbf{N}$, then $d\mathbf{Z} \cong \mathbf{Z}$.
If $a, b \in \mathbf{N}$, then $a\mathbf{Z} \subseteq b\mathbf{Z}$ if and only if $b$ divides $a$.

As a reminder, $d\mathbf{Z} = \{ dn \ | \ n \in \mathbf{Z}\}$. It is the subgroup generated by $d$.

Proof
For $(c)$:
$\Rightarrow$: If $a\mathbf{Z} \subseteq b\mathbf{Z}$, then $a$ is a multiple of $b$. So $b$ divides $a$.
$\Leftarrow$: If $b$ divides $a$, then $a \in b\mathbf{Z}$ so $a\mathbf{Z} \subseteq b\mathbf{Z}$.

For $(a)$:
Suppose $H$ is a subgroup of $\mathbf{Z}$. Since $H$ is a subgroup, then it must contain at least one element. Suppose $H \neq \{0\}$, then $H$ contains a nonzero integer. For any integer $a \in H$, $H$ must also contain $-a$. Let $d$ be the smallest element in $H \cap \mathbf{N}$. We claim that $H = d\mathbf{Z}$. We want to show that $H \subseteq d\mathbf{Z}$ and $d\mathbf{Z} \subseteq H$.

Let $h \in H$. If $h = d$, then since $d \in H$, we have $\langle d \rangle = d\mathbf{Z} \subseteq H$. Otherwise, we can write $h = qd + r$ where $0 \leq r < d$. Now, we know that $h \in H$ and we know that $qd \ \in H$ since it’s a multiple of $d$, so $r = h + (- qd) = h - qd \in H$. But $d$ is the least positive element of $H$ and $r < d$. So we have $r = 0$. Therefore, $h = qd \in d\mathbf{Z}$.

So we know that there exists a $d \in \mathbf{N}$ such that $d\mathbf{Z} = H$. To see that it’s unique, suppose that $d' \in H$ and so $d'\mathbf{Z} = H$ but by (c), $d$ and $d'$ divide one another and since they’re both positive then $d = d'$ so $d$ is unique. $\ \blacksquare$.

Corollary 2.2.22

Every subgroup of $\mathbf{Z}$ other than ${0}$ is isomorphic to $\mathbf{Z}$.

Lemma 2.2.23

Let $n \geq 2$ and let $d$ be a positive divisor of $n$. The cyclic subgroup $\langle [d] \rangle$ generated by $[d]$ in $\mathbf{Z}_n$ has cardinality $|\langle [d] \rangle| = n/d$

Reminder: The subgroup generated by $d$ is $\{...,-2d,-d,0,d,2d,...\}$. The order of this subgroup is clearly infinite. The subgroup generated by $[d]$ is $\{[0], [d], [2d],...,(k-1)[d]\}$ where $(k+1)[d] = 0$. This group is clearly finite.

Example: Suppose $d=3$ and $n=9$. $Z_9 = \{0,1,2,3,4,5,6,7,8\}$ The cyclic subgroup in $Z_9$ generated by $\langle [3] \rangle$ is $\{k[3] \mod 9 \ | \ k \in \mathbf{Z}\} = \{[0],[3],[6]\}$. The size of $\langle [3] \rangle$ is $n/d = 9/3 = 3$.

Proof
We are given that $d$ is a positive divisor of $n$. Since we’re working with addition, this means that for some multiple of $d$, we will get back to $[0]$. So let $s$ be the least positive integer such that $s[d] = [0]$. In other words, $sd \equiv 0 \mod n$. This implies that $sd$ is a multiple of $n$ so $sd = kn$ for some integer $k$. But since we need the smallest $s$, then $s = \frac{n}{d}$. $\ \blacksquare$

Proposition 2.2.24

Let $H$ be a subgroup of $\mathbf{Z}_n$.

Either $H = \{0\}$, or there is a $d > 0$ such that $H = \langle [d] \rangle$
If $d$ is the smallest of positive integers $s$ such that $H$ = $\langle [s] \rangle$, then $d|H| = n$

Example $(a)$: Let $H$ be a subgroup of $Z_9$. $H$ must be generated by some $d > 0$. For example $Z_9$ is generated by $H = \langle [1] \rangle$. $\{[0],[3],[6]\}$ is generated by $\langle [3] \rangle$ and so on.

Example $(b)$: Take $s = 6$ such that $H = \langle [6] \rangle = \{[0], [6], [3]\}$. But $d = 3$ is the smallest generator for this subgroup because $\langle [3] \rangle = \{[0], [3], [6]\}$.

Proof
For (a), suppose $H \neq \{[0]\}$. Then $H$ contains at least one equivalent such that it is not $[0]$. Let $[d]$ be the smallest positive equivalent class. We claim that $H = \langle [d] \rangle$. So we need to show that $\langle [d] \rangle \subseteq H$ and $H \subseteq \langle [d] \rangle$.

$\langle [d] \rangle \subseteq H$: Since $[d] \in H$, then by definition, $\langle [d] \rangle \subseteq H$.

$H \subseteq \langle [d] \rangle$. Suppose $[h] \in H$, then by the division algorithm we can find $q$ and $r$ such that

$$ \begin{align*} [h] = [qd] + [r] \end{align*} $$

We know that $[h] \in H$ and $[qd] \in H$. Since $H$ is closed under addition, then

$$ \begin{align*} [r] = [h] - [qd] \end{align*} $$

is also in $H$. But since $[d]$ was the smallest positive equivalent class, then $[r]=0$ and we must have $[h] = [qd]$. Therefore, $[h] \in \langle [d] \rangle$. From this we see that $H = \langle [d] \rangle$ as we wanted to show.

For $(b)$, suppose that $H = \langle [s] \rangle$ and $d$ is the smallest of the positive integers $s$ so $[d]$ also generates $H$. By the division algorithm, write $n = qd + r$ where $0 \leq r < d$. Now

$$ \begin{align*} [n] &= [qd + r] \\ 0 &= [qd] + [r] \\ [r] &= -[qd] \\ &= -q[d] \\ \end{align*} $$

But this means that $[r] \in \langle [d] \rangle$

Corollary 2.2.25

For a natural number $n \geq 2$.

Any subgroup of $\mathbf{Z}_n$ is cyclic.
Any subgroup of $\mathbf{Z}_n$ has cardinality dividing $n$.

Corollary 2.2.26

For a natural number $n \geq 2$.

For any positive divisor $q$ of $n$, there is a unique subgroup of $\mathbf{Z}_n$ of cardinality $q$ namely $\langle [n/q] \rangle$.
For any two subgroups $H$ and $H'$ of $\mathbf{Z}_n$, we have $H \subseteq H' \Leftrightarrow |H|$ divides $|H'|$.

Example: Suppose $n = 8$ and $q = 2$. Then, there is a unique subgroup of cardinality $q = 2$, namely $H = \langle [n/q] \rangle = \langle [4] \rangle = \{[0],[4]\}$

Proof
For $(a)$, since $q$ is a positive divisor of $n$, then by Lemma 2.2.23, the cyclic subgroup $\langle [n/q] \rangle$ of $\mathbf{Z}_n$ has cardinality $n/(n/q) = q$. On the other hand, if $H$ is a subgroup of cardinality $q$, then by Proposition 2.2.24 $(b)$, …. TODO

Corollary 2.2.28

Let $b \in \mathbf{Z}, b \neq 0$

The cyclic subgroup $\langle [b] \rangle$ of $\mathbf{Z}_n$ generated by $[b]$ is equal to the cyclic subgroup generated by $[d]$, where $[d] = gcd(b,n)$.
The order of $[b]$ in $\mathbf{Z}_n$ is $\frac{n}{gcd(b,n)}$.
In particular, $[b] = \mathbf{Z}_n$ if and only if $b$ is relatively prime to $n$.

Example: TODO

Proof

Proposition 2.2.30

Every subgroup of a cyclic group is cyclic.

Example: TODO

Proof

Proposition 2.2.31

Let $a$ be an element of finite order $n$ in a group. Then $\langle a^k \rangle = \langle a \rangle $, if and only if $k$ is relatively prime to $n$. The number of generators of $\langle a \rangle$ is $\phi(n)$.

Example: TODO

Proof

Proposition 2.2.32

Let $a$ be an element of finite order $n$ in a group. For each positive integer $q$ dividing $n$, $\langle a \rangle$ has a unique subgroup of order $q$.

Example: TODO

Proof

[2.2] Subgroup and Cyclic Groups

Generated Subgroups

Cyclic Groups and Cyclic Subgroups

Examples

The Order of a Cyclic Subgroup

Examples

Subgroups of Cyclic Groups

References