Tour:Exploration of cyclic groups

This page is part of the Groupprops guided tour for beginners (Jump to beginning of tour)
PREVIOUS: No proper nontrivial subgroup implies cyclic of prime order| UP: Introduction four (beginners)| NEXT: Cyclicity is subgroup-closed
General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

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 $n$ is addition of integers in the ordinary fashion, except that we set $n$ to be equal to zero. Intuitively, every time we reach $n$, 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:

1. The identity element being 0.
2. The additive inverse of 0, is 0, and the additive inverse of a nonzero digit $a$ is the digit that'd ordinarily be written as $10-a$

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 $C_{10}$, $\mathbb {Z} _{10}$ or $\mathbb {Z} /10\mathbb {Z}$.

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 $a$ hours and then move it forward by $b$ hours, it has moved forward by $(a+b)$ hours, so it points at $(a+b)$. However, if $a+b$ is bigger than 12, then we wrap around the clock once, so we effectively reach $a+b-12$. Thus, moving the hour hand forward by 7 and then moving it forward by 8 makes it point to $7+8-12=3$ 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 $a$ hours, then moving it forward by $12-a$ hours does the trick of reversing the operation.

This Abelian group is termed the cyclic group of order 12, denoted $\mathbb {Z} /12\mathbb {Z}$ or $\mathbb {Z} _{12}$ or $C_{12}$.

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 $2+3=5$ 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:

1. There are 60 minutes in an hour. The operations of moving the minute hand forward, then, form a cyclic group of order 60.
2. 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.
3. 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

Modular arithmetic is the study of cyclic groups: groups that we obtain from the integers by wrapping some integer $n$ to zero. $n=7$ corresponds to days of the week, $n=60$ corresponds to minutes in an hour, $n=24$ corresponds to hours in a day, and so on. Modular arithmetic seeks to develop a general theory to study cyclic groups modulo $n$ for different $n$.

The general description for integers modulo $n$

