Section 10.1: Orderly Orders

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 ord_n(a), will be the first position which contains a 1. In this case, ord₁₀(3) = 4. Moreover, we then know that 3ⁱ 3^j (mod 10) if and only if i j (mod ord₁₀(3)). In other words, 3ⁱ 3^j (mod 10) if and only if i j (mod 4). Thus,

3ⁱ 3 (mod 10)   if   i 1 (mod 4)

3ⁱ 9 (mod 10)   if   i 2 (mod 4)

3ⁱ 7 (mod 10)   if   i 3 (mod 4)

3ⁱ 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 3³ 7 (mod 10). It then follows that
7^j (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:

Your browser does not support java.
If we had wanted to predict the precise value of 7⁶ % 10, we could have reasoned that
7⁶ 3¹⁸ 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₁₀(3^j) for different values of j. The next applet takes a value for a and for n as input. It computes ord_n(a^j) for each j from 1 to ord_n(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 ord_n(a^j) in terms of ord_n(a) and j.

Research Question 2

Suppose that a is relatively prime to n. What are the values of ord_n(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

3ⁱ 3 (mod 10)	if	i 1 (mod 4)
3ⁱ 9 (mod 10)	if	i 2 (mod 4)
3ⁱ 7 (mod 10)	if	i 3 (mod 4)
3ⁱ 1 (mod 10)	if	i 0 (mod 4).