## 10.2   Orders in the Presence of a Primitive Root

The existence of a primitive root simplifies working with the elements of Zn*, the congruence classes relatively prime to n. Suppose that r is a primitive root modulo n. On the one hand, we know that there are (n) congruence classes relatively prime to n. On the other hand, since ordn(r) = (n), the powers r1, r2, r3, . . . , r(n) give (n) distinct congruence classes relatively prime to n. Thus, every integer relatively prime to n is congruent to a power of r. This is a big deal, so much so that we repeat it below.

If r is a primitive root modulo n, then every integer m that is relatively prime to n is congruent to r j for some integer j between 1 and (n).

Let's get some help checking this out. First, we can observe this fact by looking at the powers of r in succession. You can tell that r is a primitive root if the powers of r hit every congruence class relatively prime to n. The applet below shows each power of r reduced modulo n until it reaches a power of r which is congruent to 1. For example, here's what we get for the powers of 2 modulo 11:

Your browser does not support java.

Another way to observe this behavior is to try to write every element of Zn* as a power of r where r is a primitive root modulo n. That is the purpose of the next applet. Let's look again at the case of powers of 2 modulo 11:

Your browser does not support java.

If you try this applet when r is not a primitive root modulo n, weird things happen:

Your browser does not support java.

If r is a primitive root modulo n, then every element of Zn* is congruent to r j for some j. Furthermore, your formula given in response to Research Question 1 shows how to compute ordn(a j) from ordn(a) and j. Thus you have a formula for the order of every element of Zn*. Pretty cool, eh? Keep your formula in mind as you tackle the next two Research Questions. As you work on these questions, you will want to collect data with the assistance of the applets defined above. To save you the trouble of hunting around for integers that have a primitive root, we provide below a list of all such integers n 30:

n = 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29.

#### Research Question 3

Suppose that d is the order of some element of Zn*, and that r is a primitive root of n.

(a) What values of j satisfy 1 j (n) and ordn(r j) = d?
(b) For what values of j is r j a primitive root modulo n?

#### Research Question 4

Suppose that d is the order of some element of Zn*, and that r is a primitive root of n.

(a) How many values of j satisfy 1 j (n) and ordn(r j) = d?
(b) How many primitive roots modulo n are there?

Section 10.1 | Section 10.2 | Section 10.3 | Section 10.4