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.
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.
Notation: a+b is used instead of a·b, 0 instead of e, -a instead of a-1, na instead of an.
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⟩∎
U8 = {1, 3, 5, 7}. Observe that 32 ≡8 1, 52 ≡8 1, 72 ≡8 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.
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:
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).
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, ⟨an⁄k⟩.
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 ⟨an⁄k⟩ is the only subgroup of order k. First, we know that ⟨an⁄k⟩ 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 ⟨an⁄k⟩ 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⟩
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
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)
Finally, let’s combine our partial results, 27120+26+28 ≡ 27120· 27126· 27128 (mod 481) ≡ 271·419·16 ≡ 47 (mod 481).