10.1   Orderly Orders

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

Your browser does not support java.

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:

Your browser does not support java.

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:

Your browser does not support java.

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