The cyclic group of order $n$ ($n$ 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 $0,1,2,3,\dots ,n-1$
• The sum of two elements $a$ and $b$ is their usual integer sum $a+b$ if $a+b<n$, and is $a+b-n$ if $a+b\geq n$
• The identity element for addition is 0
• The inverse of 0 is 0, and the inverse of $a$ is $12-a$ for other $a$

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 $n$. This is saying that you could move the hour hand forward by $1000$ 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 $n$. In other words, two integers are equivalent if they leave the same remainder modulo $n$. This equivalence relation is termed being congruent modulo $n$. In symbols, we write:

$a\equiv b\mod n$

if $a$ and $b$ are congruent mod $n$.

The relation of being congruent mod $n$ is preserved by addition, i.e., if:

$a\equiv b\mod n,\qquad c\equiv d\mod n$

Then:

$a+c\equiv b+d\mod n$

Thus, the cyclic group mod $n$ 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 $0,1,2,\dots ,n-1$: 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 $\mathbb {Z} /n\mathbb {Z}$, i.e., the cyclic group of order $n$, $1$ is a generator. Every element of the group can be written in the form $1+1+1+1+\dots +1$. So, for instance, in the cyclic group mod $5$, the element $3$ can be written as $1+1+1$, It can also be written as $1+1+1+1+1+1+1+1$.

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:

$0=2+2+2,1=2+2,2=2$

Similarly, in the cyclic group of integers mod 5, the element 3 is a generator, because:

$0=3+3+3+3+3,\qquad 1=3+3,\qquad 2=3+3+3+3,\qquad 3=3,\qquad 4=3+3+3$

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:

$4,2,0,4,2,0,\dots$

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 $n$, an element $a$ is a cyclic element if and only if $a$ and $n$ are relatively prime. This is based on a general fact that given two relatively prime integers $a$ and $n$, there exist integers $x$ and $y$ such that $ax+ny=1$.

Cyclic groups in the abstract sense

We've so far viewed cyclic groups as groups of integers mod $n$, for some $n$. 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 $x$, then there are two possibilities.

1. There exists a positive integer $n$ such that $x^{n}$ is the identity element. In that case, the group has only finitely many elements: $e,x,x^{2},\dots ,x^{n-1}$. Further, for any $m$, $x^{m}=x^{r}$ where $r\cong m\mod n$. This group behaves exactly like the group of integers mod $n$, where we identify an integer $j$ mod $n$, with the element $x^{j}$. (in technical parlance, the groups are isomorphic).
2. There is no positive integer $n$ for which $x^{n}$ is the identity element. In that case, the group has infinitely many elements, and $x^{n}\neq x^{m}$ for $n\neq m$. This group is the same as the ordinary group of integers, where we identify $j$ with $x^{j}$. (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:

$2^{1}=2,2^{2}=4,2^{3}=3,2^{4}=1$

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 $p$, the nonzero congruence class mod $p$, form a cyclic group of order $p-1$. There isn't any known algorithm to find a generator for this cyclic group.
• For any prime power $p^{k}$, where $p\neq 2$, the congruence classes of those elements that are relatively prime to $p$, form a cyclic group of order $p^{k-1}(p-1)$.
• In general, for any integer $n$, the congruence classes of those elements that are relatively prime to $n$, 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 $\mathbb {R}$ to $\mathbb {R}$, under composition. Then, if a non-identity function $f:\mathbb {R} \to \mathbb {R}$ satisfies:

$f\circ f\circ f\circ f\circ f=\operatorname {Id}$

then the subgroup generated by $f$ is a cyclic subgroup of order five. If, on the other hand, no iteration of $f$ ever gives the identity map, then the subgroup generated by $f$ 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 $\{1,2,3,\dots ,2n\}$, consider the permutation $\sigma$ that sends $2j-1$ to $2j$ and $2j$ to $2j-1$, in other words, it interchanges each odd integer with the even integer above it. Then, $\sigma ^{2}$ is the identity map, so $\sigma$ 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 $(\mathbb {Z} ,+)$ of integers under addition. This group has some interesting properties, some of which put it in sharp contrast with the finite cyclic groups:

1. Not every element can be expressed as a positive power, or multiple, of the generator. So -1 cannot be written as $1+1+\dots +1$. This contrasts with finite cyclic groups, where every element can be written as $1+1+1+\dots +1$ sufficiently often. That's because for finite cyclic groups, we eventually wrap around.
2. The subgroups of this group are either the whole group, or are subgroups of the form $d\mathbb {Z}$ where $d$ is the smallest positive integer in the subgroup. The subgroup $d\mathbb {Z}$ is again infinite cyclic, with the new generator being $d$. 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 $\mathbb {Z}$ with the positive integers.

Intersections and joins of subgroups

Given two nontrivial subgroups of $\mathbb {Z}$, we want to figure out what their intersection and join look like, in terms of their generating elements. There are neat answers:

1. For positive integers $m,n$, the intersection of the subgroups $m\mathbb {Z}$ and $n\mathbb {Z}$ is the subgroup $[m,n]\mathbb {Z}$ where $[m,n]$ is the least common multiple of $m$ and $n$. More generally, the intersection of $m_{1}\mathbb {Z} ,m_{2}\mathbb {Z} ,\dots ,m_{r}\mathbb {Z}$, is the subgroup generated by the least common multiple of the $m_{i}$s.
2. For positive integers $m,n$, the join of the subgroups $m\mathbb {Z}$ and $n\mathbb {Z}$ is the subgroup $(m,n)\mathbb {Z}$, where $(m,n)$ is the greatest common divisor of $m$ and $n$. More generally, the join of $m_{1}\mathbb {Z} ,m_{2}\mathbb {Z} ,\dots ,m_{r}\mathbb {Z}$, is the subgroup generated by the greatest common divisor of the $m_{i}$s.

Generating sets

Here are some facts about generating sets:

1. There are only two possible generating sets of size 1: $\{1\}$ and $\{-1\}$
2. If $S$ is a generating set for the integers, then the set of absolute values of elements of $S$ is also a generating set. So we can restrict attention to generating sets whose elements are positive.
3. 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 $\{2,3\}$ form a generating set, so do $\{3,8,9\}$ and $\{6,10,15\}$
4. 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 $\{2,3\}$ is irredundant, as is $\{6,10,15\}$, but $\{3,8,9\}$ is not, because the subset $\{3,8\}$ 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.

Subgroups

In the cyclic group $C_{n}$ of order $n$, the subgroup generated by any element $a$, is the same as the subgroup generated by the gcd $(a,n)$. (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 $\leftrightarrow$ Subgroups of the cyclic group

For every divisor $d$ of $n$, we have a subgroup, comprising the multiples of $d$ taken modulo $n$. For instance, let $n=6$. Then, the cyclic group of order 6 has four subgroups:

1. The divisor 1 corresponds to the whole group: $\{0,1,2,3,4,5\}$. This subgroup is also the cyclic subgroup generated by 5.
2. The divisor 2 corresponds to a cyclic subgroup of order 3, the multiples of 2: $\{0,2,4\}$. This subgroup is also the cyclic subgroup generated by 4.
3. The divisor 3 corresponds to a cyclic subgroup of order 2, the multiples of 3: $\{0,3\}$.
4. The divisor 6 corresponds to the trivial subgroup: $\{0\}$

Note that the subgroup corresponding to a divisor $d$ has order $n/d$. Thus:

1. For every integer dividing $n$, there is a unique subgroup whose order equals that integer.
2. Thus, the number of subgroups equals the number of divisors of $n$.
3. When $n$ 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:

1. The intersection of the subgroups corresponding to divisors $d_{1},d_{2}$ of $n$ is the subgroup corresponding to the divisor $[d_{1},d_{2}]$: the lcm. Note that this is also a divisor of $n$.
2. The join of the subgroups corresponding to divisors $d_{1},d_{2}$ of $n$ is the subgroup corresponding to the divisor $(d_{1},d_{2})$: the gcd. Note that this is also a divisor of $n$.

Generating sets

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 $a$ that is relatively prime to $n$, forms a generator for the cyclic group of order $n$. For instance, when $n=12$, then $a=1,5,7,11$ are all possibilities for a one-element generator.

The total number of generators equals the number of elements in $1,2,\dots ,n$ that are relatively prime to $n$, and this number is denoted $\varphi (n)$, and termed the Euler-phi function of $n$. For prime $n$, $\varphi (n)=n-1$.

This page is part of the Groupprops guided tour for beginners. Make notes of any doubts, confusions or comments you have about this page before proceeding.
PREVIOUS: No proper nontrivial subgroup implies cyclic of prime order| UP: Introduction four (beginners)| NEXT: Cyclicity is subgroup-closed