Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{\nmid} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\transpose}{\text{t}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \setcounter{chapter}{-1}\)

Section3.3Orders and Subgroups

As we'll come to appreciate, one of the most important characterizing properties of any finite group is the total number of elements in its set of elements. This number is called the order of the group. Somewhat confusingly, the word "order" is also used to describe a related property of elements in a group as well, so pay close attention to the word usage in the following section to keep your head straight!

Subsection3.3.1Order

Definition3.1Order of a Group

Let \(G\) be a group. The number of elements in \(G\) is called the order of the group \(G\), and is denoted by \(\bigl| G \bigr|\text{.}\)

If \(G\) is an infinite group we denote \(\bigl| G \bigr| = \infty\text{.}\)

Example3.2

The group \(\mathbb{Z}\) of integers has infinite order: \(\bigl| \mathbb{Z} \bigr| = \infty\text{.}\) However, the additive group \(\mathbb{Z}_n\) of integers modulo \(n\) has order \(n\text{,}\) i.e., \(\bigl| \mathbb{Z}_n \bigr| = n\text{.}\)

The dihedral group \(D_n\) of the regular \(n\)-gon (5.4) has order \(\bigl| D_n \bigr| = 2n\text{.}\) (Indeed, some mathematicians prefer the notation \(D_{2n}\) for the group of symmetries of a regular \(n\)-gon, calling it instead the "dihedral group of order \(2n\text{.}\)")

Example3.3Order of Multiplicative Groups

The multiplicative group of integers modulo \(n\text{,}\) denoted \(U(n)\text{,}\) has an interesting pattern for how its order varies with \(n\text{.}\) Looking at the first few examples, the pattern is not immediately apparent:

\begin{align*} U(2) \amp = \{ 1 \} \amp |U(2)| \amp = 1 \\ U(3) \amp = \{ 1, 2 \} \amp |U(3)| \amp = 2\\ U(4) \amp = \{ 1, 3 \} \amp |U(4)| \amp = 2\\ U(5) \amp = \{ 1, 2, 3, 4 \} \amp |U(5)| \amp = 4\\ U(6) \amp = \{ 1, 5 \} \amp |U(6)| \amp = 2\\ U(7) \amp = \{ 1, 2, 3, 4, 5, 6 \} \amp |U(7)| \amp = 6 \end{align*}

Because the elements of \(U(n)\) must have (multiplicative!) inverses, for each \(k \in U(n)\) there must exist a \(p \in U(n)\) such that \(pk \equiv 1\) (mod \(n\)). In other words, there must exist integers \(p,q\) such that

\begin{gather} pk + qn = 1.\tag{3.1} \end{gather}

According to elementary number theory's division algorithm (Section 7), this is possible exactly when \(k\) and \(n\) are relatively prime, i.e., when \({\rm gcd}(k,n) = 1\text{.}\)

Evidently, then, the elements of \(U(n)\) are exactly those \(k\) which are relatively prime to \(n\), and the order of \(U(n)\) is the number of residues modulo \(n\) which are relatively prime to \(n\text{:}\)

\begin{equation*} \bigl| U(n) \bigr| = \# \left\{ k \colon 0\leq k \lt n \text{ and } {\rm gcd}(k,n)=1 \right\} = \phi(n) \end{equation*}

where \(\phi\) is the function defined below.

Definition3.4Euler phi-function

Let \(n\) be a positive integer. The Euler phi-function (or "totient") of \(n\) is the number of residues modulo \(n\) that are relatively prime to \(n\text{,}\) and is denoted \(\phi(n)\text{.}\)

Remark3.5

If \(p\) is a prime number, it is a short matter to explain why \(\phi(p) = p-1\text{.}\)

The patterns apparent in \(\phi(n)\) for composite numbers \(n\) are more intricate to explain; for instance, if \(p\) is a prime and \(k \geq 1\text{,}\) then

\begin{equation*} \phi\bigl( p^k \bigr) = p^{k-1}(p-1). \end{equation*}

Furthermore, if \(m,n\) are relatively prime to one another, then

\begin{equation*} \phi\bigl( mn \bigr) = \phi(m) \phi(n). \end{equation*}

Combined with the fundamental theorem of arithmetic (Theorem 7.45), these two facts are enough (why?) to determine the value of \(\phi(n)\) for any integer \(n\text{.}\)

We will see the Euler phi-function again in Section 7.5; it also plays a central role in the study of number theory.

The word "order" is not only attached to groups to describe how many elements they have. It is also attached to elements to describe a related property. For this reason, as you're learning the terminology, you may want to be verbose and say things like:

  • "The order of the group \(\mathbb{Z}_n\) is..." and
  • "The order of the element \(1 \in \mathbb{Z}_n\) is..."
