JustToThePoint English Website Version
JustToThePoint en español
JustToThePoint in Thai

Cyclic Groups

Definition. Let G be a group and a be any element in G (a ∈ G). Then, the set ⟨a⟩={an | n ∈ Z} is a subgroup of G. We call it the cyclic subgroup generated by a.

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. If no such positive integer exists, we say that g has infinite order.

Example. In ℤ6, |0| = 1, |1| = |5| = 6, |2| = 3, |3| = 2, |4| = 3.

Besides, it is the smallest subgroup of G that contains a.

Proof.

Futhermore, any subgroup H of G containing a, must also contain all the power of a by group closure, and therefore ⟨a⟩ is the smallest subgroup of G that contains a.

We can go more into details. Let H ≤ G, Case base: 1 = g0 ∈ H. Suppose an ∈ H (H subgroup is closed) ⇒ a-1, a-n = (an)-1 ∈ H ⇒ [H is closed under multiplication] an+1 = aan, a-(n+1)=a-n-1=a-1a-n∈ H

In particular if g1, g2 ….gr ∈ G, ⟨g1, g2,…, gr⟩ = ⟨{g1, g2,…, gr}⟩ is the subgroup generated by g1, g2,…, and gr.

Examples.

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.

Examples.

Proof.

Let p ∈ ℤn p coprime to n ⇒ [By the Euclidean Algorithm] 1 = ap + bn ⇒ ap ≡ 1 (mod n) ⇒ [ap ∈ ⟨p⟩] 1 ∈ ⟨p⟩ ⇒ ℤn = ⟨p⟩∎

U8 = {1, 3, 5, 7}. Observe that 328 1, 528 1, 728 1, and therefore ⟨1⟩ = {1}, ⟨3⟩ = {1, 3}, ⟨5⟩ = {1, 5}, ⟨7⟩ = {1, 7}, U8 is not a cyclic group, U8 ≠ ⟨a⟩ for any a ∈ U8. There is no element of order 4.

Properties of Cyclic Groups

Theorem. Let G be a group, a ∈ G. If a has infinite order, then ai=aj iff (if and only if) i=j. If a has finite order n, then ⟨a⟩ = {e, a, a2,..., an-1} and ai=aj iff (if and only if) n|(i-j), n divides i-j.

Proof.

If a has infinite order ⇒ there is no such a number, n ∈ ℕ, n > 0: an = e. Therefore, ai = aj ⇒ i = j.

Let’s assume that |a| = n, we are going to prove that ⟨a⟩ = {e, a, a2,…, an-1}. Certainly, e, a, a2,…, an-1 are in ⟨a⟩. Suppose that ak ∈ ⟨a⟩ ⇒ ∃q, r ∈ ℤ: k = qn + r, 0 ≤ r < n ⇒ ak=aqnar = (an)qar = eqar = ear = ar ∈ {e, a, a2,…, an-1}, 0 ≤ r < n.

Next, let’s assume ai = aj ⇒ ai-j = e ⇒ i - j = qn + r, 0 ≤ r < n ⇒ ai-j = (an)qar = ear = ar = e, 0 ≤ r < n ⇒ Since, by definition, n is the least positive integer such that an is the identity, r = 0 ⇒ i - j = qn ⇒ n divides i-j.

Conversely, if i - j = nq ⇒ ai-j = anq = (an)q = eq = e ⇒ ai = aj.

Example: ℤ20 = {1, 2, 3,…, 19}. ⟨5⟩ = {5, 10, 15, 0}, |⟨5⟩|=4, so by this theorem 5i = 5j iff 4|(i-j).

0 = 50 = 54 = 58
5 = 51 = 55 = 59
10 = 52 = 56 = 510
15 = 53 = 57 = 511

Corollary. For any group element a, the order of a is equal to the order of the cyclic subgroup generated by a, i.e., |a| = |⟨a⟩|.

Theorem. Let G = ⟨a⟩ be a cyclic group. If a has finite order n, then so does G and |G| = n. Futhermore, if b ∈ G and |b| = n, then h is a generator for G.

Proof. Since a has cyclic order, ⟨a⟩ = {e, a, a2,···, an-1} = G and all these elements are distinct because if ak = al, let’s assume k > l ⇒ [G is a group, there are inverses] aka-l = e ⇒ ak-l = e ⇒ k-l>0 ⊥ (it contradicts |a| = n). Therefore, |G| = n.

If b ∈ G, |b| = n, by similar reasoning ⟨b⟩ = {e, b, b2, …, bn-1} and all distinct elements and therefore G = ⟨b⟩, b is a generator.

