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. Let G be a group. A cyclic group G is a group that can be generated by a single element a. More formally, G is cyclic if there exists at least an element a ∈ G: G = ⟨a⟩ = {an | n ∈ ℤ}. We call such an element a generator of G.

The order of a is the number of elements in ⟨a⟩, that is, the order of the cyclic subgroup that it generates. For a finite cyclic group G of order n we have ⟨a⟩ = {e, a, a2,…, an-1}, where e is the identity element, ai = aj whenever i ≡ j (mod n). In particular, an = a0 = e and a-1 = an-1. In other words, the order of a is the smallest positive integer n such that an = e, and we write it as |a| = n. If no such positive integer exists, we say that a has infinite order, |a| = ∞.

Theorem: Every cyclic group is Abelian.

Proof: If g and h ∈⟨a⟩ ⇒ g = am, h = an for some m, n ∈ Z ⇒ gh = am+n = an+m = anam = hg∎

Theorem. Every subgroup of a cyclic group is cyclic.

Proof. Let G be cyclic, there exists at least an element a ∈ G: ⟨a⟩ = G. Suppose that H is a subgroup of G, H ≤ G. There are two possibilities, namely:

1. If H is the trivial subgroup, H = {e} ⇒ H = ⟨e⟩, and H is obviously cyclic.

2. Otherwise, if H is not the trivial subgroup, H ≠ {e} ⇒ ∃g ∈ H: g ≠ e, g = an ⇒ [Well-ordering principle. Every non-empty set of positive integers contains a least element.] Let m be the smallest natural number such that h = am ∈ H

We claim that H = ⟨h⟩ = ⟨am. Let h’ be an arbitrary element of H, h’ ∈ H ⇒ h’ = ak.

By the division algorithm, ∃q, r: k = mq + r where 0 ≤ r < m ⇒ ak = amq+r = amqar = (am)qar = hqar ⇒ ar = akh-q ∈ H [h’ = ak and h-q∈ H], but r < m, and h = am is the smallest element in H ⇒ r = 0 ⇒ k = mq, h’ = ak = amq = hq, and therefore, since h’ was an arbitrary element of H and it is generated by h = am ⇒ H = ⟨h⟩ = ⟨am⟩∎

Theorem. 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

Proof

Let |G| = n. By assumption d | n, let us consider h = gn/d. It is obvious that hd = (gn/d)d = gn = [G = ⟨g⟩, |G| = n] e.

If a ∈ ℤ, 1 ≤ a < d ⇒ [a < d ⇒ an/d < dn/d(=n)] 1 ≤ an/d < n. Thus, ha = gna/d ≠ e because 1 ≤ an/d < n and no power less than n can get g to the identity. Then, d is the smaller power that can get h to the identity ⇒ [By definition] |h| = d ⇒ |⟨h⟩| = d. So there is at least one such subgroup.

Let’s prove uniqueness. Let k ∈ G: |k| = d. G is cyclic so ∃m: k = gm. gdm = (gm)d = kd = e ⇒ [ga =e ↭ |g| | a] n | dm ⇒ ∃l ∈ ℤ: nl = dm ⇒ (n/d)l = m ⇒ k = gm = (gn/d)l = hl ∈ ⟨h⟩ ⇒ k = hl ∈⟨h⟩ ⇒ ⟨k⟩ ⊆ ⟨h⟩, but these are two finite sets with the same order, so they are the same set ∎

Corollary. The subgroups of ℤ are exactly nℤ and the subgroups of ℤn are exactly mℤn.

Proof.

(ℤ, +) is an infinite cyclic group. nℤ = {nk | k ∈ ℤ} are all cyclic subgroups of ℤ by definition, but we have demonstrated that being ℤ cyclic (ℤ = ⟨1⟩), then all its subgroups are necessarily cyclic ⇒ These are exactly all the subgroups of ℤ, and more importantly, there are no other subgroups left.

By similar reasoning, ℤn is a cyclic finite group, all their cyclic groups are mℤn = {mk | k ∈ ℤn} by definition, and as was reasoned before, their only subgroups are cyclic subgroups, so the subgroups of ℤn are exactly mℤn.

Theorem. Let G be a finite cyclic group generated by an element a, G = ⟨a⟩, |G| = n. Then ak = e iff n divides k.

Proof.

⇒) Let’s suppose that ak = e. By the division algorithm, k = nq +r, where 0 ≤ r < n ⇒ ak = anq+r = anqar ⇒ [ak = e, anq=a0=e because an = e or it could also be argued that nq≡0 (mod n)] e = ar ⇒ r = 0 because r < n and n is the smallest integer m such that am = e ⇒ k = nq ⇒ n | k.

⇐) Conversely, let’s suppose n divides k ⇒ k = ns for some integer s ⇒ ak = ans = (an)s = es = e∎

Exercise: Suppose G is cyclic, a ∈ G, a is an element of order n, and a24 = e. What are the possibilities of n?

a24=e ⇒ k = 24 ⇒ n|24 ⇒ n needs to be 1, 2, 3, 4, 6, 8, 12 or 24.

Proposition. Let G be an arbitrary group, a ∈ G, and let m, n ∈ ℤ. If an = e and am = e, then agcd(m, n) = 1.

This proposition gives the method for reducing arbitrary powers of a generator in a finite cyclic group to the least residue power.

Proof.

By the Euclidean Algorithm, there exists r, s ∈ ℤ such that d = mr + ns, d = gcd(m, n) =notation (m, n) ⇒ ad = amr+ns = amrans = (am)r(an)s = [By assumption, am = e, an = e] eres = 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:

1. 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}.
2. 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}.
3. 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.
4. 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 ℤnG ≋ ℤ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

This content is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. This post relies heavily on the following resources, specially on NPTEL-NOC IITM, Introduction to Galois Theory, Michael Penn, and Contemporary Abstract Algebra, Joseph, A. Gallian.
1. NPTEL-NOC IITM, Introduction to Galois Theory.
2. Algebra, Second Edition, by Michael Artin.
3. LibreTexts, Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
4. Field and Galois Theory, by Patrick Morandi. Springer.
5. Michael Penn (Abstract Algebra), and MathMajor.
6. Contemporary Abstract Algebra, Joseph, A. Gallian.
7. Andrew Misseldine: College Algebra and Abstract Algebra.
Bitcoin donation