Cyclic groups

Every integer is a sum of copies of 1 or of -1, and every nth root of unity is a power of one of them. Which groups are built from a single element in this way, and what can be said about all of their subgroups at once?

Where you are 6 in Groups

Why this exists

The smallest subgroup containing an element holds all its powers (Subgroups, Lemma 4). Some groups are nothing more than that: \mathbb{Z} and \mathbb{Z}_n are the multiples of 1, and \mu_n the powers of \omega_n. For such groups we can list every subgroup, read off the order of any element from one greatest common divisor, and see that up to renaming there is one of each size. They are the pieces from which finite abelian groups are built (Direct products and finite abelian groups).

Definition

Let G be a group and a \in G, with powers a^0 = e, a^n = a \cdots a (n factors) and a^{-n} = (a^{-1})^n for n \ge 1, as in Binary operations and the group axioms. The cyclic subgroup generated by a is

\langle a \rangle = \{a^k : k \in \mathbb{Z}\},

in additive notation \{ka : k \in \mathbb{Z}\}. A group G is cyclic if G = \langle a \rangle for some a \in G; such an a is a generator of G.

The order \operatorname{ord}(a) is the least positive integer n with a^n = e (additively, na = 0) if there is one; otherwise a has infinite order. Only e has order 1. Some texts, Judson and Beezer’s among them, write |a|; we keep bars for the size of a set and for absolute value.

So \mathbb{Z} = \langle 1 \rangle = \langle -1 \rangle; writing k for [k], \mathbb{Z}_n = \langle 1 \rangle; and the group \mu_n of nth roots of unity (Integers mod n, symmetries and matrices as groups, Exercise 12) is \langle \omega_n \rangle, as every nth root of unity is a power of \displaystyle \omega_n = \operatorname{cis}\frac{2\pi}{n} (Roots of a complex number and roots of unity).

Intuition

The powers of one element form a walk, each step multiplying by a once more. In \mu_{12} the walk by \omega^5 visits every point before closing up; the walk by \omega^8 closes after three steps. Theorem 8 predicts both: the walk by \omega^k has 12 / \gcd(12, k) points.

0 1 2 3 4 5 6 7 8 9 10 11
\langle \omega^{5} \rangle
0 1 2 3 4 5 6 7 8 9 10 11
\langle \omega^{8} \rangle
Figure 1The twelfth roots of unity, point k standing for \omega^k with \displaystyle \omega = \operatorname{cis}\frac{2\pi}{12}. The powers of \omega^5 visit all twelve points; the powers of \omega^8 visit three.

A walk that never returns to e is a copy of the integer line; one that returns after n steps is a copy of the clock \mathbb{Z}_n. Theorem 5 says there are no other shapes.

Results

Throughout, G is a group with identity e and a \in G.

Lemma 1 (laws of exponents). For all integers m and n: a^m a^n = a^{m + n}, (a^m)^{-1} = a^{-m} and (a^m)^n = a^{mn}. Additively: ma + na = (m + n)a, -(ma) = (-m)a and n(ma) = (nm)a.

Theorem 2. \langle a \rangle \le G, and every subgroup of G that contains a contains \langle a \rangle.

Theorem 3. Every cyclic group is abelian.

Theorem 4 (order and powers). (a) If \operatorname{ord}(a) = n, then for all integers i, j, k: a^k = e if and only if n \mid k; a^i = a^j if and only if i \equiv j \pmod{n}; and \langle a \rangle = \{e, a, \dots, a^{n - 1}\} with these n powers distinct. (b) If a has infinite order, then a^i \ne a^j whenever i \ne j, so \langle a \rangle is infinite. In both cases |\langle a \rangle| = \operatorname{ord}(a).

Theorem 5 (the integers and the integers mod n). Let G = \langle a \rangle. (a) If G is infinite, then f : \mathbb{Z} \to G, f(k) = a^k, is a bijection with f(j + k) = f(j)f(k). (b) If |G| = n, then \operatorname{ord}(a) = n, and f : \mathbb{Z}_n \to G, f([k]) = a^k, is a well-defined bijection with f([j] + [k]) = f([j])f([k]).

So renaming each k as a^k turns the addition table of \mathbb{Z}, or of \mathbb{Z}_n, into the operation table of G: an infinite cyclic group has the same operation table as \mathbb{Z}, and one of order n the same as \mathbb{Z}_n. Such a renaming is an isomorphism.