Definition3.6Order of an element

Let \(G\) be a group, and \(x\in G\) be an element. The order of the element \(x\) in \(G\) is the smallest positive integer \(k\) for which \(x^k = e\) is the identity element. We denote the order of \(x\) by \(\bigl| x \bigr|\text{.}\)

If no such integer exists, we say that \(x\) has infinite order and write \(\bigl| x \bigr| = \infty\text{.}\)

In other words, the order of an element \(x\) in \(G\) is an answer to the question "how many times must we 'multiply' \(x\) by itself before it becomes the identity element?"

Example3.7

In the additive group \(\mathbb{Z}_7\text{,}\) the order of the element \(5\) is seven, since (careful with notation!)

\begin{align*} 5^1 \amp = 5\\ 5^2 = 5+5 \amp = 3\\ 5^3 = 5+5+5 \amp = 1\\ 5^4 = 5+5+5+5 \amp = 6\\ 5^5 = 5+5+5+5+5 \amp = 4\\ 5^6 = 5+5+5+5+5+5 \amp = 2\\ 5^7 = 5+5+5+5+5+5+5 \amp = 0 \amp \text{(the identity)} \end{align*}

See if you can explain why every element \(x \neq 0\) in \(\mathbb{Z}_7\) also has \(|x| = 7\text{.}\)

In the multiplicative group \(U(10)\text{,}\) the order of the element \(3\) is four, since

\begin{align*} 3^1 \amp = 3\\ 3^2 = 3\cdot 3 \amp = 9\\ 3^3 = 3\cdot 3 \cdot 3 \amp = 7\\ 3^4 = 3\cdot 3 \cdot 3 \cdot 3 \amp = 1\amp \text{(the identity)} \end{align*}

(Note that the previous two examples look very different because of the role of the operation -- addition versus multiplication -- in defining what "powers" of an element really mean, and what the identity in each group means.)

In the dihedral group \(D_6\) of the regular hexagon, the order of the 60-degree rotation \(R_{60}\) is six: it takes six successive rotations by \(60^\circ\) before the hexagon returns to its original position.

Similarly, in the dihedral group \(D_6\) of the regular hexagon, the order of a reflection \(T\) is two: reflections in geometry are characterized by being their own inverses (any reflection, performed twice, is the identity). That is, \(T^2 = e\text{.}\)

In the additive group of integers \(\mathbb{Z}\text{,}\) almost every element has infinite order. For instance, \(|4| = \infty\) since no "power" of 4 in this group will ever become the additive identity 0:

\begin{align*} 4^1 \amp = 4 \\ 4^2 = 4+4 \amp = 8\\ 4^3 = 4+4+4 \amp = 12\\ 4^4 = 4+4+4+4 \amp = 16\\ \vdots \amp \vdots \end{align*}

(See if you can use well-ordering principles of the integers to prove this observation!) The lone exception to this is, of course, the identity element \(0 \in \mathbb{Z}\) itself, which like all identity elements has order 1.

Note here that the order of an element is always a positive integer since the zero-th power of any element is conventionally defined to be the identity (\(x^0 = e\) for any element \(x\) in any group \(G\)).

While the two uses of the word "order" can confuse at first, the overlap is deliberate: there is an important relationship between the two notions, as this proposition demonstrates.

Proof

(Proof by contradiction.) Suppose that \(|G| = n\) but \(|x| = q \gt n\text{.}\)

Case 1: If \(x = e\) is the identity element then we are done, since in this case \(|x| = 1 \leq n\text{.}\)

Case 2: If \(x \neq e\) then we will consider the set of all powers of the element \(x\) from the \(0\)th, which is the identity, through the \((q-1)\)st:

\begin{gather} S = \bigl\{ x^0=e, x, x^2, x^3, \ldots, x^{q-2}, x^{q-1} \bigr\} \subset G.\tag{3.2} \end{gather}

How many elements are actually in the set \(S\text{?}\) Could there be any duplicate elements in this list?

Claim: all elements listed in (3.2) are distinct (there are no duplicates).

(Proof by contrapositive.) Suppose there is a pair of distinct elements of \(S\) listed in (3.2) that are equal, i.e. that there are integers \(0 \leq k \lt \ell \leq q-1\) such that

\begin{equation*} x^k = x^{\ell}. \end{equation*}

If this were true, then multiplying both sides of this equation by \(x^{-\ell}\) would reveal

\begin{gather} x^{k-\ell} = e.\tag{3.3} \end{gather}

However, since both \(k\) and \(\ell\) are between \(0\) and \(q-1\) we must have \(k-\ell \leq q-1\text{.}\)

