cyclic group (thing)

A cyclic group G = ‹ a › generated by the element a of G is the set of all integral powers of a, which are a^k in multiplicative notation and ka in additive notation. If G is a group (not necessarily cyclic) and a is an element of G, then ‹ a › is the cyclic subgroup of G generated by a, denoted ‹ a › ≤ G.

The cyclic subgroup of G generated by the element a is also the intersection of all subgroups H of G that contain a. Thus, the cyclic subgroup ‹ a › generated by the element a of G is the smallest subgroup of G that contains a.

Theorem: Every subgroup of a cyclic group is cyclic.

Proof:

Let G = ‹ a › be a cyclic group and let H be a subgroup of G.
Then, H is a subset of G and so, for any element h of H, h = a^k for some integer k.
If there does not exist an integer m such that a^m ≠ 1 (where 1 denotes, of course, the identity element of G) and a^m is an element of H, then H = {1}, and H is trivially a cyclic subgroup of G.
If there does exist an integer m such that a^m ≠ 1 and a^m is an element of H, then either m < 0 or m > 0.
If m < 0, then, since H is a group it contains the inverse of a^m, (a^m)^-1 = a^-m.
a^ma^-m = 1, and if a^-m = 1, then 1 = a^ma^-m = 1a^m = a^m, which is a contradiction, and so a^-m ≠ 1, and -m > 0, since m < 0.
Therefore, there exists a positive integer m such that a^m ≠ 1 and a^m is an element of H.
Let S = { n | n is a positive integer and aⁿ ≠ 1 and aⁿ is an element of H}.
Since S is non-empty, by the well-ordering of the positive integers (natural numbers), S has a least element n₀.
‹ aⁿ⁰ › is a subgroup of H and therefore if h is an element of H, then h = a^k, where k = qn₀ + r, for some integer q and an integer r such that 0 ≤ r < n₀. (See division algorithm for proof of this)
a^qn0 = (aⁿ⁰)^q is an element of ‹ aⁿ⁰ ›, which is a group, and so its inverse (a^qn0)^-1 = a^-qn0 is an element of
‹ aⁿ⁰ › and also of H (since ‹ aⁿ⁰ › is a subgroup of H).
H is a group, and so is closed its group operation, which is denoted here by juxtapostion.
Therefore, a^ka^-qn0 = a^{qn0 + r}a^-qn0 = a^r is an element of H.
n₀ is the least positive integer such that aⁿ⁰ ≠ 1 and r < n₀, and so a^r = 1.
Therefore, a^k = a^{qn0 + r} = a^qn0a^r = a^qn01 = a^qn0 and a^k is an element of ‹ aⁿ⁰ ›
Therefore, H is a subset of ‹ aⁿ⁰ ›, which is itself a subset of H, and so H = ‹ aⁿ⁰ › and H is cyclic. (QED)

The following are a few important results concerning finite cyclic groups.

Theorem: If G = ‹ a › is a cyclic group of order n and 1 ≤ k < n, then

A. The order of a^k, denoted o(a^k), which is the least positive integer m such that (a^k)^m = 1,
is n/(n,k), where (n,k) is the greatest common divisor of n and k.
In particular, a^k generates G if and only if (n,k) = 1, i.e., n and k are relatively prime.

Proof:

Let d = (n,k). Since d is the greatest common divisor of n and k, there exist integers x and y such that
d = kx + ny. (See greatest common divisor for proof of this.)
Then, a^d = a^{kx + ny} = a^kxa^ny
Since G = ‹ a › is a cyclic group of order n, aⁿ = 1, and a^ny = 1^y = 1.
Therefore, a^d = a^{kx + ny} = a^kxa^ny = a^kx1 = a^kx = (a^k)^x and a^d ε ‹ a^k › , which implies that ‹ a^d › is a subset of ‹ a^k ›
d divides k, so there exists an integer m such that m = k/d and a^k = (a^d)^k/d = (a^d)^m and a^k ε ‹ a^d ›,
which implies ‹ a^k › is a subset of ‹ a^d ›
Since ‹ a^k › is a subset of ‹ a^d › and ‹ a^d › is a subset of ‹ a^k ›, ‹ a^d › = ‹ a^k ›
Therefore, o(a^k) = o(a^d), but d divides n and so the least integer m such that dm = n is n/d.
Therefore, o(a^k) = n/d = n/(n,k) (QED).
The second part of the claim follows easily. If G = ‹ a › is a cyclic group of order n, then o(a^k) = n if and only if (n,k) = 1, which is just to state that ‹ a^k › = G.

B. If d divides n, then o(a^k) = d if and only if k = r(n/d) and (r,d) = 1.

Proof:

From, part A we have that o(a^k) = n/(n,k).
Let d = n / (n,k). Then d(n,k) = (dn,dk) = n.
Let r = k / (n,k). Then nr = n(k / (n,k)) = k(n/ (n,k)) = dk.
Therefore, (dn,dk) = (dn, nr) = n and n = n(d,r), which holds if and only if (d,r) = 1. (QED)

C. Each subgroup H of G is of the form ‹ a^d ›, where d is a uniquely determined positive divisor of n.

Proof:

Let H be a subgroup of G and c be the order of H. Then, by Lagrange's theorem for finite groups, c divides n.
From part B we have that o(a^k) = c if and only if k = r(n/c) and (r,c) = 1, which is just to state that ‹ a^k › = H if and only if k = r(n/c) and (r,c) = 1
(1,c) = 1 and so if k = n/c then ‹ a^k › = H and n/(n/c) = c, so k obviously divides n.
Now, suppose ‹ a^k › = H and k divides n and k ≠ n/c.
This means that k = r(n/c) and (r,c) = 1 and r ≠ 1 and so r does not divide c. k, however, does divide n and so there exists an integer m such that km = n and k = n/m.
k = n/m = r(n/c). so 1/m = r/c and m = c/r contradicting the fact that r does not divide c.
Therefore k = n/c is the only divisor of n such that ‹ a^k › = H. (QED)

D. For each divisor d of n, the group G has exactly one subgroup H_d of order d and the number of elements of order d is equal to the number of positive integers less than d that are relatively prime to d and all of these elements lie in H_d.

Proof:

It follows from B that if G is a cyclic group of order n, then for each divisor d of n each and each 1 ≤ k < n,
a^k generates a subgroup H of G if and only if k = r(n/d) and r and d are relatively prime. By Lagrange's theorem, the order of each subgroup H of G must divide the order of G, i.e., n. Therefore, there are precisely φ(d) generators for every subgroup H of G of order d., where φ(d) is the number of positive integers less than or equal to d that are relatively prime to d. Now, suppose there is another subgroup ‹ b › of G of order d. Being cyclic, ‹ b › has an element of order d, which is necessarily of the form b^r(n/d) where (r,d) = 1. This element, however, is also in H_d = ‹ a^(n/d) › and is a generator of this subgroup. Therefore, ‹ b › = H_d. (QED)

E. For each positive integer n and each divisor d of n, Σ φ(d) = n, where φ is the Euler Phi Function.

Proof: Let G = ‹ a › be a cyclic group of order n. For each divisor d of n, let G_d = { b ε G | o(b) = d }. Again, by Lagrange's theorem, the order of each element must divide the order of G, and so each element b of G is in G_d for some divisor d of n. Furthermore, the set of all G_d forms a partition of the group G, given that the order of any element of G is unique. Therefore, the sum of the cardinalities of each G_d is n, but from B, for each d, the cardinality of G_d is φ(d). This just means that for each divisor d of n, Σ φ(d) = n. (QED)