Theorem 6. Every subgroup of a cyclic group is cyclic. If G = \langle a \rangle and \{e\} \ne H \le G, then H = \langle a^m \rangle, where m is the least positive integer with a^m \in H.

Corollary 7. The subgroups of \mathbb{Z} are exactly the sets n\mathbb{Z} with n \ge 0, and these are all different.

Theorem 8 (order of a power). If \operatorname{ord}(a) = n, k is an integer and d = \gcd(n, k), then \operatorname{ord}(a^k) = n/d and \langle a^k \rangle = \langle a^d \rangle.

Corollary 9 (generators). If \operatorname{ord}(a) = n, then \langle a^k \rangle = \langle a \rangle if and only if \gcd(k, n) = 1. So a cyclic group of order n has exactly \varphi(n) generators; those of \mathbb{Z}_n are the k with 0 \le k \le n - 1 and \gcd(k, n) = 1.

Theorem 10 (subgroups of a finite cyclic group). Let G = \langle a \rangle with |G| = n. (a) The order of every subgroup of G divides n. (b) For each positive divisor d of n, G has exactly one subgroup of order d, namely \langle a^{n/d} \rangle. (c) For positive divisors s and t of n, \langle a^s \rangle \subseteq \langle a^t \rangle if and only if t \mid s.

Why it is true

Proof of Lemma 1. First, a^n a = a^{n + 1} for every integer n: for n \ge 0 by definition (Theorem 7 of Binary operations and the group axioms drops brackets), and for n = -m with m \ge 1 because a^{-m}a = (a^{-1})^{m - 1}a^{-1}a = (a^{-1})^{m - 1} = a^{n + 1}. Multiplying on the right by a^{-1} gives also a^{n - 1} = a^n a^{-1}.

Fix m. The law a^m a^n = a^{m + n} holds for n = 0; if it holds for n, then a^m a^{n \pm 1} = a^m a^n a^{\pm 1} = a^{m + n}a^{\pm 1} = a^{m + n \pm 1}. By induction upward and downward it holds for all n. Then a^m a^{-m} = e gives (a^m)^{-1} = a^{-m}. Next, (a^m)^{n + 1} = (a^m)^n a^m = a^{mn}a^m = a^{mn + m} proves (a^m)^n = a^{mn} for n \ge 0 by induction; for n = -k < 0, the second law applied to a^m gives (a^m)^{-k} = ((a^m)^k)^{-1} = (a^{mk})^{-1} = a^{-mk}. \square

Proof of Theorem 2. e = a^0 \in \langle a \rangle, and a^m(a^n)^{-1} = a^{m - n} by Lemma 1, so the one-step test (Subgroups, Theorem 3) applies. A subgroup containing a contains every a^k by Lemma 4 there. \square

Proof of Theorem 3. Any two elements are a^m and a^n, and a^m a^n = a^{m + n} = a^n a^m. \square

Proof of Theorem 4. (a) Divide: k = qn + r with 0 \le r < n, and a^k = (a^n)^q a^r = a^r by Lemma 1. As n is the least positive exponent giving e, a^r = e only for r = 0; so a^k = e exactly when n \mid k. Next, a^i = a^j if and only if a^{i - j} = e, that is, n \mid i - j. Every a^k equals some a^r with 0 \le r < n, and these are distinct, since 0 < j - i < n for 0 \le i < j < n. (b) a^i = a^j with i < j would give a^{j - i} = e with j - i \ge 1. \square

Proof of Theorem 5. (a) f is onto by definition. As G is infinite, Theorem 4(a) rules out finite order, so f is one-to-one by Theorem 4(b); and f(j + k) = a^j a^k by Lemma 1. (b) By Theorem 4, \operatorname{ord}(a) = |G| = n, and [j] = [k] if and only if n \mid j - k, if and only if a^j = a^k. Read forward this says f is well defined, read backward that it is one-to-one. It is onto as G = \{a^k\}, and f([j] + [k]) = f([j + k]) = a^{j + k} = a^j a^k. \square

