In the previous lesson we defined and examined cyclic groups. We recall that a cyclic group is a group that happens to have an element 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 generates the entire group if it is the case that every element in the group can be obtained by multiplying to itself some number of times. We also recall that this includes the possibility of multiplying the inverse of to itself some number of times.
To put this all a bit more mathematically, we say that an element is a generator of the group if any element of the group can be written as for some integer Before we remind ourselves of some particular examples of this, we note that simply means “multiply to itself times.” For example, the element itself corresponds to the value while the identity element in the group corresponds to the value (simply because, by definition, any element to the power of zero is the identity element). Additionally, we have (also by definition) that is the inverse of Thus, when is a negative integer like then the notation means “multiply the inverse of 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 of integers is the number since any integer is just equal to raised to the power of that integer. Namely, we see that 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
Similarly, the integer is equal to negative 1 added to itself 15 times, which is written as because the inverse of is and so we want to “abstract group multiply” the inverse of 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 (with abstract group multiplication being addition modulo 5) can be written as for some integer Namely, because and we also have that because where holds because we are doing addition modulo 5.
We also note that we can write because, by definition, any group element raised to the power of is the identity element of the group. This is fine, though, because there is nothing wrong with the fact that In particular, just because an element of the group (in this case, the identity element ) can be written as for some integer (in this case, ), this doesn’t mean that a different value of (in this case, ) can’t also work. Indeed, the reader is encouraged to convince herself that we have as well as other equalities like (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 is a generator of a group We then know that its inverse, the element is also a generator of the group To see this, let us consider some arbitrary element (recall that this is read as “let us consider some arbitrary element in the group “). We then know that for some integer simply because we know that is a generator of the group so that every element in the group takes this form. We then immediately know that In other words, we know that is equal to the inverse of raised to the power of Namely, if we raise the inverse of to the negative of then it is the same as raising itself to the power of Let’s look at a specific example of this to see how it all works.
Let’s consider the set with addition modulo We know that is a generator of this group. However, since is the inverse of in this group (i.e., modulo ), then is also a generator of our group based on our arguments in the previous paragraph. This is indeed the case. For example, where in the second equality we used the fact that (modulo 9). Thus, we see that any number in this group can be obtained by raising to the negative of that number. Namely, as another example, We therefore see that is also a generator of this group.
However, we don’t need to first translate back to its inverse in order to see that is a generator of this group. For example, we can write the number as since 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):
The reason for all of this is that we’re adding modulo 9, so that, for example
We have therefore just shown that is a generator for the group with addition modulo
Are we done finding generators of the group ? Namely, are the only generators of this group and ? The answer is indeed no once again! For example, the number is also a generator for this group. To see this, we simply note that we can obtain every element of this group by adding to itself over and over again:
Due to our prior discussion, we now also know that is a generator of our group as well, since it is the inverse of
We have now found that and 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 is not a generator of our group. The reason for this is that but so that as we keep adding to itself over and over again, we simply keep cycling through the numbers and In particular, the elements and can never be obtained by adding to itself over and over again. For similar reasons, one can check that the element is not a generator of the group
It turns out, however, that is a generator of the group with addition modulo as well as for the group of addition modulo (the reader should check these two facts). So what is it that makes 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 we have seen that is not a generator, whereas when we do addition modulo or (or indeed for any number that isn’t a multiple of ) we see that is a generator. The reason for this is clear: if we’re doing addition modulo a number that is a multiple of then adding to itself over and over again will simply have us cycling through the multiples of and will never allow us to get the numbers that are not multiples of (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 so that our group is then any (non-zero) element in the group that shares a common factor with is not a generator of the group, and any element in the group that does not share any common factors with is a generator of the group. For example, is not a generator of the group with addition modulo (as the reader should check) and this is in line with what we just said because and share the common factor of
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!
- 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 is not a generator of the group We then need to check that is a generator both for the group with addition modulo as well as for the group with addition modulo Finally, we need to check that is not a generator of the group with addition modulo
- Show that every element other than in the group with addition modulo is a generator.
On To Lesson 37