Theorem. Let G be a group with a ∈ G. Then, am = e iff |a| | m. In particular, if b = am,, then the order of b divides the order of a.

Proof.

Let |a| = n. By the division algorithm, ∃q, r ∈ ℤ: m = qn + r and 0 ≤ r < n. ar = am-qn = am(an)-q = am. Then, am = e ↭ ar = e ↭ [0 ≤ r < n, |a|=n, so by the minimality of n] r = 0 ↭ m = qn

In particular, bn = [b = am] (am)n = (an)m = em = e ⇒ [By the previous statement] |b| | n = |a|∎

The idea behind these results is that multiplication in ⟨a⟩ is essentially done by addition modulo n that is, if (i+j) mod n = k, then aiaj = ak. In other words, in the finite case, it works as addition in ℤn. Otherwise, if a has infinite order, multiplication in ⟨a⟩ is essentially done by addition. It works as addition in ℤ, that is, no modular arithmetic is needed.  

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.

If H = {e} ⇒ H = ⟨e⟩, and H is cyclic.

If H ≠ {e} ⇒ ∃g ∈ H: g ≠ e, g = an. Let m be the smallest natural number such that h = am ∈ H [Well-ordering principle. It states that every non-empty set of positive integers contains a least element.]

Let’s prove that H = ⟨h⟩ = ⟨am⟩. Let be h’ an 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 [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 it is generated by h.

Theorem. Let G be a cyclic group of finite order, G = ⟨g⟩. Then, G has exactly one subgroup of order d for each d | |G|

Proof

Let |G| = n. By assumption d | n, let h = gn/d. It is obvious that hd = (gn/d)d = gn = e.

If a ∈ ℤ, 1 ≤ a < d ⇒ [a < d ⇒ an/d < dn/d] 1 ≤ an/d < n. Thus, ha = gna/d ≠ e because 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 |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⟩ ⊆ ⟨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, then all its subgroups are necessarily cyclic ⇒ These are exactly all the subgroups of ℤ, 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 cyclic group of order n, G = ⟨a⟩. Then ak = e iff (if and only if) 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 nq≡0 (mod n)] e = ar ⇒ r = 0 because r < n and n is the smallest integer m such that am = e.

Conversely, let’s suppose n divides k ⇒ k = ns for some integer s ⇒ ak = ans = a0 = e because ns≡0 (mod n).

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.

Theorem. Let G be a cyclic group of order n and generated by a, G = ⟨a⟩. ⟨ak⟩=⟨agcd(n,k)⟩ and |⟨ak⟩| = $\frac{n}{gcd(n,k)}.$

Proof. We need to know the smallest integer m such that e = bm = akm. By the previous theorem, 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, so m needs to be n/d.

Example. Suppose |a|=24 and k=10. ⟨ak⟩=⟨agcd(n,k)⟩ = ⟨a10⟩=⟨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, |⟨5⟩|=6, |⟨9⟩|=3, |⟨11⟩|=3, |⟨13⟩|=2
  2. Let |a| = n. Then ⟨ai⟩=⟨aj⟩ iff gcd(n, i) = gcd(n, j) and |ai| = |aj| iff gcd(n, i) = gcd(n, j). Example: Let a ∈ G, |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$.
  3. Let |a|=n. Then ⟨a⟩=⟨aj⟩ iff gcd(n, j) = 1 and |a| = |aj| iff gcd(n, j) = 1. Example: Let ⟨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⟩= ⟨3⟩ = U14).
  4. An integer k ∈ ℤn is a generator of ℤn iff gcd(n, k) = 1.

As a result, the generators of ℤn are the integers r such that n/d = n, d = gcd(r, n) = 1. In other words, the generators of ℤn are the integers r that are relatively prime to n. Example: 1 and 3 are generators of ℤ4, 1 and 5 are generators of Z6, and 1, 5, 7, and 11 are the generators of ℤ12. 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 contrary to our assumption. Therefore, ∀g ∈ G, g = am for a unique m ∈ ℤ.

The map Φ: G → ℤ, Φ(am)=m is well defined, one to one, and obviously onto ℤ.

Let’s suppose the order of G is finite. am= e 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, one to one, and onto ℤn.

We claim that a0 (e), a, a2, a3,… an-1 are all distinct and comprise all elements of G.

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, and therefore a0 (e), a, a2, a3,… an-1 are all distinct.

an = e ⇒ aiaj = ak where k = i +n j ⇒ Φ(aiaj) = i +n j = Φ(ai) + Φ(aj).

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.

