## Section11.1Cyclic Groups and Orders of Elements

Given an element $a$ in a group $G\text{,}$ we can consider what happens when we multiply $a$ by itself (or if we are writing the group additively, add $a$ to itself). Depending on what group we are in, if we continue to multiply the result by $a\text{,}$ we might eventually find ourselves back at the identity. How long does this take? That is precisely the question that the order of a group element addresses. We will see that this relatively simple idea has far reaching consequences.

### Worksheet11.1.1Powers mod Powers

Main Question: What is the remainder when you divide $a^p$ by $p\text{?}$

###### 1.

Compute $a^p$ and its remainder when divided by $p\text{,}$ for various values of $a$ and $p\text{.}$ Everyone should do at least 5, and then share with the group. As a group, discuss any patterns you see and form a conjecture.

Find the remainders when you perform the following divisions. Try different values of $a\text{.}$ You should first guess what the value is based on your conjecture and then verify (or refute) your guess.

###### 2.

$a^6$ divided by 10?

###### 3.

$a^9$ divided by 15?

###### 4.

$a^{13}$ divided by 21?

###### 5.

$a^{2321}$ divided by $2419\text{?}$

Discuss in your groups: how might we think about the main question here in terms of group theory? What would we need to prove (about groups)?

### Worksheet11.1.2Activity: Orders of Permutations

The order of an element $g$ in a group $G$ is the least natural number $n$ such that $g^n = e\text{,}$ if such a number exists (otherwise we say the order of $g$ is infinite).

###### 1.

Find the orders of the elements of $S_5$ below:

\begin{equation*} \alpha = (12) \hspace{1in}\alpha = (123) \hspace{1in} \alpha = (1234) \hspace{1in} \alpha = (12345) \end{equation*}
Solution

The orders are 2, 3, 4, and 5, respectively.

###### 2.

Find an element of $S_5$ that has an order different from those found above.

Solution

We will need an element that is not just a cycle, since the longest cycle is of length 5. So how about $(12)(345)\text{.}$ This will have order 6.

###### 3.

Let $\alpha$ be an element of $S_5\text{.}$ What is $\alpha^{120}\text{?}$

Solution

No matter what element we pick, $\alpha^{120}$ will always be $(1)\text{.}$ This will work in general, but you can also see this by considering the orders of elements, which must all divide the size of the group.

###### 4.

Is there an element in $S_5$ that has order $120\text{?}$

Solution

No there is not. If there were, this would say that $S_5$ was cyclic, and would thus be abelian, which we know is not the case. Alternatively, just look at how to write elements as disjoint cycles.

###### 5.

What is the largest order of any element in $S_5\text{?}$

Solution

The largest order will be 6, for elements that are the disjoint product of a 2-cycle and 3-cycle.

### Subsection11.1.3Cyclic Subgroups

Often a subgroup will depend entirely on a single element of the group; that is, knowing that particular element will allow us to compute any other element in the subgroup.

###### Example11.1.

Suppose that we consider $3 \in {\mathbb Z}$ and look at all multiples (both positive and negative) of $3\text{.}$ As a set, this is

\begin{equation*} 3 {\mathbb Z} = \{ \ldots, -3, 0, 3, 6, \ldots \}\text{.} \end{equation*}

It is easy to see that $3 {\mathbb Z}$ is a subgroup of the integers. This subgroup is completely determined by the element $3$ since we can obtain all of the other elements of the group by taking multiples of $3\text{.}$ Every element in the subgroup is “generated” by $3\text{.}$

###### Example11.2.

If $H = \{ 2^n : n \in {\mathbb Z} \}\text{,}$ then $H$ is a subgroup of the multiplicative group of nonzero rational numbers, ${\mathbb Q}^*\text{.}$ If $a = 2^m$ and $b = 2^n$ are in $H\text{,}$ then $ab^{-1} = 2^m 2^{-n} = 2^{m-n}$ is also in $H\text{.}$ Thus $H$ is a subgroup of ${\mathbb Q}^*$ determined by the element $2\text{.}$

###### Proof.