But then (3.3) would mean there exists an integer \((k-\ell)\text{,}\) which is less than \(q\), whose power of \(x\) is equal to the identity. This contradicts the assumption that \(q\) is the order of the element \(x\text{.}\)

Thus the list of elements of \(S\) in (3.2) has no duplicates.

Hence the set \(S\) has \(q\) distinct elements. But this is impossible, since \(S\) is a subset of \(G\) and \(G\) has only \(n\) elements with \(n \lt q\text{.}\) So since a subset cannot have more elements than its parent set, we have a contradiction, establishing the proof.

The key idea of the proof of Proposition 3.8 was the construction of the set \(S\) of all powers of the element \(x\text{:}\) because it had to be a subset of \(G\text{,}\) it had to have no more elements than \(G\) has. In fact, more is true about the set \(S\text{.}\) The elements which comprise \(S\) are themselves closed under the operation of the group \(G\text{,}\) the identity element can be found in \(S\text{,}\) and every element of \(S\) has an inverse that resides in \(S\) (why?). So \(S\) can be thought of as itself a group: a smaller group living within the bigger group \(G\text{,}\) which inherits \(G\)'s operation. We call such groups-within-groups subgroups, and will study those next.

Subsection3.3.2Subgroups: Definitions and Examples

Sometimes we wish to investigate smaller groups sitting inside a larger group. The set of even integers \(2{\mathbb Z} = \{\ldots, -2, 0, 2, 4, \ldots \}\) is a group under the operation of addition. This smaller group sits naturally inside of the group of integers under addition. We define a subgroup \(H\) of a group \(G\) to be a subset \(H\) of \(G\) such that when the group operation of \(G\) is restricted to \(H\text{,}\) \(H\) is a group in its own right. Observe that every group \(G\) with at least two elements will always have at least two subgroups, the subgroup consisting of the identity element alone and the entire group itself. The subgroup \(H = \{ e \}\) of a group \(G\) is called the trivial subgroup. A subgroup that is a proper subset of \(G\) is called a proper subgroup. In many of the examples that we have investigated up to this point, there exist other subgroups besides the trivial and improper subgroups.

Example3.9

Consider the set of nonzero real numbers, \({\mathbb R}^*\text{,}\) with the group operation of multiplication. The identity of this group is \(1\) and the inverse of any element \(a \in {\mathbb R}^*\) is just \(1/a\text{.}\) We will show that

\begin{equation*} {\mathbb Q}^* = \{ p/q : p \, \text{and}\, q\, \text{are nonzero integers} \} \end{equation*}

is a subgroup of \({\mathbb R}^*\text{.}\) The identity of \({\mathbb R}^*\) is \(1\text{;}\) however, \(1 = 1/1\) is the quotient of two nonzero integers. Hence, the identity of \({\mathbb R}^*\) is in \({\mathbb Q}^*\text{.}\) Given two elements in \({\mathbb Q}^*\text{,}\) say \(p/q\) and \(r/s\text{,}\) their product \(pr/qs\) is also in \({\mathbb Q}^*\text{.}\) The inverse of any element \(p/q \in {\mathbb Q}^*\) is again in \({\mathbb Q}^*\) since \((p/q)^{-1} = q/p\text{.}\) Since multiplication in \({\mathbb R}^*\) is associative, multiplication in \({\mathbb Q}^*\) is associative.

Example3.10

Recall that \({\mathbb C}^{\ast}\) is the multiplicative group of nonzero complex numbers. Let \(H = \{ 1, -1, i, -i \}\text{.}\) Then \(H\) is a subgroup of \({\mathbb C}^{\ast}\text{.}\) It is quite easy to verify that \(H\) is a group under multiplication and that \(H \subset {\mathbb C}^{\ast}\text{.}\)

Example3.11

Let \(SL_2( {\mathbb R})\) be the subset of \(GL_2( {\mathbb R })\)consisting of matrices of determinant one; that is, a matrix

\begin{equation*} A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \end{equation*}

is in \(SL_2( {\mathbb R})\) exactly when \(ad - bc = 1\text{.}\) To show that \(SL_2( {\mathbb R})\) is a subgroup of the general linear group, we must show that it is a group under matrix multiplication. The \(2 \times 2\) identity matrix is in \(SL_2( {\mathbb R})\text{,}\) as is the inverse of the matrix \(A\text{:}\)

\begin{equation*} A^{-1} = \begin{pmatrix} d & -b \\ -c & a \end{pmatrix}. \end{equation*}

It remains to show that multiplication is closed; that is, that the product of two matrices of determinant one also has determinant one. We will leave this task as an exercise. The group \(SL_2({\mathbb R})\) is called the special linear group.

Example3.12

