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
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:
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:
If you try this applet when r is not a primitive root modulo n, weird things happen:
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:
Research Question 3
Suppose that d is the order of some element of
Zn*, and that r
is a primitive root of n.
|
Research Question 4
Suppose that d is the order of some element of
Zn*, and that r
is a primitive root of n.
|