1. Explicitly check all of the things that were asked of the reader to check in this lesson. Namely, if we “control find” 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
Solution: We begin by checking that is not a generator of the group with addition modulo There are various ways to do this, some are “slicker” than others, and we’ll choose the most “nitty gritty” way. Namely, we know that if is a generator of this group, then by adding to itself over and over again we should be able to “hit” every element in the group. Thus, let us just look at what happens when we start adding to itself over and over again.
We first have that where in the second equality we used the fact that this is addition modulo so that when we land at a number that is bigger than we must “cycle back through” (i.e., subtract by so that, in particular, 9=0, 10=1, 11=2, 12=3, and so on). Thus, if we add to itself again, i.e., if we consider we have that where we used the fact that in the first equality, since everything is modulo Therefore, since we see that because this is now just adding to This means that we have already cycled back to which was our starting point. Thus, by adding to itself over and over again, we simply cycle through the elements Thus, we can never arrive at, for example, the element by adding to itself over and over again, and so is not a generator of this group. As mentioned in the lesson, this is precisely what we should expect because we know that and share a common factor (namely, they both have as a common factor).
We now need to show that is a generator of the group with addition modulo To do this, we simply add to itself over and over again, abiding by the rules of addition modulo We have
and thus we see that every element in the group can be obtained from adding three to itself over and over again, and thus is a generator of this group.
We now need to check that is indeed an generator of the group with addition modulo We have
and we again see that indeed, every element of can be obtained by adding to itself over and over again. Thus, is a generator of this group. Before ending this solution, we note that in the above calculations we began using the observation that to some power is equal to plus raised to one lower power, and using our result from the previous calculation. Namely, once we know then we also know rather quickly because
The statement that is a generator of the group with addition modulo as well as the group with addition modulo are in line with the comments that ended this lesson, since shares no common factors with nor with
We will not give the explicit proof that is not a generator of the group with addition modulo because it is identical to the proof that is not a generator of the group with addition modulo The reader is still encouraged to check this, though, and she will find that adding to itself over and over again simply cycles through
2. Show that every element other than in the group with addition modulo is a generator.
Solution: We will solve this problem by explicitly checking that every element in other than the element is a generator. However, it is enlightening to first get a more abstract understanding of why this is true. Namely, we saw in the lesson (though we didn’t explicitly prove the pattern) that the generators for these “clock arithmetic” groups are those elements that do not share a common factor with the number by which we are doing addition modulo. For example, we saw in the first exercise that when we do addition modulo the element is not a generator because it shares a common factor with In this exercise, we are doing addition modulo But is a prime number, which means that no number smaller than (and larger than ) shares a common factor with it. Thus, we expect it to be the case that every non-zero element in this group is a generator. Therefore, what we’re really doing here is checking that this is all true, since we now know that it must be.
We already know that the element is a generator of this group, since we proved in the lesson that is a generator of every “clock arithmetic” group. Let’s now move on to the element We have (remembering that this is all addition modulo )
and we therefore see that we have cycled back to which means that and so on. We therefore see that adding to itself over and over again gives the pattern
and we see that this cycles through every element of the group. Thus, since every element in the group can be expressed as raised to some power (i.e., added to itself over and over again), we see that is a generator of the group.
Let us now explicitly (and quickly) check that and are also generators. We will do this explicitly in the sense that we will write out each calculation, and we will do this quickly in the sense that this is all we’ll do, since we are now probably used to this sort of thing. The reader is encouraged to do this for herself first and use the following simply as a check on her work.
and thus the pattern here is
and thus is a generator of the group of addition modulo
To check this for we see that we have
and thus the pattern here is
and thus is a generator of the group of addition modulo (Notice that adding to itself over and over again “cycles through” the elements in this group in the reverse order that adding to itself over and over does—can you make sense of this? What about the relationship between how and respectively “cycle through” the elements of this group? Can you find the general pattern that applies to generators of any modular arithmetic group? Namely, when is it that two different generators “cycle through” the group in reverse order? These are the types of questions that we as mathematicians must get used to asking, since mathematics is just about asking questions!). This completes our exercise.
On To Lesson 37