Lesson 36 Solutions

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 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.

Solution: We begin by checking that 6 is not a generator of the group \{0, 1, 2, 3, 4, 5, 6, 7, 8\} with addition modulo 9.  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 6 is a generator of this group, then by adding 6 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 6 to itself over and over again.

We first have that 6+6=12=3 where in the second equality we used the fact that this is addition modulo 9, so that when we land at a number that is bigger than 8 we must “cycle back through” (i.e., subtract by 9 so that, in particular, 9=0, 10=1, 11=2, 12=3, and so on).  Thus, if we add 6 to itself again, i.e., if we consider 6+6+6, we have that 6+6+6=3+6=9=0 where we used the fact that 6+6=3 in the first equality, since everything is modulo 9.  Therefore, since 6^3=6+6+6=0, we see that 6^4=6+6+6+6=6 because this is now just adding 6 to 0.  This means that we have already cycled back to 6, which was our starting point.    Thus, by adding 6 to itself over and over again, we simply cycle through the elements 6\rightarrow 3\rightarrow 0\rightarrow 6\rightarrow 3\rightarrow 0\rightarrow...  Thus, we can never arrive at, for example, the element 2 by adding 6 to itself over and over again, and so 6 is not a generator of this group.  As mentioned in the lesson, this is precisely what we should expect because we know that 6 and 9 share a common factor (namely, they both have 3 as a common factor).

We now need to show that 3 is a generator of the group \{0, 1, 2, 3\} with addition modulo 4.  To do this, we simply add 3 to itself over and over again, abiding by the rules of addition modulo 4. We have

3^1=3

3^2=3+3=6=2

3^3=3+(3+3)=3+2=1

3^4=3+(3+3+3)=3+1=0

and thus we see that every element in the group \{0, 1, 2, 3\} can be obtained from adding three to itself over and over again, and thus 3 is a generator of this group.

We now need to check that 3 is indeed an generator of the group \{0, 1, 2, 3, 4, 5, 6, 7\} with addition modulo 8.  We have

3^1=3

3^2=3+3=6

3^3=3+(3+3)=3+3^2=3+6=9=1

3^4=3+(3+3+3)=3+3^3=3+1=4

3^5=3+(3+3+3+3)=3+3^4=3+4=7

3^6=3+(3+3+3+3+3)=3+3^5=3+7=10=2

3^7=3+3^6=3+2=5

3^8=3+3^7=3+5=0

and we again see that indeed, every element of \{0, 1, 2, 3, 4, 5, 6, 7\} can be obtained by adding 3 to itself over and over again.  Thus, 3 is a generator of this group.  Before ending this solution, we note that in the above calculations we began using the observation that 3 to some power is equal to 3 plus 3 raised to one lower power, and using our result from the previous calculation.  Namely, once we know 3^6, then we also know 3^7 rather quickly because 3^7=3+3^6.

The statement that 3 is a generator of the group with addition modulo 4 as well as the group with addition modulo 8 are in line with the comments that ended this lesson, since 3 shares no common factors with 4 nor with 8.

We will not give the explicit proof that 6 is not a generator of the group \{0, 1, 2, 3, 4, 5, 6, 7\} with addition modulo 8 because it is identical to the proof that 6 is not a generator of the group with addition modulo 9.  The reader is still encouraged to check this, though, and she will find that adding 6 to itself over and over again simply cycles through 6\rightarrow 4\rightarrow 2\rightarrow 0\rightarrow 6\rightarrow 4\rightarrow 2\rightarrow...

2.  Show that every element other than 0 in the group \{0, 1, 2, 3, 4\} with addition modulo 5 is a generator.

Solution: We will solve this problem by explicitly checking that every element in \{0, 1, 2, 3, 4\} other than the element 0 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 9, the element 6 is not a generator because it shares a common factor with 9.  In this exercise, we are doing addition modulo 5. But 5 is a prime number, which means that no number smaller than 5 (and larger than 0) 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 1 is a generator of this group, since we proved in the lesson that 1 is a generator of every “clock arithmetic” group.  Let’s now move on to the element 2.  We have (remembering that this is all addition modulo 5)

2^1=2

2^2=2+2=4

2^3=2+2^2=2+4=6=1

2^4=2+2^3=2+1=3

2^5=2+2^4=2+3=5=0

and we therefore see that we have cycled back to 0, which means that 2^6=2 and so on.  We therefore see that adding 2 to itself over and over again gives the pattern

2\rightarrow 4\rightarrow 1\rightarrow 3\rightarrow 0 \rightarrow 2\rightarrow...,

and we see that this cycles through every element of the group.  Thus, since every element in the group can be expressed as 2 raised to some power (i.e., 2 added to itself over and over again), we see that 2 is a generator of the group.

Let us now explicitly (and quickly) check that 3 and 4 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.

We have

3^1=3

3^2=3+3=6=1

3^3=3+3^2=3+1=4

3^4=3+3^3=3+4=7=2

3^5=3+3^4=3+2=5=0

and thus the pattern here is

3\rightarrow 1\rightarrow 4\rightarrow 2\rightarrow 0\rightarrow 3...,

and thus 3 is a generator of the group of addition modulo 5.

To check this for 4 we see that we have

4^1=4

4^2=4+4=8=3

4^3=4+4^2=4+3=2

4^4=4+4^3=4+2=6=1

4^5=4+4^4=4+1=5=0

and thus the pattern here is

4\rightarrow 3\rightarrow 2\rightarrow 1\rightarrow 0\rightarrow 4...,

and thus 4 is a generator of the group of addition modulo 5.  (Notice that adding 4 to itself over and over again “cycles through” the elements in this group in the reverse order that adding 1 to itself over and over does—can you make sense of this?  What about the relationship between how 2 and 3 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.

Back To Lesson 36

On To Lesson 37

Advertisement