Proof of Theorem 6. Let G = \langle a \rangle and \{e\} \ne H \le G. Some a^k \in H has k \ne 0, and a^{-k} \in H too, so H contains a positive power of a. By the well-ordering principle (Strong induction and well-ordering) there is a least m \ge 1 with a^m \in H, and \langle a^m \rangle \subseteq H by Theorem 2. Conversely, let a^k \in H and write k = qm + r with 0 \le r < m. Then a^r = a^k(a^m)^{-q} \in H, so r = 0 by the choice of m, and a^k = (a^m)^q \in \langle a^m \rangle. \square

Proof of Corollary 7. \mathbb{Z} = \langle 1 \rangle, so by Theorem 6 a subgroup is \{0\} = 0\mathbb{Z} or \langle m \rangle = m\mathbb{Z}, and each n\mathbb{Z} is a subgroup by Theorem 2. For n \ge 1, n is the least positive element of n\mathbb{Z}, and 0\mathbb{Z} has none, so different n give different sets. \square

Proof of Theorem 8. By Lemma 1 and Theorem 4(a), (a^k)^m = a^{km} = e if and only if n \mid km. Write n = dn' and k = dk', so \gcd(n', k') = 1; then n \mid km if and only if n' \mid k'm. This holds if n' \mid m. Conversely, Bezout’s identity (Bezout's identity and the extended Euclidean algorithm) gives integers u, v with un' + vk' = 1, so m = un'm + vk'm is a multiple of n' whenever n' \mid k'm. So (a^k)^m = e exactly when n' \mid m, and the least positive such m is n' = n/d. Next, a^k = (a^d)^{k'} \in \langle a^d \rangle, and writing d = un + vk gives a^d = (a^n)^u (a^k)^v = (a^k)^v \in \langle a^k \rangle. By Theorem 2 each subgroup contains the other. \square

Proof of Corollary 9. \langle a^k \rangle \subseteq \langle a \rangle, a set of n elements, so they are equal exactly when n/\gcd(n, k) = n. By Theorem 4 the elements of \langle a \rangle are the a^k with 0 \le k \le n - 1, each once, and \varphi(n) of these k are prime to n (as \gcd(0, n) = \gcd(n, n)). \square

Proof of Theorem 10. (a) A subgroup is \langle a^k \rangle for some k by Theorem 6 (with \{e\} = \langle a^0 \rangle), of order n / \gcd(n, k) by Theorems 4 and 8, a divisor of n. (b) \langle a^{n/d} \rangle has order n / \gcd(n, n/d) = d. If H also has order d, then H = \langle a^k \rangle = \langle a^g \rangle with g = \gcd(n, k) and d = n/g, so H = \langle a^{n/d} \rangle. (c) If t \mid s, then a^s = (a^t)^{s/t} \in \langle a^t \rangle, and Theorem 2 applies. If a^s \in \langle a^t \rangle, then a^s = a^{tj} for some j, so n \mid s - tj; as t \mid n, t \mid s. \square

Worked examples

Example 1

Orders in the integers mod 30

In \mathbb{Z}_{30}, list \langle 18 \rangle and find \operatorname{ord}(18) and \operatorname{ord}(25). Then list the generators of \mathbb{Z}_{30}.

Solution

Writing k for [k], the multiples of 18 are 18, 36 \equiv 6, 24, 42 \equiv 12 and 60 \equiv 0, so \langle 18 \rangle = \{0, 6, 12, 18, 24\} and \operatorname{ord}(18) = 5. Theorem 8 with a = 1 agrees: \gcd(30, 18) = 6, so the order is 30/6 = 5 and \langle 18 \rangle = \langle 6 \rangle. Likewise \gcd(30, 25) = 5 gives \operatorname{ord}(25) = 6. By Corollary 9 the generators are the k divisible by none of 2, 3, 5: 1, 7, 11, 13, 17, 19, 23, 29, which is \varphi(30) = 8 of them.

Example 2

The units mod 25

Show that \mathbb{Z}_{25}^\times is cyclic with generator 2. Find every element of order 4, and the number of generators.

Solution

|\mathbb{Z}_{25}^\times| = \varphi(25) = 20. Mod 25, 2^5 = 32 \equiv 7 and 2^{10} \equiv 49 \equiv -1, so 2^{20} \equiv 1 and \operatorname{ord}(2) divides 20 (Theorem 4). As 2^1, 2^2, 2^4, 2^5, 2^{10} are 2, 4, 16, 7, 24, none of them 1, \operatorname{ord}(2) = 20, and \langle 2 \rangle has 20 elements: it is all of \mathbb{Z}_{25}^\times.

