- A cyclic group generated by g is
- Induction shows:
A cyclic group of order n is isomorphic to the integers modulo n with addition
Let Cm be a cyclic group of order m generated by g with
Let be the group of integers modulo m with addition
- Cm is isomorphic to
Let n be the minimal positive integer such that gn = e
Proof of Lemma
- Let i > j. Let i - j = sn + r where 0 ≤ r < n and s,r,n are all integers.
||as i - j = sn + r, and gn = e
||as n is the minimal positive integer such that gn = e
- and 0 ≤ r < n
||0. and 7.
- 0. Define
- Lemma shows f is well defined (only has one output for each input).
- f is homomorphism:
- f is injective by lemma
- f is surjective as both and has m elements and m is injective
In the previous section about subgroups we saw that if is a group with , then the set of powers of , constituted a subgroup of , called the cyclic subgroup generated by . In this section, we will generalize this concept, and in the process, obtain an important family of groups which is very rich in structure.
Definition 1: Let be a group with an element such that . Then is called a cyclic group, and is called a generator of . Alternatively, is said to generate . If there exists an integer such that , and is the smallest positive such integer, is denoted , the cyclic group of order . If no such integer exists, is denoted , the infinite cyclic group.
The infinite cyclic group can also be denoted , the free group with one generator. This is foreshadowing for a future section and can be ignored for now.
Theorem 2: Any cyclic group is abelian.
Proof: Let be a cyclic group with generator . Then if , then and for some . To show commutativity, observe that and we are done. ∎
Theorem 3: Any subgroup of a cyclic group is cyclic.
Proof: Let be a cyclic group with generator , and let . Since , in paticular every element of equals for some . We claim that if the lowest positive integer such that , then . To see this, let . Then and for unique . Since is a subgroup and , we must have . Now, assume that . Then contradicts our assumption that is the least positive integer such that . Therefore, . Consequently, only if , and and is cyclic, as was to be shown. ∎
As the alert reader will have noticed, the preceeding proof invoked the notion of division with remainder which should be familiar from number theory. Our treatment of cyclic groups will have close ties with notions from number theory. This is no coincidence, as the next few statements will show. Indeed, an alternative title for this section could have been "Modular arithmetic and integer ideals". The notion of an ideal may not yet be familiar to the reader, who is asked to wait patiently until the chapter about rings.
Theorem 4: Let with addition defined modulo . That is , where . We denote this operation by . Then is a cyclic group.
Proof: We must first show that is a group, then find a generator. We verify the group axioms. Associativity is inherited from the integers. The element is an identity element with respect to . An inverse of is an element such that . Thus . Then, , and so , and is a group. Now, since , generates and so is cyclic. ∎
Unless we explicitly state otherwise, by we will always refer to the cyclic group . Since the argument for the generator of can be made valid for any integer , this shows that also is cyclic with the generator .
Theorem 5: An element is a generator if and only if .
Proof: We will need the following theorem from number theory: If are integers, then there exists integers such that , if and only if . We will not prove this here. A proof can be found in the number theory section.
For the right implication, assume that . Then for all , for some integer . In paticular, there exists an integer such that . This implies that there exists another integer such that . By the above-mentioned theorem from number theory, we then have . For the left implication, assume . Then there exists integers such that , implying that in . Since generates , it must be true that is also a generator, proving the theorem. ∎
We can generalize Theorem 5 a bit by looking at the orders of the elements in cyclic groups.
Theorem 6: Let . Then, .
Proof: Recall that the order of is defined as the lowest positive integer such that in . Since is cyclic, there exists an integer such that is minimal and positive. This is the definition of the least common multiple; . Recall from number theory that . Thus, , as was to be proven. ∎
Theorem 7: Every subgroup of is of the form .
Proof: The fact that any subgroup of is cyclic follows from Theorem 3. Therefore, let generate . Then we see immediately that . ∎
Theorem 8: Let be fixed, and let . Then is a subgroup of generated by .
Proof: We msut first show that is a subgroup. This is immediate since . From the proof of Theorem 3, we see that any subgroup of is generated by its lowest positive element. It is a theorem of number theory that the lowest positive integer such that for fixed integers and equals the greatest common divisor of and or . Thus generates . ∎
Theorem 9: Let and be subgroups of . Then is the subgroup generated by .
Proof: The fact that is a subgroup is obvious since and are subgroups. To find a generator of , we must find its lowest positive element. That is, the lowest positive integer such that is both a multiple of and of . This is the definition of the least common multiple of and , or , and the result follows. ∎
It should be obvious by now that and , and and are the same groups. This will be made precise in a later section but can be visualized by denoting any generator of or by .
We will have more to say about cyclic groups later, when we have more tools at our disposal.