The existence of a primitive root simplifies working with the elements of

Z_{n}^{*}, the congruence classes relatively prime ton. Suppose thatris a primitive root modulon. On the one hand, we know that there are_{}(n) congruence classes relatively prime ton. On the other hand, since ord_{n}(r) =_{}(n), the powersr^{1},r^{2},r^{3}, . . . ,r^{(n)}give_{}(n) distinct congruence classes relatively prime ton. Thus,everyinteger relatively prime tonis congruent to a power ofr. This is abig deal, so much so that we repeat it below.If

ris a primitive root modulon, then every integermthat is relatively prime tonis congruent tor^{ j}for some integerjbetween 1 and_{}(n).Let's get some help checking this out. First, we can observe this fact by looking at the powers of

rin succession. You can tell thatris a primitive root if the powers ofrhit every congruence class relatively prime ton. The applet below shows each power ofrreduced modulonuntil it reaches a power ofrwhich is congruent to 1. For example, here's what we get for the powers of 2 modulo 11:

Another way to observe this behavior is to try to write every element of

Z_{n}^{*}as a power ofrwhereris a primitive root modulon. That is the purpose of the next applet. Let's look again at the case of powers of 2 modulo 11:

If you try this applet when

ris not a primitive root modulon, weird things happen:

If

ris a primitive root modulon, then every element ofZ_{n}^{*}is congruent tor^{ j}for somej. Furthermore, your formula given in response to Research Question 1 shows how to compute ord_{n}(a^{ j}) from ord_{n}(a) andj. Thus you have a formula for the order of every element ofZ_{n}^{*}. 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 integersn30: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

dis the order of some element ofZ_{n}^{*}, and thatris a primitive root ofn.

(a) What values ofjsatisfy 1j_{}(n) and ord_{n}(r^{ j}) =d?

(b) For what values ofjisr^{ j}a primitive root modulon?

## Research Question 4

Suppose that

dis the order of some element ofZ_{n}^{*}, and thatris a primitive root ofn.

(a) How many values ofjsatisfy 1j_{}(n) and ord_{n}(r^{ j}) =d?

(b) How many primitive roots modulonare there?

Section 10.1 | Section 10.2 | Section 10.3 | Section 10.4

Copyright © 2001 by W. H. Freeman and Company