display | more...
A cyclic group is a mathematical group which is generated by one of its elements, i.e. every element x can be written as x = ak, where a is the generator and k is an integer.

Cyclic groups are important in number theory because any cyclic group of infinite order is isomorphic to the group formed by the set of all integers and addition as the operation, and any finite cyclic group of order n is isomorphic to the set of all integers modulo n, using addition followed by taking the modulo as the operation.

A cyclic group G = ‹ a › generated by the element a of G is the set of all integral powers of a, which are ak 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 = ak for some integer k.
If there does not exist an integer m such that am ≠ 1 (where 1 denotes, of course, the identity element of G) and am 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 am ≠ 1 and am 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 am, (am)-1 = a-m.
ama-m = 1, and if a-m = 1, then 1 = ama-m = 1am = am, which is a contradiction, and so a-m ≠ 1, and -m > 0, since m < 0.
Therefore, there exists a positive integer m such that am ≠ 1 and am is an element of H.
Let S = { n | n is a positive integer and an ≠ 1 and an 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 n0.
an0 › is a subgroup of H and therefore if h is an element of H, then h = ak, where k = qn0 + r, for some integer q and an integer r such that 0 ≤ r < n0. (See division algorithm for proof of this)
aqn0 = (an0)q is an element of ‹ an0 ›, which is a group, and so its inverse (aqn0)-1 = a-qn0 is an element of
an0 › and also of H (since ‹ an0 › is a subgroup of H).
H is a group, and so is closed its group operation, which is denoted here by juxtapostion.
Therefore, aka-qn0 = aqn0 + ra-qn0 = ar is an element of H.
n0 is the least positive integer such that an0 ≠ 1 and r < n0, and so ar = 1.
Therefore, ak = aqn0 + r = aqn0ar = aqn01 = aqn0 and ak is an element of ‹ an0
Therefore, H is a subset of ‹ an0 ›, which is itself a subset of H, and so H = ‹ an0 › 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 ak, denoted o(ak), which is the least positive integer m such that (ak)m = 1,
is n/(n,k), where (n,k) is the greatest common divisor of n and k.
In particular, ak 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, ad = akx + ny = akxany
Since G = ‹ a › is a cyclic group of order n, an = 1, and any = 1y = 1.
Therefore, ad = akx + ny = akxany = akx1 = akx = (ak)x and ad ε ‹ ak › , which implies that ‹ ad › is a subset of ‹ ak
d divides k, so there exists an integer m such that m = k/d and ak = (ad)k/d = (ad)m and ak ε ‹ ad ›,
which implies ‹ ak › is a subset of ‹ ad
Since ‹ ak › is a subset of ‹ ad › and ‹ ad › is a subset of ‹ ak ›, ‹ ad › = ‹ ak
Therefore, o(ak) = o(ad), but d divides n and so the least integer m such that dm = n is n/d.
Therefore, o(ak) = 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(ak) = n if and only if (n,k) = 1, which is just to state that ‹ ak › = G.

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

Proof:

From, part A we have that o(ak) = 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 ‹ ad ›, 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(ak) = c if and only if k = r(n/c) and (r,c) = 1, which is just to state that ‹ ak › = H if and only if k = r(n/c) and (r,c) = 1
(1,c) = 1 and so if k = n/c then ‹ ak › = H and n/(n/c) = c, so k obviously divides n.
Now, suppose ‹ ak › = 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 ‹ ak › = H. (QED)

D. For each divisor d of n, the group G has exactly one subgroup Hd 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 Hd.

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,
ak 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 br(n/d) where (r,d) = 1. This element, however, is also in Hd = ‹ a(n/d) › and is a generator of this subgroup. Therefore, ‹ b › = Hd. (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 Gd = { 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 Gd for some divisor d of n. Furthermore, the set of all Gd 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 Gd is n, but from B, for each d, the cardinality of Gd is φ(d). This just means that for each divisor d of n, Σ φ(d) = n. (QED)

Log in or register to write something here or to contact authors.