The identity is in $\langle a \rangle$ since $a^0 = e\text{.}$ If $g$ and $h$ are any two elements in $\langle a \rangle \text{,}$ then by the definition of $\langle a \rangle$ we can write $g = a^m$ and $h = a^n$ for some integers $m$ and $n\text{.}$ So $gh = a^m a^n = a^{m+n}$ is again in $\langle a \rangle \text{.}$ Finally, if $g = a^n$ in $\langle a \rangle \text{,}$ then the inverse $g^{-1} = a^{-n}$ is also in $\langle a \rangle \text{.}$ Clearly, any subgroup $H$ of $G$ containing $a$ must contain all the powers of $a$ by closure; hence, $H$ contains $\langle a \rangle \text{.}$ Therefore, $\langle a \rangle$ is the smallest subgroup of $G$ containing $a\text{.}$

###### Remark11.4.

If we are using the “+” notation, as in the case of the integers under addition, we write $\langle a \rangle = \{ na : n \in {\mathbb Z} \}\text{.}$

For $a \in G\text{,}$ we call $\langle a \rangle$ the cyclic subgroup generated by $a\text{.}$ If $G$ contains some element $a$ such that $G = \langle a \rangle \text{,}$ then $G$ is a cyclic group. In this case $a$ is a generator of $G\text{.}$ If $a$ is an element of a group $G\text{,}$ we define the order of $a$ to be the smallest positive integer $n$ such that $a^n= e\text{,}$ and we write $|a| = n\text{.}$ If there is no such integer $n\text{,}$ we say that the order of $a$ is infinite and write $|a| = \infty$ to denote the order of $a\text{.}$

###### Example11.5.

Notice that a cyclic group can have more than a single generator. Both $1$ and $5$ generate ${\mathbb Z}_6\text{;}$ hence, ${\mathbb Z}_6$ is a cyclic group. Not every element in a cyclic group is necessarily a generator of the group. The order of $2 \in {\mathbb Z}_6$ is $3\text{.}$ The cyclic subgroup generated by $2$ is $\langle 2 \rangle = \{ 0, 2, 4 \}\text{.}$

The groups ${\mathbb Z}$ and ${\mathbb Z}_n$ are cyclic groups. The elements $1$ and $-1$ are generators for ${\mathbb Z}\text{.}$ We can certainly generate ${\mathbb Z}_n$ with 1 although there may be other generators of ${\mathbb Z}_n\text{,}$ as in the case of ${\mathbb Z}_6\text{.}$

###### Example11.6.

The group of units, $U(9)\text{,}$ in ${\mathbb Z}_9$ is a cyclic group. As a set, $U(9)$ is $\{ 1, 2, 4, 5, 7, 8 \}\text{.}$ The element 2 is a generator for $U(9)$ since

\begin{align*} 2^1 & = 2 \qquad 2^2 = 4\\ 2^3 & = 8 \qquad 2^4 = 7\\ 2^5 & = 5 \qquad 2^6 = 1\text{.} \end{align*}
###### Example11.7.

Not every group is a cyclic group. Consider the symmetry group of an equilateral triangle $S_3\text{.}$ The multiplication table for this group is Figure 2.7. The subgroups of $S_3$ are shown in Figure 2.39. Notice that every subgroup is cyclic; however, no single element generates the entire group.

###### Proof.

Let $G$ be a cyclic group and $a \in G$ be a generator for $G\text{.}$ If $g$ and $h$ are in $G\text{,}$ then they can be written as powers of $a\text{,}$ say $g = a^r$ and $h = a^s\text{.}$ Since

\begin{equation*} g h = a^r a^s = a^{r+s} = a^{s+r} = a^s a^r = h g\text{,} \end{equation*}

$G$ is abelian.

### Subsection11.1.4Subgroups of Cyclic Groups

We can ask some interesting questions about cyclic subgroups of a group and subgroups of a cyclic group. If $G$ is a group, which subgroups of $G$ are cyclic? If $G$ is a cyclic group, what type of subgroups does $G$ possess?

###### Proof.

The main tools used in this proof are the division algorithm and the Principle of Well-Ordering. Let $G$ be a cyclic group generated by $a$ and suppose that $H$ is a subgroup of $G\text{.}$ If $H = \{ e \}\text{,}$ then trivially $H$ is cyclic. Suppose that $H$ contains some other element $g$ distinct from the identity. Then $g$ can be written as $a^n$ for some integer $n\text{.}$ Since $H$ is a subgroup, $g^{-1} = a^{-n}$ must also be in $H\text{.}$ Since either $n$ or $-n$ is positive, we can assume that $H$ contains positive powers of $a$ and $n \gt 0\text{.}$ Let $m$ be the smallest natural number such that $a^m \in H\text{.}$ Such an $m$ exists by the Principle of Well-Ordering.

