Exploration of cyclic groups
This is a survey article related to:cyclic group
View other survey articles about cyclic group
This survey article explores cyclic groups from a number of viewpoints, including their occurrence as quotients of the group of integers, modular arithmetic, their role as subgroups in any group.
Modular arithmetic and the role of cyclic groups
Arithmetic modulo is addition of integers in the ordinary fashion, except that we set to be equal to zero. Intuitively, every time we reach , we wrap back to zero. Here are some examples.
1s digit arithmetic
While adding positive integers, we know that the last digit of the sum depends only on the last digits of the numbers being added. So, if one number has a last digit of 5 and another has a last digit of 7, the last digit of the sum is 2 (because 5 + 7 = 12, giving 2 in the last digit and a carry of 1). Thus, we can look at an arithmetic of 1s digit addition: the numbers in this arithmetic are 0,1,2,3,4,5,6,7,8,9, and the addition rule is: add the digits, and take the last digit (1s digit) of the sum. This gives an Abelian group under addition, with:
- The identity element being 0.
- The additive inverse of 0, is 0, and the additive inverse of a nonzero digit is the digit that'd ordinarily be written as
Another way of formulating this is that we're adding numbers, but we only care about the remainder mod 10.
The group that we construct this way is the cyclic group of order 10, or the group of integers mod 10. It is denoted as , or .
Time: Clocks, calendars
If you go round once, you're back to where you started.
Seven days a week, twelve hours a clock, twenty-four hours a day
There are twelve hours on the wall-clock. The twelve hours are denoted by the positive integers 1,2,3,4,5,6,7,8,9,10,11,12. These denote hour positions.
Suppose we start the hour hand pointing at 12. Moving the hour hand forward by 2 hours and then moving it forward by 3 hours moves the hour hand forward by 5 hours, so that it points at 5. More generally, we expect that if we move the hour hand forward by hours and then move it forward by hours, it has moved forward by hours, so it points at . However, if is bigger than 12, then we wrap around the clock once, so we effectively reach . Thus, moving the hour hand forward by 7 and then moving it forward by 8 makes it point to hours.
We can describe this by an arithmetic of addition, where the set of numbers is 0,1,2,3,4,5,6,7,8,9,10,11. To add two numbers here, we add them as integers. If the ordinary sum is less than 12, then that's the sum we want. If the ordinary sum is at least 12, then we subtract 1 to get the desired sum.
This is the arithmetic of addition mod 12.
Under this addition, the numbers 0,1,2,3,4,5,6,7,8,9,10,11 form an Abelian group. The associativity of addition is clear from the definition: the order in which one parenthesizes the operations of moving the hour hand forward, doesn't matter. Commutativity is also clear: what order you do the two operations doesn't matter. The identity operation is doing nothing: moving the hour hand forward by zero hours. As for inverses, if you move the hour hand forward by hours, then moving it forward by hours does the trick of reversing the operation.
This Abelian group is termed the cyclic group of order 12, denoted or or .
A similar phenomenon can be seen in days of the week. Going forward by 2 days and then going forward by 3 days, has the effect of going forward by days of the week. But going forward by 3 days and then 4 days gets one back to the same day of the week. Thus, the addition here is modulo 7, and the arithmetic of addition again gives an Abelian group.
Some other examples:
- There are 60 minutes in an hour. The operations of moving the minute hand forward, then, form a cyclic group of order 60.
- There are 24 hours in a day. If we're working with a 24-hour clock, the operations of moving the hour hand forward, form a cyclic group of order 24.
- There are 12 notes in an octave. The operations of transposing the notes, i.e., moving them up on the scale, gives a cyclic group of order 12.
Why have wrap-arounds and modular arithmetic?
Wrap-around and modular arithmetic is good for a number of reasons. In some cases, it is forced upon us by nature. For instance, the sun rises once a day, so we need a way to wrap around and get back to where we started once a day. Next, we divide the day into convenient intervals (like hours). The number of intervals that we use (which is, in this case, 24) tells us what size of cyclic group we get.
This is natural for time intervals because of the natural time periodicity of the motions of heavenly bodies: for instance, the earth rotates once around its axis every day, and revolves once around the sun every year. However, the choice of how many intervals to divide it into is arbitrary and based on our convenience rather than for any intrinsic reason.
In the case of music, both the natural periodicity of music and the choice of dividing into 12 parts are natural in some sense. Further information: cyclic groups in music
Modular arithmetic is the study of cyclic groups: groups that we obtain from the integers by wrapping some integer to zero. corresponds to days of the week, corresponds to minutes in an hour, corresponds to hours in a day, and so on. Modular arithmetic seeks to develop a general theory to study cyclic groups modulo for different .
The general description for integers modulo
The cyclic group of order ( is termed the order of the group, and also called the modulus or the period of addition) is described as follows:
- Its elements are the integers
- The sum of two elements and is their usual integer sum if , and is if
- The identity element for addition is 0
- The inverse of 0 is 0, and the inverse of is for other
A somewhat better description
Though the above is the easiest way to describe the cyclic group, the following description is somewhat better conceptually. Here, we think of the cyclic group as the set of all integers, except that we declare two integers to be equal if and only if they differ by a multiple of . This is saying that you could move the hour hand forward by hours, but moving it forward by 1000 hours is equivalent to moving it forward by 4 hours (because 1000 - 4 is a multiple of 12).
In the language of sets and equivalence relations, we're taking the set of all integers, and introducing an equivalence relation on the set, where two integers are equivalent if their difference is a multiple of . In other words, two integers are equivalent if they leave the same remainder modulo . This equivalence relation is termed being congruent modulo . In symbols, we write:
if and are congruent mod .
The relation of being congruent mod is preserved by addition, i.e., if:
Thus, the cyclic group mod that we have is a group whose elements are the equivalence classes. We're adding equivalence classes.
What we effectively did in the previous description was to simply replace each equivalence class by the unique element in that class among : the remainder there.
Cyclic group in terms of generators
The cyclic groups occurring in modular arithmetic are characterized by the presence of a generator or a cyclic element: every element of the group is obtained by repeating this element. In the group , i.e., the cyclic group of order , is a generator. Every element of the group can be written in the form . So, for instance, in the cyclic group mod , the element can be written as , It can also be written as .
However, 1 is not the only possible element that can play the role of generator. There are other elements that could be generators. Here's an example. In the cyclic group of integers mod 3, the element 2 is a generator. That's because every element of the group is obtained as a multiple of 2 mod 3:
Similarly, in the cyclic group of integers mod 5, the element 3 is a generator, because:
On the other hand, in the cyclic group of integers mod 6, the element 4 is not a generator. To see this, consider the multiples of 4, i.e., the elements obtained by adding 4 to itself repeatedly:
Clearly, the multiples of 4 don't cover all the elements 0,1,2,3,4,5. Thus, 4 is not a cyclic element.
A little thought reveals that in the group of integers mod , an element is a cyclic element if and only if and are relatively prime. This is based on a general fact that given two relatively prime integers and , there exist integers and such that .
Cyclic groups in the abstract sense
We've so far viewed cyclic groups as groups of integers mod , for some . We also noted that any such group is generated by a single element, namely, the element 1. This is what defines cyclic groups abstractly:
A cyclic group is a group generated by one element, i.e., there exists an element in the group such that no proper subgroup contains the element.
If a group is generated by one element , then there are two possibilities.
- There exists a positive integer such that is the identity element. In that case, the group has only finitely many elements: . Further, for any , where . This group behaves exactly like the group of integers mod , where we identify an integer mod , with the element . (in technical parlance, the groups are isomorphic).
- There is no positive integer for which is the identity element. In that case, the group has infinitely many elements, and for . This group is the same as the ordinary group of integers, where we identify with . (in technical parlance, the groups are isomorphic).
In other words, cyclic groups don't just occur in modular arithmetic, they occur inside any group, and can be made to contain any element. In fact, every group is a union of cyclic subgroups: we just take the cyclic subgroups generated by all the elements.
Finding multiplicative cyclic groups
Here's another example of a cyclic group: a multiplicative one. Namely, this time we look at the nonzero integers modulo 5, under multiplication. In this group, we multiply two integers and then take the remainder mod 5.
It's not immediately clear that this set under multiplication forms a group, and it's even less clear that this is a cyclic group. It's also not clear what a generator for this group should be. However, a little playing around shows that the group is cyclic with generator 2:
Hence, the group of nonzero integers mod 5, under multiplication, is just like the group of integers mod 4, under addition.
The following further facts are true:
- For any prime number , the nonzero congruence class mod , form a cyclic group of order . There isn't any known algorithm to find a generator for this cyclic group.
- For any prime power , where , the congruence classes of those elements that are relatively prime to , form a cyclic group of order .
- In general, for any integer , the congruence classes of those elements that are relatively prime to , form a group under multiplication, but this group is not necessarily cyclic.
Finding other cyclic groups
The multiplicative cyclic groups give an example of a cyclic group where the group operation is conventionally treated as multiplication. There are other cyclic groups, where again the operations aren't usually thought of in terms of adding numbers. For instance, consider the group whose elements are bijective maps from to , under composition. Then, if a non-identity function satisfies:
then the subgroup generated by is a cyclic subgroup of order five. If, on the other hand, no iteration of ever gives the identity map, then the subgroup generated by is a cyclic subgroup of infinite order, i.e., it looks like the group of integers.
Similarly, in the group of all permutations on a set , consider the permutation that sends to and to , in other words, it interchanges each odd integer with the even integer above it. Then, is the identity map, so generates a cyclic subgroup of order two.
The infinite cyclic group
Further information: Group of integers
Let's now take a closer look at the infinite cyclic group, which can be viewed as the group of integers under addition. This group has some interesting properties, some of which put it in sharp contrast with the finite cyclic groups:
- Not every element can be expressed as a positive power, or multiple, of the generator. So -1 cannot be written as . This contrasts with finite cyclic groups, where every element can be written as sufficiently often. That's because for finite cyclic groups, we eventually wrap around.
- The subgroups of this group are either the whole group, or are subgroups of the form where is the smallest positive integer in the subgroup. The subgroup is again infinite cyclic, with the new generator being . Thus, every nontrivial subgroup of the group is isomorphic to the group (i.e., it looks just like the whole group). In particular, we can identify the nontrivial subgroups of with the positive integers.
Intersections and joins of subgroups
Given two nontrivial subgroups of , we want to figure out what their intersection and join look like, in terms of their generating elements. There are neat answers:
- For positive integers , the intersection of the subgroups and is the subgroup where is the least common multiple of and . More generally, the intersection of , is the subgroup generated by the least common multiple of the s.
- For positive integers , the join of the subgroups and is the subgroup , where is the greatest common divisor of and . More generally, the join of , is the subgroup generated by the greatest common divisor of the s.
Here are some facts about generating sets:
- There are only two possible generating sets of size 1: and
- If is a generating set for the integers, then the set of absolute values of elements of is also a generating set. So we can restrict attention to generating sets whose elements are positive.
- A set of positive integers is a generating set for the group of integers if and only if the gcd of all the integers is 1. Thus, for instance form a generating set, so do and
- A set of positive integers is an irredundant generating set for the group of integers (i.e., a generating set from which no element can be thrown out) if the gcd of all the integers is 1, but the gcd of any proper subset is not 1. Thus is irredundant, as is , but is not, because the subset generates the group.
Finite cyclic groups
Finite cyclic groups are a little trickier to handle than infinite cyclic groups. The main complication for finite cyclic groups is that, while analogous statements to those for infinite cyclic groups can be made, the order of the group, and the number-theoretic properties of this number, play an important role.
In the cyclic group of order , the subgroup generated by any element , is the same as the subgroup generated by the gcd . (we're viewing the gcd as ordinary integers). There is thus a one-to-one correspondence between:
Divisors of the order of the cyclic group Subgroups of the cyclic group
For every divisor of , we have a subgroup, comprising the multiples of taken modulo . For instance, let . Then, the cyclic group of order 6 has four subgroups:
- The divisor 1 corresponds to the whole group: . This subgroup is also the cyclic subgroup generated by 5.
- The divisor 2 corresponds to a cyclic subgroup of order 3, the multiples of 2: . This subgroup is also the cyclic subgroup generated by 4.
- The divisor 3 corresponds to a cyclic subgroup of order 2, the multiples of 3: .
- The divisor 6 corresponds to the trivial subgroup:
Note that the subgroup corresponding to a divisor has order . Thus:
- For every integer dividing , there is a unique subgroup whose order equals that integer.
- Thus, the number of subgroups equals the number of divisors of .
- When is a prime number, there are only two subgroups: the trivial subgroup and the whole group.
Intersections and joins
Now that we've identified subgroups with divisors, we can discuss the intersections and joins of subgroups in terms of the effect on divisors:
- The intersection of the subgroups corresponding to divisors of is the subgroup corresponding to the divisor : the lcm. Note that this is also a divisor of .
- The join of the subgroups corresponding to divisors of is the subgroup corresponding to the divisor : the gcd. Note that this is also a divisor of .
Unlike the case of the infinite cyclic group, there could be many possible generating sets of size one for a finite cyclic group. Indeed, by the above remarks, any that is relatively prime to , forms a generator for the cyclic group of order . For instance, when , then are all possibilities for a one-element generator.
The total number of generators equals the number of elements in that are relatively prime to , and this number is denoted , and termed the Euler-phi function of . For prime , .