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

• a0 = e, so the identity is in ⟨a⟩.
• If g and h ∈ ⟨a⟩ ⇒ g = am, h = an for some m, n ∈ Z ⇒ gh = am+n, g-1 = a-n where m+n and -n are obviously integers, so gh and g-1∈ ⟨a⟩.

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.

• 2Z and 3Z are both infinite cyclic groups generated by 2 and 3 respectively. Futhermore, ⟨4, 2⟩ = ⟨2⟩ = 2ℤ = {2n | n ∈ ℤ} = {…, -2, 0, 2, 4, 6, ···} ≤ ℚ.

• Let (ℤ, +), n ∈ ℤ, nℤ = {r·n | r ∈ ℤ} = ⟨n⟩ = ⟨-n⟩ is a cyclic subgroup of ℤ for all integers n.

• Consider (ℚ*, ·), let H be the set of all powers of 2, H = {2n | n ∈ ℤ} = {···, 1/2, 1, 2, 4, 8,···}. H = ⟨2⟩ ≤ ℚ*

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.

• (ℤ, +) is cyclic. It is generated by 1 and -1, ⟨1⟩ =⟨-1⟩ = ℤ. Therefore, ℤ is an infinite cyclic group with two generators, 1 and -1.

• n = {[0], [1], …, [n-1]} is also cyclic. It is generated by [1]. Consider ℤn under addition. Then, mℤn = ⟨m⟩ = {km | k ∈ ℤn} is a cyclic subgroup of ℤn for all congruence classes m. 1 and n-1 are always generators, but there can be more.n = 1ℤn = ⟨1⟩ = ⟨n-1⟩.

Abusing notation, we refer m instead of [m], that is, just using the representatives of their equivalent classes.

• In ℤ6=$\frac{ℤ}{6ℤ}$, ⟨0⟩ = {0}, ⟨1⟩ = ⟨5⟩ = $\frac{ℤ}{6ℤ}$. ⟨2⟩ = ⟨4⟩ = {0, 2, 4} and ⟨3⟩ = {0, 3} are nontrivial proper subgroups of $\frac{ℤ}{6ℤ}$. To sum up, 2ℤ6 = {0, 2, 4} = ⟨2⟩ = ⟨4⟩ ≤ ℤ6.

• 5 = ⟨1⟩ = ⟨2⟩ = ⟨3⟩ = ⟨4⟩. Every number is a generator except the identity. The generators are all the elements of ℤn which are coprime p to n.

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⟩∎

• The multiplicative group of integers modulo n U10 = {1, 3, 7, 9} (Figure 1.a.) is a cyclic group, 3 and 7 are generators. U10 = {30, 31, 33, 32} = ⟨3⟩ = ⟨7⟩. U9 = {1, 2, 4, 5, 7, 8} is cyclic of order 6 generated by the element 2. U9 = ⟨2⟩ = {20 = 1, 21 = 2, 22 = 4, 23 = 8, 24 = 16 ≡9 7, 25 = 32 ≡9 5} and 26 = 64 ≡9 1. U14 = {1, 3, 5, 9, 11, 13} = ⟨3⟩ = ⟨5⟩. U17 = {1, 2, 3, 4, 5, . . . , 16} is cyclic of order 16 generated by the element 3.

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.

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

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