We claim that $h = a^m$ is a generator for $H\text{.}$ We must show that every $h' \in H$ can be written as a power of $h\text{.}$ Since $h' \in H$ and $H$ is a subgroup of $G\text{,}$ $h' = a^k$ for some integer $k\text{.}$ Using the division algorithm, we can find numbers $q$ and $r$ such that $k = mq +r$ where $0 \leq r \lt m\text{;}$ hence,

\begin{equation*} a^k = a^{mq +r} = (a^m)^q a^r = h^q a^r\text{.} \end{equation*}

So $a^r = a^k h^{-q}\text{.}$ Since $a^k$ and $h^{-q}$ are in $H\text{,}$ $a^r$ must also be in $H\text{.}$ However, $m$ was the smallest positive number such that $a^m$ was in $H\text{;}$ consequently, $r=0$ and so $k=mq\text{.}$ Therefore,

\begin{equation*} h' = a^k = a^{mq} = h^q \end{equation*}

and $H$ is generated by $h\text{.}$

###### Proof.

First suppose that $a^k=e\text{.}$ By the division algorithm, $k = nq + r$ where $0 \leq r \lt n\text{;}$ hence,

\begin{equation*} e = a^k = a^{nq + r} = a^{nq} a^r = e a^r = a^r\text{.} \end{equation*}

Since the smallest positive integer $m$ such that $a^m = e$ is $n\text{,}$ $r= 0\text{.}$

Conversely, if $n$ divides $k\text{,}$ then $k=ns$ for some integer $s\text{.}$ Consequently,

\begin{equation*} a^k = a^{ns} = (a^n)^s = e^s = e\text{.} \end{equation*}
###### Proof.

We wish to find the smallest integer $m$ such that $e = b^m = a^{km}\text{.}$ By Proposition 2.43, this is the smallest integer $m$ such that $n$ divides $km$ or, equivalently, $n/d$ divides $m(k/d)\text{.}$ Since $d$ is the greatest common divisor of $n$ and $k\text{,}$ $n/d$ and $k/d$ are relatively prime. Hence, for $n/d$ to divide $m(k/d)$ it must divide $m\text{.}$ The smallest such $m$ is $n/d\text{.}$

###### Example11.15.

Let us examine the group ${\mathbb Z}_{16}\text{.}$ The numbers $1\text{,}$ $3\text{,}$ $5\text{,}$ $7\text{,}$ $9\text{,}$ $11\text{,}$ $13\text{,}$ and $15$ are the elements of ${\mathbb Z}_{16}$ that are relatively prime to $16\text{.}$ Each of these elements generates ${\mathbb Z}_{16}\text{.}$ For example,

\begin{align*} 1 \cdot 9 & = 9 & 2 \cdot 9 & = 2 & 3 \cdot 9 & = 11\\ 4 \cdot 9 & = 4 & 5 \cdot 9 & = 13 & 6 \cdot 9 & = 6\\ 7 \cdot 9 & = 15 & 8 \cdot 9 & = 8 & 9 \cdot 9 & = 1\\ 10 \cdot 9 & = 10 & 11 \cdot 9 & = 3 & 12 \cdot 9 & = 12\\ 13 \cdot 9 & = 5 & 14 \cdot 9 & = 14 & 15 \cdot 9 & = 7\text{.} \end{align*}

### Exercises11.1.5Collected Homework

###### 1.

Prove the following basic facts about orders of elements. None of these are particularly difficult, so you should focus on writing nice, clean proofs. In each of the following, $a$ is an element of a group $G\text{.}$

###### (a)

If $\ord(a) = n\text{,}$ then for any $r \lt n\text{,}$ the inverse of $a^r$ is $a^{n-r}\text{.}$ That is, $(a^r)\inv = a^{n-r}\text{.}$

###### (b)

The order of $a\inv$ is the same as the order of $a\text{.}$

Hint

Careful: it is not enough to say that $(a\inv)^n = e$ (where $\ord(a) = n$). That is only half of it, since you must also show that no smaller power of $a\inv$ is the identity.

###### (c)

If $a^k = e$ where $k$ is odd, then the order of $a$ is odd.

###### (d)

If $a \ne e$ and $a^p = e$ where $p$ is prime, then $\ord(a) = p\text{.}$