An element of order 4 generates a subgroup of order 4, and by Theorem 10 the only one is \langle 2^{20/4} \rangle = \langle 7 \rangle, with elements 7, 7^2 \equiv 24, 7^3 \equiv 168 \equiv 18 and 7^4 \equiv 126 \equiv 1. As 24 \equiv -1 has order 2, the elements of order 4 are 7 and 18, the \varphi(4) = 2 generators of \langle 7 \rangle. By Corollary 9 the group has \varphi(20) = 8 generators.

Example 3

Orders on the unit circle

In \mathbb{C}^\times, find the orders of \displaystyle z = \operatorname{cis}\frac{3\pi}{4} and of w = \operatorname{cis} 1 (one radian). Then show that the circle S^1 is not cyclic.

Solution

By De Moivre’s theorem (Multiplying, powers and De Moivre's theorem), (\operatorname{cis}\theta)^k = \operatorname{cis} k\theta, which is 1 exactly when k\theta is a multiple of 2\pi. So z^k = 1 if and only if 8 \mid 3k, that is, 8 \mid k (as \gcd(3, 8) = 1, by the Bezout step in the proof of Theorem 8). Hence \operatorname{ord}(z) = 8; in fact z = \omega_8^3, so \langle z \rangle = \mu_8 by Corollary 9. Next, w^k = 1 with k \ge 1 would need k = 2\pi j for a positive integer j, making \displaystyle \pi = \frac{k}{2j} rational. As \pi is irrational (used here without proof), w has infinite order, and \langle w \rangle \le S^1 is infinite cyclic.

Suppose S^1 = \langle g \rangle. As S^1 is infinite, g has infinite order (Theorem 4). For k \ne 0 and m \ge 1, (g^k)^m = g^{km} \ne 1 by Theorem 4(b), so no element but 1 has finite order. But i \in S^1 has order 4. So S^1 is not cyclic.

Example 4

Two groups that are not cyclic

Prove that (\mathbb{Q}, +) is not cyclic and that \mathbb{Z}_{24}^\times is not cyclic.

Solution

Suppose \mathbb{Q} = \{kr : k \in \mathbb{Z}\}. Then r \ne 0, and \displaystyle \frac{r}{2} \in \mathbb{Q}, so \displaystyle \frac{r}{2} = kr for an integer k; dividing by r gives \displaystyle k = \frac{1}{2}, a contradiction (Proof by contradiction).

\mathbb{Z}_{24}^\times = \{1, 5, 7, 11, 13, 17, 19, 23\} has 8 elements, and 5^2 = 25, 7^2 = 49, 11^2 = 121, 13^2 = 169, 17^2 = 289, 19^2 = 361, 23^2 = 529 are each 1 more than a multiple of 24. So every element has order 1 or 2, each \langle a \rangle has at most 2 elements (Theorem 4), and no element generates. Thus Theorem 3 has no converse.

Example 5

Every subgroup of the integers mod 36

Find all subgroups of \mathbb{Z}_{36} and order them by inclusion. Which subgroups are \langle 27 \rangle and \langle 20 \rangle, and which subgroups contain 6?

Solution

\mathbb{Z}_{36} = \langle 1 \rangle, so by Theorems 6 and 10 the subgroups are exactly one for each divisor d of 36, namely \langle 36/d \rangle of order d: \langle 1 \rangle, \langle 2 \rangle, \langle 3 \rangle, \langle 4 \rangle, \langle 6 \rangle, \langle 9 \rangle, \langle 12 \rangle, \langle 18 \rangle and \langle 36 \rangle = \{0\}, of orders 36, 18, 12, 9, 6, 4, 3, 2, 1. By Theorem 10(c), \langle s \rangle \subseteq \langle t \rangle exactly when t \mid s, which gives the diagram.

\{0\}
\langle 18 \rangle
\langle 12 \rangle
\langle 9 \rangle
\langle 6 \rangle
\langle 4 \rangle
\langle 3 \rangle
\langle 2 \rangle
\mathbb{Z}_{36}
Figure 2The nine subgroups of \mathbb{Z}_{36} (Example 5), one for each divisor of 36, each joined to the subgroups just above it that contain it.

By Theorem 8, \langle 27 \rangle = \langle \gcd(36, 27) \rangle = \langle 9 \rangle = \{0, 9, 18, 27\}, and \langle 20 \rangle = \langle 4 \rangle, of order 9. A subgroup contains 6 exactly when it contains \langle 6 \rangle (Theorem 2): these are \langle 1 \rangle, \langle 2 \rangle, \langle 3 \rangle and \langle 6 \rangle.

Example 6

Restoring a deck by shuffling

Amara, a magician, does perfect out-shuffles of a 52-card deck: she cuts it into the top 26 and the bottom 26 cards and interleaves them one at a time, the top card staying on top. How many out-shuffles restore the deck? Where is the card that started second after five shuffles?

Solution

Number the positions 0 to 51 from the top. After a shuffle the deck reads, by old positions, 0, 26, 1, 27, \dots, 25, 51: the card at i \le 25 moves to 2i, and the card at 26 + j moves to 2j + 1 = 2(26 + j) - 51. So for i \le 50 the card at i moves to 2i \bmod 51, and the bottom card stays. In \mathbb{Z}_{51}, one shuffle multiplies positions by 2, and k shuffles by 2^k.

The deck is restored exactly when 2^k i \equiv i \pmod{51} for every i; taking i = 1, this means 2^k \equiv 1. So the answer is \operatorname{ord}(2) in \mathbb{Z}_{51}^\times. As 2^8 = 256 = 5 \cdot 51 + 1, the order divides 8, and 2, 4, 16 are not 1: Amara needs 8 out-shuffles. The card that started at position 1 passes through 1, 2, 4, 8, 16, 32, 13, 26, the elements of \langle 2 \rangle, so after five shuffles it is at position 32.

Example 7

Groups with no proper nontrivial subgroups

Prove that if G \ne \{e\} and the only subgroups of G are \{e\} and G, then G is cyclic of prime order.

Solution

Proof. Pick a \ne e. Then \langle a \rangle \ne \{e\}, so \langle a \rangle = G. If a had infinite order, \langle a^2 \rangle would be a third subgroup: a^2 \ne e, and a \notin \langle a^2 \rangle, since a = a^{2k} would give 1 = 2k by Theorem 4(b). So n = \operatorname{ord}(a) = |G| is finite, and n \ge 2. If n = rs with 1 < r < n, then by Theorem 8 \langle a^r \rangle has order n / \gcd(n, r) = s, with 1 < s < n, again a third subgroup. So n is prime. \square Conversely, by Theorem 10(a) \mathbb{Z}_p has only subgroups of order 1 and p.

Boundaries

  • Abelian is not enough. \mathbb{Z}_{24}^\times and (\mathbb{Q}, +) are abelian and not cyclic (Example 4), and \mathbb{Z}_{20}^\times has three subgroups of order 2 (Subgroups, Example 5).
  • Theorem 8 needs finite order. An infinite cyclic group has only the two generators a and a^{-1} (Exercise 13).
  • Orders of products need commuting. In \operatorname{GL}_2(\mathbb{R}), A = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} and B = \begin{pmatrix} -1 & 1 \\ 0 & 1 \end{pmatrix} have order 2, but AB = \begin{pmatrix} -1 & 1 \\ 0 & -1 \end{pmatrix} has infinite order, as (AB)^k = (-1)^k \begin{pmatrix} 1 & -k \\ 0 & 1 \end{pmatrix}. Compare Exercise 14.