It is important to realize that a subset \(H\) of a group \(G\) can be a group without being a subgroup of \(G\text{.}\) For \(H\) to be a subgroup of \(G\) it must inherit \(G\)'s binary operation. The set of all \(2 \times 2\) matrices, \({\mathbb M}_2(\mathbb R)\text{,}\) forms a group under the operation of addition. The \(2 \times 2\) general linear group is a subset of \({\mathbb M}_2(\mathbb R)\) and is a group under matrix multiplication, but it is not a subgroup of \({\mathbb M}_2(\mathbb R)\text{.}\) If we add two invertible matrices, we do not necessarily obtain another invertible matrix. Observe that

\begin{equation*} \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} + \begin{pmatrix} -1 & 0 \\ 0 & -1 \end{pmatrix} = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}, \end{equation*}

but the zero matrix is not in \(GL_2( {\mathbb R })\text{.}\)

Example3.13

One way of telling whether or not two groups are the same is by examining their subgroups. Other than the trivial subgroup and the group itself, the group \({\mathbb Z}_4\) has a single subgroup consisting of the elements \(0\) and \(2\text{.}\) From the group \({\mathbb Z}_2\text{,}\) we can form another group of four elements as follows. As a set this group is \({\mathbb Z}_2 \times {\mathbb Z}_2\text{.}\) We perform the group operation coordinatewise; that is, \((a,b) + (c,d) = (a+c, b+d)\text{.}\) Table 3.14 is an addition table for \({\mathbb Z}_2 \times {\mathbb Z}_2\text{.}\) Since there are three nontrivial proper subgroups of \({\mathbb Z}_2 \times {\mathbb Z}_2\text{,}\) \(H_1 = \{ (0,0), (0,1) \}\text{,}\) \(H_2 = \{ (0,0), (1,0) \}\text{,}\) and \(H_3 = \{ (0,0), (1,1) \}\text{,}\) \({\mathbb Z}_4\) and \({\mathbb Z}_2 \times {\mathbb Z}_2\) must be different groups.

\begin{equation*} \begin{array}{c|cccc} + & (0,0) & (0,1) & (1,0) & (1,1) \\ \hline (0,0) & (0,0) & (0,1) & (1,0) & (1,1) \\ (0,1) & (0,1) & (0,0) & (1,1) & (1,0) \\ (1,0) & (1,0) & (1,1) & (0,0) & (0,1) \\ (1,1) & (1,1) & (1,0) & (0,1) & (0,0) \end{array} \end{equation*}
Table3.14Addition table for \({\mathbb Z}_2 \times {\mathbb Z}_2\)

Subsection3.3.3Some Subgroup Theorems

Let us examine some criteria for determining exactly when a subset of a group is a subgroup.

Proof

First suppose that \(H\) is a subgroup of \(G\text{.}\) We must show that the three conditions hold. Since \(H\) is a group, it must have an identity \(e_H\text{.}\) We must show that \(e_H = e\text{,}\) where \(e\) is the identity of \(G\text{.}\) We know that \(e_H e_H = e_H\) and that \(ee_H = e_H e = e_H\text{;}\) hence, \(ee_H = e_H e_H\text{.}\) By right-hand cancellation, \(e =e_H\text{.}\) The second condition holds since a subgroup \(H\) is a group. To prove the third condition, let \(h \in H\text{.}\) Since \(H\) is a group, there is an element \(h' \in H\) such that \(hh' = h'h = e\text{.}\) By the uniqueness of the inverse in \(G\text{,}\) \(h' = h^{-1}\text{.}\)

Conversely, if the three conditions hold, we must show that \(H\) is a group under the same operation as \(G\text{;}\) however, these conditions plus the associativity of the binary operation are exactly the axioms stated in the definition of a group.

Proof

First assume that \(H\) is a subgroup of \(G\text{.}\) We wish to show that \(gh^{-1} \in H\) whenever \(g\) and \(h\) are in \(H\text{.}\) Since \(h\) is in \(H\text{,}\) its inverse \(h^{-1}\) must also be in \(H\text{.}\) Because of the closure of the group operation, \(gh^{-1} \in H\text{.}\)

Conversely, suppose that \(H \subset G\) such that \(H \neq \emptyset\) and \(g h^{-1} \in H\) whenever \(g, h \in H\text{.}\) If \(g \in H\text{,}\) then \(gg^{-1} = e\) is in \(H\text{.}\) If \(g \in H\text{,}\) then \(eg^{-1} = g^{-1}\) is also in \(H\text{.}\) Now let \(h_1, h_2 \in H\text{.}\) We must show that their product is also in \(H\text{.}\) However, \(h_1(h_2^{-1})^{-1} = h_1 h_2 \in H\text{.}\) Hence, \(H\) is a subgroup of \(G\text{.}\)