In the last chapter, we looked at multiplicative orders of integers a modulo n by considering different values of a separately. 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 a modulo n. Then, we have a pretty good grasp on the powers of a when computed modulo n. For example, with a = 3 and n = 10, the first 30 powers a j reduced modulo n are
We know that this sequence will be purely periodic, and the period, which is also ordn(a), will be the first position which contains a 1. In this case, ord10(3) = 4. Moreover, we then know that 3i 3 j (mod 10) if and only if i j (mod ord10(3)). In other words, 3i 3 j (mod 10) if and only if i j (mod 4). Thus,
3i 3 (mod 10) if i 1 (mod 4) 3i 9 (mod 10) if i 2 (mod 4) 3i 7 (mod 10) if i 3 (mod 4) 3i 1 (mod 10) if i 0 (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 33 7 (mod 10). It then follows that
7 j (33) j 33j (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 76 % 10, we could have reasoned that
76 318 9 (mod 10)
because 18 2 (mod 4). Looking at the results above, we can see that this is right.
We now focus on ord10(3j) for different values of j. The next applet takes a value for a and for n as input. It computes ordn(aj) for each j from 1 to ordn(a). Here it is in action when a = 3 and n = 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 a is relatively prime to n and j > 0. Find a formula for ordn(a j) in terms of ordn(a) and j.
Research Question 2
Suppose that a is relatively prime to n. What are the values of ordn(a j) for j = 0, 1, 2, . . . ?
Section 10.1 | Section 10.2 | Section 10.3 | Section 10.4
Chapter 10 | DNT Table of Contents
Copyright © 2001 by W. H. Freeman and Company