Where this goes next

Powers of a permutation are the subject of Permutation groups and cycle notation, and the rotations of a polygon form the cyclic part of the Dihedral groups. Cosets of \langle a \rangle lead to Lagrange's theorem: in a finite group \operatorname{ord}(a) divides |G|, so every group of prime order is cyclic. Isomorphisms makes Theorem 5 a statement about maps, and Direct products and finite abelian groups decides when \mathbb{Z}_m \times \mathbb{Z}_n is cyclic, the group form of the The Chinese remainder theorem.

Exercises

Orders and generators

  1. In \mathbb{Z}_{40}, find \operatorname{ord}(14) and \operatorname{ord}(25), and list \langle 25 \rangle.
  2. List the generators of \mathbb{Z}_{18}, and find how many generators \mathbb{Z}_{100} has.
  3. Show that 2 generates \mathbb{Z}_{11}^\times, and list all generators of \mathbb{Z}_{11}^\times.
  4. Find the orders of A = \begin{pmatrix} 0 & -1 \\ 1 & 1 \end{pmatrix} and B = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} in \operatorname{GL}_2(\mathbb{R}).
  5. Find the orders in \mathbb{C}^\times of (a) -i; (b) \displaystyle \frac{1 + \sqrt{3}\,i}{2}; (c) \displaystyle \operatorname{cis}\frac{4\pi}{9}; (d) 3i.
  6. Is \mathbb{Z}_{21}^\times cyclic?

