Lesson 36: The Generators

In the previous lesson we defined and examined cyclic groups. We recall that a cyclic group $G$ is a group that happens to have an element $g$ which “generates” the entire group. We also recall that when we say a particular element “generates” the entire group, we mean something very precise. In particular, an element $g$ generates the entire group if it is the case that every element in the group can be obtained by multiplying $g$ to itself some number of times. We also recall that this includes the possibility of multiplying the inverse of $g$ to itself some number of times.

To put this all a bit more mathematically, we say that an element $g$ is a generator of the group if any element of the group can be written as $g^m$ for some integer $m.$ Before we remind ourselves of some particular examples of this, we note that $g^m$ simply means “multiply $g$ to itself $m$ times.” For example, the element $g$ itself corresponds to the value $m=1$ while the identity element in the group $e$ corresponds to the value $m=0$ (simply because, by definition, any element to the power of zero is the identity element). Additionally, we have (also by definition) that $g^{-1}$ is the inverse of $g.$ Thus, when $m$ is a negative integer like $-10,$ then the notation $g^{-10}$ means “multiply the inverse of $g$ to itself 10 times.”

Let us look at particular examples of generators for particular groups. We saw last lesson that a generator in the group $\mathbb{Z}$ of integers is the number $1$ since any integer is just equal to $1$ raised to the power of that integer. Namely, we see that $15=1^{15}$ because (recalling that here, raising some number to another number’s power does not mean multiplying (in the number sense) that number to itself over and over again, but rather that we are astract group multiplying that number to itself over and over again and in our current case the abstract group multiplication is regular addition) in the group of integers (where the abstract group multiplication is simply addition) we see that

$1^{15}=1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=15.$

Similarly, the integer $-15$ is equal to negative 1 added to itself 15 times, which is written as $1^{-15}$ because the inverse of $1$ is $-1$ and so we want to “abstract group multiply” the inverse of $1$ to itself 15 times.

The groups that we will focus on in this lesson are the modular arithmetic (or “clock addition”) groups. We saw last lesson that the number 1 is also a generator for these groups. For example, any number in the group $\{0, 1, 2, 3, 4\}$ (with abstract group multiplication being addition modulo 5) can be written as $1^m$ for some integer $m.$ Namely, $4=1^4$ because $1^4=1+1+1+1=4$ and we also have that $0=1^5$ because $1^5=1+1+1+1+1=5=0$ where $5=0$ holds because we are doing addition modulo 5.

We also note that we can write $0=1^0$ because, by definition, any group element raised to the power of $0$ is the identity element of the group. This is fine, though, because there is nothing wrong with the fact that $0=1^0=1^5.$ In particular, just because an element of the group (in this case, the identity element $0$ ) can be written as $1^m$ for some integer $m$ (in this case, $m=5$ ), this doesn’t mean that a different value of $m$ (in this case, $m=0$ ) can’t also work. Indeed, the reader is encouraged to convince herself that we have $0=1^0=1^5=1^{10}$ as well as other equalities like $2=1^2=1^7=1^{12}$ (all when using addition modulo 5).

Now that we have thoroughly refreshed our memories on cyclic groups and their generators, let us now go on to ask the next obvious question. Namely, is it the case that a generator of a group is unique?

Let us get some perspective on this question. Recall that in Lesson 23 we found that the identity element of any group is unique. What this means is that if we find any element in a group that has all of the properties that we require of an identity element, then it must be the case that there is only one such element. We note that this did not have to be the case. Namely, when we defined an identity element in Lesson 22, we did not require the property that any group could only have one identity element. Instead, we stated the requirements that any identity element would have to have, and then proved that if one element has this property, then only one element can have this property.

We have now done something similar with generators. Namely, we have defined a generator of a cyclic group to be an element with a particular kind of property (the property of being able to produce any element in the group by multiplying to itself over and over again). The natural next questions to ask, then, are the following. If we have found one generator of a group, have we found all of them? Or, could it be the case that a given group has more than one generator? If a group has more than one generator, how many generators does it have? Can we group together these generators in a nice way?

This is a very common mode of reasoning in math. We first define some object, then we try to find or construct such an object, and then we ask how unique that object is. If the object is unique, then we’re done and we move on to other objects. If the object is not unique, then we try to classify these objects and determine just how non-unique they are—we try to find structure within the structure. So let us go ahead and do this for cyclic groups.

It turns out that a generator of a cyclic group is, in general, not unique. The reason for this is the following. Suppose that an element $g$ is a generator of a group $G.$ We then know that its inverse, the element $g^{-1},$ is also a generator of the group $G.$ To see this, let us consider some arbitrary element $h\in G$ (recall that this is read as “let us consider some arbitrary element $h$ in the group $G$ “). We then know that $h=g^m$ for some integer $m,$ simply because we know that $g$ is a generator of the group so that every element in the group takes this form. We then immediately know that $h=(g^{-1})^{-m}.$ In other words, we know that $h$ is equal to the inverse of $g$ raised to the power of $-m.$ Namely, if we raise the inverse of $g$ to the negative of $m,$ then it is the same as raising $g$ itself to the power of $m.$ Let’s look at a specific example of this to see how it all works.

