Definition. Let G be a group and a be any element in G (a ∈ G). Then, the set ⟨a⟩={a^{n} | 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, a^{2},…, a^{n-1}}, where e is the identity element, a^{i}=a^{j} whenever i≡j (mod n); in particular a^{n} = a^{0} = e, and a^{-1} = a^{n-1}. In other words, the order of a is the smallest positive integer n such that a^{n} = 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 = g^{0} ∈ H. Suppose a^{n} ∈ H (H subgroup is closed) ⇒ a^{-1}, a^{-n} = (a^{n})^{-1} ∈ H ⇒ [H is closed under multiplication] a^{n+1} = aa^{n}, a^{-(n+1)}=a^{-n-1}=a^{-1}a^{-n}∈ H
In particular if g_{1}, g_{2} ….g_{r} ∈ G, ⟨g_{1}, g_{2},…, g_{r}⟩ = ⟨{g_{1}, g_{2},…, g_{r}}⟩ is the subgroup generated by g_{1}, g_{2},…, and g_{r}.
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 a^{n}.
Consider (ℚ^{*}, ·), let H be the set of all powers of 2, H = {2^{n} | 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⟩ = {a^{n} | 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⟩∎
U_{8} = {1, 3, 5, 7}. Observe that 3^{2} ≡_{8} 1, 5^{2} ≡_{8} 1, 7^{2} ≡_{8} 1, and therefore ⟨1⟩ = {1}, ⟨3⟩ = {1, 3}, ⟨5⟩ = {1, 5}, ⟨7⟩ = {1, 7}, U_{8} is not a cyclic group, U_{8} ≠ ⟨a⟩ for any a ∈ U_{8}. There is no element of order 4.
Theorem. Let G be a group, a ∈ G. If a has infinite order, then a^{i}=a^{j} iff (if and only if) i=j. If a has finite order n, then ⟨a⟩ = {e, a, a^{2},..., a^{n-1}} and a^{i}=a^{j} 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: a^{n} = e. Therefore, a^{i} = a^{j} ⇒ i = j.
Let’s assume that |a| = n, we are going to prove that ⟨a⟩ = {e, a, a^{2},…, a^{n-1}}. Certainly, e, a, a^{2},…, a^{n-1} are in ⟨a⟩. Suppose that a^{k} ∈ ⟨a⟩ ⇒ ∃q, r ∈ ℤ: k = qn + r, 0 ≤ r < n ⇒ a^{k}=a^{qn}a^{r} = (a^{n})^{q}a^{r} = e^{q}a^{r} = ea^{r} = a^{r} ∈ {e, a, a^{2},…, a^{n-1}}, 0 ≤ r < n.
Next, let’s assume a^{i} = a^{j} ⇒ a^{i-j} = e ⇒ i - j = qn + r, 0 ≤ r < n ⇒ a^{i-j} = (a^{n})^{q}a^{r} = ea^{r} = a^{r} = e, 0 ≤ r < n ⇒ Since, by definition, n is the least positive integer such that a^{n} is the identity, r = 0 ⇒ i - j = qn ⇒ n divides i-j.
Conversely, if i - j = nq ⇒ a^{i-j} = a^{nq} = (a^{n})^{q} = e^{q} = e ⇒ a^{i} = a^{j}.
Example: ℤ_{20} = {1, 2, 3,…, 19}. ⟨5⟩ = {5, 10, 15, 0}, |⟨5⟩|=4, so by this theorem 5^{i} = 5^{j} iff 4|(i-j).
0 = 5^{0} = 5^{4} = 5^{8}…
5 = 5^{1} = 5^{5} = 5^{9}…
10 = 5^{2} = 5^{6} = 5^{10}…
15 = 5^{3} = 5^{7} = 5^{11}…
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, a^{2},···, a^{n-1}} = G and all these elements are distinct because if a^{k} = a^{l}, let’s assume k > l ⇒ [G is a group, there are inverses] a^{k}a^{-l} = e ⇒ a^{k-l} = e ⇒ k-l>0 ⊥ (it contradicts |a| = n). Therefore, |G| = n.
If b ∈ G, |b| = n, by similar reasoning ⟨b⟩ = {e, b, b^{2}, …, b^{n-1}} and all distinct elements and therefore G = ⟨b⟩, b is a generator.
Theorem. Let G be a group with a ∈ G. Then, a^{m} = e iff |a| | m. In particular, if b = a^{m,}, 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. a^{r} = a^{m-qn} = a^{m}(a^{n})^{-q} = a^{m}. Then, a^{m} = e ↭ a^{r} = e ↭ [0 ≤ r < n, |a|=n, so by the minimality of n] r = 0 ↭ m = qn
In particular, b^{n} = [b = a^{m}] (a^{m})^{n} = (a^{n})^{m} = e^{m} = 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 a^{i}a^{j} = a^{k}. 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 = a^{m}, h = a^{n} for some m, n ∈ Z ⇒ gh = a^{m+n} = a^{n+m} = a^{n}a^{m} = 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 = a^{n}. Let m be the smallest natural number such that h = a^{m} ∈ H [Well-ordering principle. It states that every non-empty set of positive integers contains a least element.]
Let’s prove that H = ⟨h⟩ = ⟨a^{m}⟩. Let be h’ an element of H, h ∈ H ⇒ h’ = a^{k}.
By the division algorithm, ∃q, r: k = mq + r where 0 ≤ r < m ⇒ a^{k} = a^{mq+r} = a^{mq}a^{r} = (a^{m})^{q}a^{r} = h^{q}a^{r} ⇒ a^{r} = a^{k}h^{-q} ∈ H [a^{k} and h^{-q}∈ H], but r < m, and h = a^{m} is the smallest element in H ⇒ r = 0 ⇒ k = mq, h’ = a^{k} = a^{mq} = h^{q}, 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 = g^{n/d}. It is obvious that h^{d} = (g^{n/d})^{d} = g^{n} = e.
If a ∈ ℤ, 1 ≤ a < d ⇒ [a < d ⇒ an/d < dn/d] 1 ≤ an/d < n. Thus, h^{a} = g^{na/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 = g^{m}. g^{dm} = (g^{m})^{d} = k^{d} = e ⇒ [g^{a} =e ↭ |g| | a] n | dm ⇒ ∃l ∈ ℤ: nl = dm ⇒ (n/d)l = m ⇒ k = g^{m} = (g^{n/d})^{l} = h^{l} ∈ ⟨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 a^{k} = e iff (if and only if) n divides k.
Proof.
Let’s suppose that a^{k} = e. By the division algorithm, k = nq +r, where 0 ≤ r < n ⇒ a^{k} = a^{nq+r} = a^{nq}a^{r} ⇒ [a^{k} = e, a^{nq}=a^{0}=e because nq≡0 (mod n)] e = a^{r} ⇒ r = 0 because r < n and n is the smallest integer m such that a^{m} = e.
Conversely, let’s suppose n divides k ⇒ k = ns for some integer s ⇒ a^{k} = a^{ns} = a^{0} = e because ns≡0 (mod n).
Exercise: Suppose G is cyclic, a ∈ G, a is an element of order n, and a^{24}=e. What are the possibilities of n?
a^{24}=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⟩. ⟨a^{k}⟩=⟨a^{gcd(n,k)}⟩ and |⟨a^{k}⟩| = $\frac{n}{gcd(n,k)}.$
Proof. We need to know the smallest integer m such that e = b^{m} = a^{km}. 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. ⟨a^{k}⟩=⟨a^{gcd(n,k)}⟩ = ⟨a^{10}⟩=⟨a^{gcd(24, 10)}⟩ = ⟨a^{2}⟩ = {a^{2}, a^{4}, a^{6}, … a^{22}, a^{0}} and |⟨a^{10}⟩| = $\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 Z_{6}, 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, a^{m} ≠ e. We claim that ∀h, k ∈ ℤ, a^{h} ≠ a^{k}. Suppose a^{h} = a^{k} and h > k ⇒ a^{h}a^{-k} = a^{h-k} = e contrary to our assumption. Therefore, ∀g ∈ G, g = a^{m} for a unique m ∈ ℤ.
The map Φ: G → ℤ, Φ(a^{m})=m is well defined, one to one, and obviously onto ℤ.
Let’s suppose the order of G is finite. a^{m}= e m ∈ ℤ, m > 0. Let n be the smallest positive integer such that a^{n} = e. The map Φ: G → ℤ^{n}, given by Φ(a^{i})=i, for i=0, 1, 2,…n-1 is well-defined, one to one, and onto ℤ_{n}.
We claim that a^{0} (e), a, a^{2}, a^{3},… a^{n-1} are all distinct and comprise all elements of G.
s = nq + r, 0 ≤ r < n, a^{s} = a^{nq}a^{r} = (a^{n})^{q}a^{r} =e^{q}a^{r} = a^{r}, a^{r-s} = e. If 0 < s < r < n, a^{r-s} = e and 0 < r-s < n so it contradicts our choice of n, and therefore a^{0} (e), a, a^{2}, a^{3},… a^{n-1} are all distinct.
a^{n} = e ⇒ a^{i}a^{j} = a^{k} where k = i +_{n} j ⇒ Φ(a^{i}a^{j}) = i +_{n} j = Φ(a^{i}) + Φ(a^{j}).
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, ⟨a^{n/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, U_{n} = Φ(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, ⟨a^{n⁄k}⟩.
Proof. G = ⟨a⟩, |⟨a⟩|=n, H subgroup. Previously, we have already demonstrated that H = ⟨h⟩ = ⟨a^{m}⟩ and m is the smallest natural number such that h = a^{m} ∈ H.
Let h’ = e = a^{n} (|⟨a⟩|=n). By the division algorithm, ∃q, r: n = mq + r where 0 ≤ r < m ⇒ a^{n} = a^{mq+r} = a^{mq}a^{r} = (a^{m})^{q}a^{r} = h^{q}a^{r} ⇒ a^{r} = a^{n}h^{-q} ∈ H [a^{k} and h^{-q}∈ H], but r < m, and h = a^{m} 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 ⟨a^{n⁄k}⟩ is the only subgroup of order k. First, we know that ⟨a^{n⁄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 ⟨a^{n⁄k}⟩ has order $\frac{n}{\frac{n}{k}}=k.$
Let H be any subgroup of order k. We have already demonstrated that H = ⟨a^{m}⟩ and m is a divisor of n ⇒ m = gcd(n, m) ⇒ k = |a^{m}|= |a^{gcd(n,m)}|=$\frac{n}{gcd(n, m)}= \frac{n}{m}$. Therefore, m=n/k and H = ⟨a^{n/k}⟩
What is 5^{7} mod 21 or 271^{321} (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 = 2^{k1} + 2^{k2} + … + 2^{kn}, e.g., 7_{10} = 111_{2} and 321_{10}= 101000001_{2}.
The laws of exponents still work in ℤ_{n} [b≡a^{x} (mod n), c≡a^{y} (mod n) ⇒ bc≡a^{x+y} (mod n),] so we can calculate a^{2k} (mod n) in k multiplications by computing a^{20} (mod n), a^{21} (mod n), …, a^{2k} (mod n)
5^{7} mod 21 ≡ 5^{4+2+1} mod 21
Finally, let’s combine our partial results, 5^{7} mod 21 ≡ 5^{4+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, 271^{20+26+28} ≡ 271^{20}· 271^{26}· 271^{28} (mod 481)
Finally, let’s combine our partial results, 271^{20+26+28} ≡ 271^{20}· 271^{26}· 271^{28} (mod 481) ≡ 271·419·16 ≡ 47 (mod 481).