Subgroups of cyclic groups

  1. List every subgroup of \mathbb{Z}_{45} with a generator and its order. Which one is \langle 30 \rangle?
  2. Let G = \langle a \rangle have order 60. How many subgroups does G have? List the elements of order 12.
  3. In \mathbb{Z}_{48}, find \langle 32 \rangle \cap \langle 36 \rangle and the smallest subgroup containing both 32 and 36.
  4. How many perfect out-shuffles (as in Example 6) restore a deck of 8 cards? Of 20 cards?
  5. Jin does perfect in-shuffles of 52 cards: the same cut, but the bottom half’s top card goes on top. With positions numbered 1 to 52, show that the card at position p moves to 2p \bmod 53. How many in-shuffles restore the deck?

Proofs

  1. Prove that \operatorname{ord}(a^{-1}) = \operatorname{ord}(a) and \operatorname{ord}(gag^{-1}) = \operatorname{ord}(a) for all a, g \in G.
  2. Prove that an infinite cyclic group \langle a \rangle has exactly two generators.
  3. Let G be abelian, and let a, b \in G have finite orders m and n with \gcd(m, n) = 1. Prove that \operatorname{ord}(ab) = mn.
  4. Prove that a cyclic group has at most one element of order 2. Deduce that \mathbb{Z}_{2^k}^\times is not cyclic for k \ge 3.
  5. Let G be cyclic of order n and d a positive divisor of n. Prove that G has exactly \varphi(d) elements of order d, and deduce that \sum_{d \mid n} \varphi(d) = n.
