Cyclic Groups II. Fundamental Theorem.
An expert is a person who has made all the mistakes that can be made in a very narrow field, Neils Bohr.
Recall
Definition: A group $G$ is called cyclic if there exists at least one element $a \in G$ that generates the entire group. That is, $G = \langle a \rangle$.
We call the element $a$ a generator of the group.
The order of an element $a$, denoted $\vert{}a\vert{}$, is the number of elements inside the subgroup it generates ($\vert{}\langle a \rangle\vert{}$). Equivalently, $|a| = \min \{n \in \mathbb N \mid a^n=e \},$ if such a positive integer $n$ exists. If no such $n$ exists, then $a$ has infinite order and we write $|a| = \infty.$
Theorem. The Fundamental Theorem of Cyclic Groups. Let $G = \langle g \rangle$ be a finite cyclic group of order $n$. For every positive divisor $d$ of $n$, $G$ has a unique subgroup of order $d$, namely $H = \langle g^{n/d} \rangle$.
Orders and Generators of Powers in Cyclic Groups
Suppose you have an element $a$ of order $n$, and you take a power of it, $a^k$. What subgroup does $a^k$ generate, and what is its exact order? The following theorem answers both questions completely using only the greatest common divisor.
Theorem: Let $a$ be an element of finite order $n$ in a group $G$, and let $k \in \mathbb{Z}$ be any integer. Then, $\langle a^k \rangle = \langle a^{\gcd(n, k)} \rangle \quad \text{and} \quad \vert{}a^k\vert{} = \vert{}\langle a^k \rangle\vert{} = \frac{n}{\gcd(n, k)}$
Proof:
Let $b = a^k$ and $d = \gcd(n, k)$.
Step 1. Finding the Order $\vert{}a^k\vert{}$:
We want to find the smallest positive integer $m$ such that $b^m = a^{km} = e$. Because $\vert{}a\vert{} = n$, we know $a^{km} = e$ if and only if $n \mid km$.
Dividing both sides of this divisibility relation by $d = \gcd(n, k)$ gives an equivalent condition: $\frac{n}{d} \;\Big\vert{}\; m \left(\frac{k}{d}\right)$
Because we divided both $n$ and $k$ by their greatest common divisor, the integers $\frac{n}{d}$ and $\frac{k}{d}$ are coprime: $\gcd\left(\frac{n}{d}, \frac{k}{d}\right) = 1$. By Euclid’s Lemma, $\frac{n}{d}$ cannot share any factors with $\frac{k}{d}$, so it must divide $m$: $\frac{n}{d} \;\Big\vert{}\; m$.
The smallest positive integer $m$ divisible by $\frac{n}{d}$ is simply $m = \frac{n}{d}$. Therefore, $\vert{}a^k\vert{} = \vert{}\langle a^k \rangle\vert{} = \frac{n}{d} = \frac{n}{\gcd(n, k)}$
Step 2. Proving $\langle a^k \rangle = \langle a^d \rangle$:
Since $\vert{}a^k\vert{} = \frac{n}{d}$ the subgroup $\langle a^k\rangle$ has order $\frac{n}{d}$.
By the Fundamental Theorem of Cyclic Groups, the finite cyclic group $\langle a \rangle$ of order $n$ has a unique subgroup of order $m = n/d$, namely $\langle a^{n/(\frac{n}{d})} \rangle = \langle a^d \rangle$.
Therefore, $\vert{}a^k\vert{} = \langle a^d \rangle$.
Since $d = \gcd(n, k), \vert{}a^k\vert{} =\langle a^{\gcd(n, k)} \rangle$ $\blacksquare$
Four Powerful Corollaries
This single theorem immediately unlocks four major structural facts about finite cyclic groups.
Divisibility of Element Orders Corollary. In a finite cyclic group, the order of every element divides the order of the group. In fact, by Lagrange’s Theorem, this holds in any finite group.
Example: Consider the multiplicative group of units $U_{14} = \{1, 3, 5, 9, 11, 13\}$, which has order $\vert{}U_{14}\vert{} = 6$. Every element’s order must divide $6$ (so the only possible orders are $1, 2, 3,$ and $6$):$\langle 1 \rangle = \{1\}$, so $\vert{}1\vert{} = 1$.$\langle 13 \rangle = \{13, 1\}$, so $\vert{}13\vert{} = 2$.$\langle 9 \rangle = \{9, 11, 1\}$ and $\langle 11 \rangle = \{11, 9, 1\}$, so $\vert{}9\vert{} = \vert{}11\vert{} = 3$.$\langle 3 \rangle = \{3, 9, 13, 11, 5, 1\} = U_{14}$ (since $3^3 = 27 \equiv 13 \pmod{14}$) and $\langle 5 \rangle = U_{14}$, so $\vert{}3\vert{} = \vert{}5\vert{} = 6$.
Proposition: Let $G$ be an arbitrary group, let $a \in G$, and let $m, n \in \mathbb{Z}$. If $a^m = e$ and $a^n = e$, then $a^{\gcd(m, n)} = e$.
Theorem. Let a be an arbitrary element of order n in a group G, and let k be a positive integer. Then, ⟨ak⟩=⟨agcd(n,k)⟩ and |⟨ak⟩| = $\frac{n}{gcd(n,k)}.$
Proof.
Let b = ak and d = gcd(k, n). We need to know the smallest integer m such that e = bm = akm. By the previous theorem, [Theorem. Let G be a finite cyclic group generated by an element a, G = ⟨a⟩, |G| = n. Then ak = e iff n divides k.] this is the smallest integer m such that n divides km or n/d divides m(k/d). d = gcd(k, n), and therefore n/d and k/d are coprimes, [n/d|m(k/d), (n/d,k/d)=1]the smallest m s.t. n/d | m is m = n/d ⇒ [Let G be a finite cyclic group, G = ⟨g⟩. Then, G has exactly one subgroup of order d for each d | |G|, namely H = ⟨gn/d⟩ ≤ G] ⟨ak⟩ = ⟨an/d⟩ = ⟨an/gcd(k,n)⟩.
Example. Suppose |a|=24 and k=10. ⟨ak⟩= ⟨a10⟩= ⟨agcd(n,k)⟩ = ⟨agcd(24, 10)⟩ = ⟨a2⟩ = {a2, a4, a6, … a22, a0} and |⟨a10⟩| = $\frac{24}{gcd(24,10)}=\frac{24}{2}=12.$
Corollaries:
- In a finite cyclic group, the order of an element divides the order of the group. Example: U14 = {1, 3, 5, 9, 11, 13}, |U14| = 6, so the order of their elements are 1, 2, 3, and 6. |⟨1⟩|=1; |⟨3⟩| = 6 and ⟨3⟩ = {3, 9, (33 = 27 % 14 = 13) 13, 11, 5, 1} = ⟨5⟩, |⟨5⟩| = 6, |⟨9⟩|=3 and ⟨9⟩ = {9, 11, 1}, |⟨11⟩|=3, ⟨11⟩ = {11, 9, 1}, |⟨13⟩| = 2, ⟨13⟩ = {13, 1}.
- Let |a| = n. Then ⟨ai⟩=⟨aj⟩ iff $\frac{n}{gcd(n,i)}=\frac{n}{gcd(n,j)}$ ↭ gcd(n, i) = gcd(n, j) and |ai| = |aj| = $\frac{n}{gcd(n,i)}$. Since G = ⟨a⟩ is a cyclic group, it has exactly one subgroup of order d for each d| |⟨a⟩|. Example: Suppose |a| = 15. Compute the orders of a6 and a8. |a6|= $\frac{15}{gcd(15, 6)}=\frac{15}{3}=5$. |a8|= $\frac{15}{gcd(15, 8)}=\frac{15}{1}=15$. In U14, |32| = $\frac{|3|}{gcd(|3|, 2)}=\frac{6}{gcd(6,2)}=\frac{6}{2} = 3$. In U14, |⟨9⟩|=3 and ⟨9⟩ = {9, 11, 1}.
- Let |a|=n. Then ⟨a⟩=⟨aj⟩ iff $\frac{n}{gcd(n, j)}=n$ ↭ gcd(n, j) = 1. In particular, the number of generators of ⟨a⟩ is φ(n) where φ is Euler’s φ-function. Example: ⟨5⟩ = U14 = {1, 3, 5, 9, 11, 13}, |U14| = 6. Which other element generates U14? gcd(6, j) = 1 ⇒ j = 1 (⟨51⟩ = ⟨5⟩ = U14) and j = 5 (⟨55⟩= [52 = 25 ≡14 11, 53 = 55 ≡14 13, 54 = 65 ≡14 9, 55 = 45 ≡14 3] ⟨3⟩ = U14.
- An integer k ∈ ℤn is a generator of ℤn iff gcd(n, k) = 1. Addition notation, G = ℤn = ⟨1⟩, |G| = n, k ∈ ℤn ⇒ k = 1 + 1 + ··ₖ·· + 1 = k·1, ⟨k⟩ = G ↭ gcd(n, k) = 1.
As a result, the generators of ℤn are the integers k such that |⟨ak⟩| =[a = 1 in ℤn = ⟨1⟩, k = k·1] |⟨k⟩| n/d = n where d = gcd(k, n) = 1. In other words, the generators of ℤn are the integers k that are relatively prime to n.
Examples:
- 1 and 3 are generators of ℤ4 (φ(4) = 2), 1 and 5 are generators of Z6 (φ(6) = 2), and 1, 5, 7, and 11 are the generators of ℤ12 (φ(12) = 4).
- In ℤ12, |⟨2⟩|= 12/gcd(12, 2)= 6, ⟨2⟩ = {0, 2, 4, 6, 8, 10}; |⟨3⟩|= 12/gcd(12, 3)= 4, ⟨3⟩ = {0, 3, 6, 9}; |⟨4⟩|= 12/gcd(12, 4)= 3, ⟨4⟩ = {0, 4, 8}; |⟨6⟩|= 12/gcd(12, 6)= 2, ⟨6⟩ = {0, 6}; |⟨9⟩|= 12/gcd(12, 9)= 12/3 = 4, ⟨3⟩ = ⟨9⟩ = {0, 3, 6, 9}.
Theorem. Let G be a cyclic group with generator a. If the order of G is infinite, then G is isomorphic to (ℤ, +). Otherwise, G is isomorphic to (ℤn, +n)
Proof.
If the order of G is infinite, ∀m ∈ ℤ, m ≠ 0, am ≠ e. We claim that ∀h, k ∈ ℤ, ah ≠ ak. Suppose ah = ak and h > k ⇒ aha-k = ah-k = e ⊥ .i.e, contrary to our assumption that G is infinite. Therefore, ∀g ∈ G, g = am for a unique power m ∈ ℤ.
The map Φ: (G,·) → (ℤ, +), Φ(g) = Φ(am) = m is well defined (We have already demonstrated that ∀g ∈ G, g = am for a unique power m ∈ ℤ), homomorphism (∀g1, g2 ∈ G, ∃!m1, m2 s.t. g1 = am1, g2 = am2 ⇒ Φ(g1·g2) = Φ(am1·am2) = Φ(am1+m2) = m1 + m2 = Φ(g1)+Φ(g2)), one to one (m1 = m2 ⇒ g1 = am1 = am2 = g2), and onto ℤ (∀m ∈ ℤ, m ≠ 0, am≠e, a → m, e → 0) ⇒ G ≋ ℤ.
Let’s suppose the order of G is finite. am= e for some m ∈ ℤ, m > 0. Let n be the smallest positive integer such that an = e. The map Φ: G → ℤn, given by Φ(ai)=i, for i=0, 1, 2,…n-1 is well-defined, homomorphism, one to one, and onto ℤn ⇒ G ≋ ℤn
We claim that a0 (e), a, a2, a3,… an-1 are all distinct and comprise all elements of G = ⟨a⟩, |G| = n.
Hint: s = nq + r, 0 ≤ r < n, as = anqar = (an)qar =eqar = ar, ar-s = e. If 0 < s < r < n, ar-s = e and 0 < r-s < n so it contradicts our choice of n, r = 0 and s = nq. Besides, a0 (e), a, a2, a3,… an-1 are all distinct.
is Φ homomorphism? Φ(g·g’) = Φ(g)+nΦ(g’)? ∀g, g’ ∈ H, ∃i, j such that g = ai, g’ = aj
Let k = i +n j, an = a0 = e ⇒ [ak-(i+j) = al·n = e] ak = ai+j ⇒ aiaj = ak ⇒ Φ(aiaj) = k = i +n j = Φ(ai) + Φ(aj).
Corollary. Any two cyclic groups of the same order are isomorphic.
Proof
Let ⟨a⟩ and ⟨b⟩ be cyclic groups of order n, then the map Φ: ⟨a⟩ → ⟨b⟩ defined by, Φ(ak) = bk is well-defined and is an isomorphism (you may want to check this).
Is it well-defined? If ar = as ⇒ Φ(ar) = Φ(as) ↭ br = bs
ar = as ⇒ ar-s = e ⇒ n | (r -s), say r -s = tn ⇒ r = tn +s ⇒ Φ(ar) = Φ(atn+s) = btn+s = btnbs = (bn)tbs = bs.
Classification of subgroups of cyclic groups
Fundamental Theorem of Cyclic Groups. Every subgroup of a cyclic group is cyclic. If ⟨a⟩=n, then the order of any subgroup of ⟨a⟩ is a divisor of n. For each positive divisor k of n, the group ⟨a⟩ has exactly one subgroup of order k, namely, ⟨an/k⟩
Example. Suppose G = ⟨a⟩ and |G|=20. List the subgroups G and their orders.
Orders of subgroups of G: 1, 2, 4, 5, 10, and 20.
- Order 1: ⟨an/k⟩ = ⟨a20/1⟩ = ⟨a20⟩ = {e}.
- Order 2: ⟨an/k⟩ = ⟨a20/2⟩ = ⟨a10⟩ = {a10, e}.
- Order 4: ⟨an/k⟩ = ⟨a20/4⟩ = ⟨a5⟩ = {a5, a10, a15, e}.
- Order 5: ⟨an/k⟩ = ⟨a20/5⟩ = ⟨a4⟩ = {a4, a8, a12, a16, e}.
- Order 10: ⟨an/k⟩ = ⟨a20/10⟩ = ⟨a2⟩ = {a2, a4, a6, a8,… e}.
- Order 20: ⟨an/k⟩ = ⟨a20/20⟩ = ⟨a⟩ = G.
Corollary. For each positive divisor k of n, the set ⟨n/k⟩ is the unique subgroup of ℤn of order k.
Let φ(1) = 1 and for any n ∈ ℤ, n > 1, let φ(n) denote the number of positive integers less than n and relative prime to n, φ is the Euler phi function. If d is a positive divisor of n, the number of elements of order d in a cyclic group of order n is φ(d).
Proof.
By a previous result, Let G be a finite cyclic group, G = ⟨g⟩. Then, G has exactly one subgroup of order d for each d | |G|, namely H = ⟨gn/d⟩ ≤ G. Hence, for each d | |G|, G = ⟨g⟩ has exactly one subgroup of order d, say ⟨a⟩, and we have also demonstrated that ak generates ⟨a⟩ ↭ gcd(k, d) = 1 and this is by definition precisely φ(d)∎
Examples
-
ℤ12. Order of subgroups are: 1, 2, 3, 4, 6, and 12. The number of elements of order 2, 3, 4, 6, 12, are φ(1)= 1 (0), φ(2)= 1 (6, |⟨6⟩| = 2), φ(3)= 2 (4, 8), φ(4)= 2 (3, 9), φ(6)= 2 (2, 10), φ(12)= 4 (1, 5, 7, 11) respectively (Figure 1.a.)
-
ℤ24. Order of subgroups are: 1, 2, 3, 4, 6, 8, 12, and 24. Let’s list all generators for the subgroup of order 8.
⟨n/k⟩ is the unique subgroup of ℤn of order k. ⟨24/8⟩=⟨3⟩ is the unique subgroup of ℤ24 of order 8. 3 is obviously a generator, but it does not need to be the only one. ⟨3⟩=⟨3j⟩, 3j is a generator of a group of order 8 of ℤ24 where 24/gcd(8, j) = 24, that is, gcd(8, j) = 1, so 3 (j=1), 9(j=3), 15(j=5), 21(j=7). ⟨3⟩=⟨9⟩=⟨15⟩=⟨21⟩ = {3, 6, 9, 12, 15, 18, 21, 1}. There are four generators for the unique subgroup of ℤ24 of order 8, φ(8) = 4.
To sum up, in ℤ24, the number of elements of order 8 is φ(8) = 4. They are ⟨3⟩=⟨9⟩=⟨15⟩=⟨21⟩ = {3, 6, 9, 12, 15, 18, 21, 1}.
- ℤ30. Order of subgroups are: 1, 2, 3, 5, 6, 10, and 15. The number of elements of order 1, 2, 3, 5, 6, 10, and 15, are φ(1)= 1 (0), φ(2)= 1 (15), φ(3)= 2 (10, 20), φ(5)= 4 (6, 12, 18, 24), φ(6)= 2 (5, 25), φ(10)= 4 (3, 9, 21, 27) respectively (Figure 1.c.)
Bibliography
- NPTEL-NOC IITM, Introduction to Galois Theory.
- Algebra, Second Edition, by Michael Artin.
- LibreTexts, Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
- Field and Galois Theory, by Patrick Morandi. Springer.
- Michael Penn (Abstract Algebra), and MathMajor.
- Contemporary Abstract Algebra, Joseph, A. Gallian.
- Andrew Misseldine: College Algebra and Abstract Algebra.