In the last chapter, we looked at multiplicative orders of integers

amodulonby considering different values ofaseparately. We can learn more by considering how the order of one integer might be related to the order of another integer.Suppose we know the order of

amodulon. Then, we have a pretty good grasp on the powers ofawhen computed modulon. For example, witha= 3 andn= 10, the first 30 powersa^{ j}reduced modulonare

We know that this sequence will be purely periodic, and the period, which is also ord_{n}(a), will be the first position which contains a 1. In this case, ord_{10}(3) = 4. Moreover, we then know that 3^{i}3^{ j}(mod 10) if and only ifij(mod ord_{10}(3)). In other words, 3^{i}3^{ j}(mod 10) if and only ifij(mod 4). Thus,

3 ^{i}3 (mod 10)if i1 (mod 4)3 ^{i}9 (mod 10)if i2 (mod 4)3 ^{i}7 (mod 10)if i3 (mod 4)3 ^{i}1 (mod 10)if i0 (mod 4).This gives us lots of information about the powers of 3 modulo 10. How can we really make use of this? If we look at the list of powers 3

^{ j}mod 10 above, we see that 3^{3}7 (mod 10). It then follows that7 ^{ j}(3^{3})^{ j}3^{3j}(mod 10).So, not only should the powers of 7 appear as powers of 3 (when each are reduced modulo 10), but we should be able to connect exactly which power of 7 matches with which power of 3. Let's look at the sequence of powers of 7 taken modulo 10:

If we had wanted to predict the precise value of 7

^{6}% 10, we could have reasoned that7 ^{6}3^{18}9 (mod 10)because 18 2 (mod 4). Looking at the results above, we can see that this is right.

We now focus on ord

_{10}(3^{j}) for different values ofj. The next applet takes a value foraand fornas input. It computes ord_{n}(a^{j}) for eachjfrom 1 to ord_{n}(a). Here it is in action whena= 3 andn= 10:Use this applet to experiment with the next Research Question. (Some ideas for a proof are contained in the preceding discussion!)

## Research Question 1

Suppose that

ais relatively prime tonandj> 0. Find a formula for ord_{n}(a^{ j}) in terms of ord_{n}(a) andj.

## Research Question 2

Suppose that

ais relatively prime ton. What are the values of ord_{n}(a^{ j}) forj= 0, 1, 2, . . . ?

Section 10.1 | Section 10.2 | Section 10.3 | Section 10.4

Copyright © 2001 by W. H. Freeman and Company