Answers
  1. By Theorem 8, \operatorname{ord}(14) = 40/\gcd(40, 14) = 20 and \operatorname{ord}(25) = 40/5 = 8; \langle 25 \rangle = \langle 5 \rangle = \{0, 5, 10, 15, 20, 25, 30, 35\}.
  2. The k prime to 18: 1, 5, 7, 11, 13, 17. \mathbb{Z}_{100} has \varphi(100) = 40 (Corollary 9).
  3. Mod 11, 2^1, \dots, 2^{10} are 2, 4, 8, 5, 10, 9, 7, 3, 6, 1: all ten classes. The generators are the 2^k with \gcd(k, 10) = 1, k = 1, 3, 7, 9: 2, 8, 7, 6.
  4. \operatorname{ord}(A) = 6: A^2 = \begin{pmatrix} -1 & -1 \\ 1 & 0 \end{pmatrix} and A^3 = -I_2, so A^4 = -A, A^5 = -A^2, A^6 = I_2. B has infinite order: B^k = \begin{pmatrix} 1 & k \\ 0 & 1 \end{pmatrix} \ne I_2 for k \ge 1.
  5. (a) 4: (-i)^2 = -1. (b) 6: it is \displaystyle \operatorname{cis}\frac{\pi}{3}, and \displaystyle \frac{k}{6} is first an integer at k = 6. (c) 9: \displaystyle \frac{2k}{9} is an integer exactly when 9 \mid k. (d) Infinite: |(3i)^k| = 3^k > 1 for k \ge 1.
  6. No. It has \varphi(21) = 12 elements, but for x prime to 21, Fermat's little theorem gives x^2 \equiv 1 \pmod 3 and x^6 \equiv 1 \pmod 7, so 21 \mid x^6 - 1. Every order divides 6 (Theorem 4), so no element has order 12 and none generates.
  7. Six, one per divisor of 45: \langle 1 \rangle (order 45), \langle 3 \rangle (15), \langle 5 \rangle (9), \langle 9 \rangle (5), \langle 15 \rangle (3), \{0\} (1). As \gcd(45, 30) = 15, \langle 30 \rangle = \langle 15 \rangle = \{0, 15, 30\}.
  8. 12 subgroups, one per divisor 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60. The elements of order 12 generate the one subgroup of order 12, \langle a^5 \rangle: they are a^{5k} with \gcd(k, 12) = 1, that is, a^5, a^{25}, a^{35}, a^{55}.
  9. \langle 32 \rangle = \{0, 16, 32\} and \langle 36 \rangle = \{0, 12, 24, 36\} (Theorem 8), so the intersection is \{0\}. A subgroup containing 32 and 36 contains 16, 12 and 16 - 12 = 4, and \langle 4 \rangle contains both: the answer is \langle 4 \rangle, of order 12.
  10. As in Example 6, a 2m-card out-shuffle multiplies positions 0, \dots, 2m - 2 by 2 in \mathbb{Z}_{2m - 1}. For 8 cards, 2^3 = 8 \equiv 1 \pmod 7: 3 shuffles. For 20 cards, 2^9 = 512 = 27 \cdot 19 - 1, so 2^{18} \equiv 1 \pmod{19}; as 2^1, 2^2, 2^3, 2^6 = 64 \equiv 7, 2^9 are not 1, the order is 18: 18 shuffles.
  11. The new deck reads 27, 1, 28, 2, \dots, 52, 26 by old positions, so p \le 26 moves to 2p, and 26 + j moves to 2j - 1 = 2(26 + j) - 53. So k shuffles multiply by 2^k in \mathbb{Z}_{53}^\times. Mod 53, 2^{13} = 8192 \equiv 30 and 2^{26} \equiv 900 \equiv -1, so 2^{52} \equiv 1; as 2, 4, 16, 2^{13}, 2^{26} are not 1, \operatorname{ord}(2) = 52: 52 in-shuffles.
  12. Proof. (a^{-1})^k = (a^k)^{-1} (Lemma 1) is e exactly when a^k = e, so the same positive k work for both. For k \ge 1, (gag^{-1})^k = ga^kg^{-1} by induction (ga^kg^{-1} \cdot gag^{-1} = ga^{k + 1}g^{-1}), and ga^kg^{-1} = e if and only if a^k = g^{-1}eg = e. \square
  13. Proof. If \langle a^k \rangle = \langle a \rangle, then a = a^{km} for some m, so 1 = km by Theorem 4(b), and k = \pm 1. Conversely \langle a^{-1} \rangle = \langle a \rangle, as (a^{-1})^j = a^{-j}; and a \ne a^{-1}, since a^2 \ne e. \square
  14. Proof. In an abelian group (ab)^k = a^k b^k, so (ab)^{mn} = (a^m)^n (b^n)^m = e. Let (ab)^k = e. Then a^k = b^{-k} lies in K = \langle a \rangle \cap \langle b \rangle, a subgroup of both (Subgroups, Theorem 6). By Theorem 10(a), |K| divides m and n, so K = \{e\}, and a^k = b^k = e. By Theorem 4(a), m \mid k and n \mid k; with k = mq, n \mid mq and \gcd(m, n) = 1 give n \mid q (the Bezout step of Theorem 8), so mn \mid k. Hence \operatorname{ord}(ab) = mn. \square
  15. Proof. An infinite cyclic group has none: by Theorem 4(b), (a^k)^2 = e forces 2k = 0. In a finite cyclic group an element of order 2 generates a subgroup of order 2; Theorem 10 allows only one, and its only element of order 2 is its one element besides e. \square For k \ge 3, (2^{k - 1} \pm 1)^2 = 2^{2k - 2} \pm 2^k + 1 \equiv 1 and (2^k - 1)^2 \equiv 1 \pmod{2^k}, as 2k - 2 \ge k. The classes 2^{k - 1} - 1, 2^{k - 1} + 1, 2^k - 1 are distinct and not 1: three elements of order 2, so \mathbb{Z}_{2^k}^\times is not cyclic.
  16. Proof. An element of order d generates a subgroup of order d (Theorem 4), and by Theorem 10 there is exactly one, H = \langle a^{n/d} \rangle. So the elements of order d are the generators of H, and by Corollary 9 there are \varphi(d) of them. Every element has an order dividing n (Theorem 10(a) for \langle x \rangle), so sorting the n elements by order gives n = \sum_{d \mid n} \varphi(d). \square
math.wiki · updated 2026-11-17 · CC-BY-SA-4.0