Let’s consider the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8\}$ with addition modulo $9.$ We know that $1$ is a generator of this group. However, since $8$ is the inverse of $1$ in this group (i.e., $1+8=0$ modulo $9$ ), then $8$ is also a generator of our group based on our arguments in the previous paragraph. This is indeed the case. For example, $8^{-2}=(8^{-1})^2=1^2=2,$ where in the second equality we used the fact that $8^{-1}=1$ (modulo 9). Thus, we see that any number in this group can be obtained by raising $8$ to the negative of that number. Namely, as another example, $8^{-5}=(8^{-1})^5=1^5=5.$ We therefore see that $8$ is also a generator of this group.

However, we don’t need to first translate $8$ back to its inverse in order to see that $8$ is a generator of this group. For example, we can write the number $7$ as $8^2=8+8$ since $8+8=16=7$ when we add modulo 9. Indeed, we can write out how to obtain any element in this group as various powers of 8 as follows (if these equalities don’t make sense, see the sentence following these equalities):

$8^0=0$

$8^1=8$

$8^2=8+8=7$

$8^3=8+8+8=6$

$8^4=8+8+8+8=5$

$8^5=8+8+8+8+8=4$

$8^6=8+8+8+8+8+8=3$

$8^7=8+8+8+8+8+8+8=2$

$8^8=8+8+8+8+8+8+8+8=1$

The reason for all of this is that we’re adding modulo 9, so that, for example

$8+8+8+8+8=40=31=22=13=4.$

We have therefore just shown that $8$ is a generator for the group $\{0, 1, 2, 3, 4, 5, 6, 7, 8\}$ with addition modulo $9.$

Are we done finding generators of the group $\{0, 1, 2, 3, 4, 5, 6, 7, 8\}$ ? Namely, are the only generators of this group $1$ and $8$ ? The answer is indeed no once again! For example, the number $2$ is also a generator for this group. To see this, we simply note that we can obtain every element of this group by adding $2$ to itself over and over again:

$2^0=0$

$2^1=2$

$2^2=2+2=4$

$2^3=2+2+2=6$

$2^4=2+2+2+2=8$

$2^5=2+2+2+2+2=10=1$

$2^6=2+2+2+2+2+2=12=3$

$2^7=2+2+2+2+2+2+2=14=5$

$2^8=2+2+2+2+2+2+2+2=16=7.$

Due to our prior discussion, we now also know that $7$ is a generator of our group as well, since it is the inverse of $2.$

We have now found that $1, 2, 7,$ and $8$ are all generators of this group. At this point we might ask if there is any element in this group that doesn’t generate the whole group! Hopefully there are some non-generator elements, for otherwise it would be kind of boring (or maybe not?) if every element in the group is a generator. Indeed, though, we quickly notice that the number $3$ is not a generator of our group. The reason for this is that $3+3=6,$ but $3+3+3=9=0$ so that as we keep adding $3$ to itself over and over again, we simply keep cycling through the numbers $0, 3,$ and $6.$ In particular, the elements $1, 2, 4, 5, 7,$ and $8$ can never be obtained by adding $3$ to itself over and over again. For similar reasons, one can check that the element $6$ is not a generator of the group $\{0, 1, 2, 3, 4, 5, 6, 7, 8\}.$

It turns out, however, that $3$ is a generator of the group $\{0, 1, 2, 3\}$ with addition modulo $4,$ as well as for the group $\{0, 1, 2, 3, 4, 5, 6, 7\}$ of addition modulo $8$ (the reader should check these two facts). So what is it that makes $3$ a generator of some modular arithmetic groups and not others? The answer lies in whether or not we’re doing addition modulo a number that is a multiple of 3. For example, when doing addition modulo $9,$ we have seen that $3$ is not a generator, whereas when we do addition modulo $4$ or $8$ (or indeed for any number that isn’t a multiple of $3$ ) we see that $3$ is a generator. The reason for this is clear: if we’re doing addition modulo a number that is a multiple of $3,$ then adding $3$ to itself over and over again will simply have us cycling through the multiples of $3$ and will never allow us to get the numbers that are not multiples of $3$ (like 1, 2, 4, 5, 7, 8, etc.).

The pattern that we have seen develop (though haven’t rigorously proven yet (nor will we, as it’s “believable” enough and the proof isn’t all that important for us here)) is the following beautiful statement. If we’re doing addition modulo $N,$ so that our group is $\{0, 1, 2, ..., N-1\},$ then any (non-zero) element in the group that shares a common factor with $N$ is not a generator of the group, and any element in the group that does not share any common factors with $N$ is a generator of the group. For example, $6$ is not a generator of the group with addition modulo $8$ (as the reader should check) and this is in line with what we just said because $6$ and $8$ share the common factor of $2.$

Let us get a bit more familiar with the structure of generators within a group by taking a look at the following exercises. Then, in the next lesson, we’ll move on to something new and a bit more abstract!

Exercises

Explicitly check all of the things that were asked of the reader to check in this lesson. Namely, if we “Control f” the word “check” in this lesson, we see that we need to do the following. We first need to check that the element $6$ is not a generator of the group $\{0, 1, 2, 3, 4, 5, 6, 7, 8\}.$ We then need to check that $3$ is a generator both for the group $\{0, 1, 2, 3\}$ with addition modulo $4,$ as well as for the group $\{0, 1, 2, 3, 4, 5, 6, 7\}$ with addition modulo $8.$ Finally, we need to check that $6$ is not a generator of the group $\{0, 1, 2, 3, 4, 5, 6, 7\}$ with addition modulo $8.$
Show that every element other than $0$ in the group $\{0, 1, 2, 3, 4\}$ with addition modulo $5$ is a generator.