Corollary. For each positive divisor k of n, the set ⟨n/k⟩ is the unique subgroup of ℤn of order k.

Example: ℤ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, e}. There are four generators for the unique subgroup of ℤ24 of order 8.

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, that is, Un = Φ(n). If d is a positive divisor of n, the number of elements of order d in a cyclic group of order n is Φ(d).

Example. In ℤ24, the number of elements of order 8, Φ(8) = 4. They are ⟨3⟩=⟨9⟩=⟨15⟩=⟨21⟩ = {3, 6, 9, 12, 15, 18, 21, e}.

Theorem. Let G be cyclic, G = ⟨a⟩, |⟨a⟩|=n, then the order of any subgroup H is a divisor of n. Futhermore, for each positive divisor k of n, G has exactly one subgroup of order k, that is, ⟨ank.

Proof. G = ⟨a⟩, |⟨a⟩|=n, H subgroup. Previously, we have already demonstrated that H = ⟨h⟩ = ⟨am⟩ and m is the smallest natural number such that h = am ∈ H.

Let h’ = e = an (|⟨a⟩|=n). By the division algorithm, ∃q, r: n = mq + r where 0 ≤ r < m ⇒ an = amq+r = amqar = (am)qar = hqar ⇒ ar = anh-q ∈ H [ak and h-q∈ H], but r < m, and h = am is the smallest element in H ⇒ r = 0 ⇒ n = mq, m is a divisor of n.

Let k be any divisor of n. Let’s prove that ⟨ank⟩ is the only subgroup of order k. First, we know that ⟨ank⟩ has order $\frac{n}{d}$ where d = gcd(n/k, n) = k [k is a divisor of n, n = qk, gcd(q, qk) = q = n/k], so ⟨ank⟩ has order $\frac{n}{\frac{n}{k}}=k.$

Let H be any subgroup of order k. We have already demonstrated that H = ⟨am⟩ and m is a divisor of n ⇒ m = gcd(n, m) ⇒ k = |am|= |agcd(n,m)|=$\frac{n}{gcd(n, m)}= \frac{n}{m}$. Therefore, m=n/k and H = ⟨an/k

The Method of Repeated Squares

What is 57 mod 21 or 271321 (mod 481)?

The first step is to write the exponent in binary. Of course, every number a can be written as the sum of distinct power of 2, a = 2k1 + 2k2 + … + 2kn, e.g., 710 = 1112 and 32110= 1010000012.

The laws of exponents still work in ℤn [b≡ax (mod n), c≡ay (mod n) ⇒ bc≡ax+y (mod n),] so we can calculate a2k (mod n) in k multiplications by computing a20 (mod n), a21 (mod n), …, a2k (mod n)

57 mod 21 ≡ 54+2+1 mod 21

  1. 51 = 5 mod 21 = 5
  2. 52 = 25 ≡ 4 mod 21
  3. 54 = (52)2 ≡ [It’s time to use the previous one] 42 ≡ 16 mod 21.

Finally, let’s combine our partial results, 57 mod 21 ≡ 54+2+1 mod 21 ≡ 16·4·5 mod 21 ≡ 320 mod 21 ≡ 5 mod 21.

Analogously, but we will need a little more extra effort, 27120+26+28 ≡ 27120· 27126· 27128 (mod 481)

  1. 27120 ≡ 271 (mod 481)
  2. 27121 ≡ 73441 (mod 481) ≡ 329 (mod 481)
  3. 27122 ≡ [Using the previous result] 3292 ≡ 108241 ≡ 16 (mod 481).
  4. 27123 ≡ 162 ≡ 256 (mod 481).
  5. 27124 ≡ 2562 ≡ 120 (mod 481).
  6. 27125 ≡ 1202 ≡ 451 (mod 481).
  7. 27126 ≡ 4512 ≡ 419 (mod 481).
  8. 27127 ≡ 4192 ≡ 477 (mod 481).
  9. 27128 ≡ 4772 ≡ 16 (mod 481).

Finally, let’s combine our partial results, 27120+26+28 ≡ 27120· 27126· 27128 (mod 481) ≡ 271·419·16 ≡ 47 (mod 481).

Bitcoin donation

JustToThePoint Copyright © 2011 - 2023 Anawim. ALL RIGHTS RESERVED. Bilingual e-books, articles, and videos to help your child and your entire family succeed, develop a healthy lifestyle, and have a lot of fun.

This website uses cookies to improve your navigation experience.
By continuing, you are consenting to our use of cookies, in accordance with our Cookies Policy and Website Terms and Conditions of use.