10.3   When Is There a Primitive Root?

The Research Questions in the previous section assumed that an integer n had a primitive root. In this section, we shall consider the problem of determining which integers n have primitive roots, and which do not. A good place to start your investigation is with an applet from a previous chapter. It displays each element a that is relatively prime to the input n, along with the value of ordn(a). Here is a sample of its output:

Your browser does not support java.

Try it out, and watch for values of n for which there is an element of order phi(n). To make this task easier, you can use the following enhanced version of the previous applet, which includes a computation of phi(n) in the output:

Your browser does not support java.

As you can see, the output confirms what you discovered when working the Prelab exercises: there are no primitive roots modulo 15. The positive integers n leq 30 that have primitive roots were given in the previous section; here they are again:

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

Use the functions defined above to determine which other integers n have primitive roots until you have enough data to make a conjecture for the final Research Question of this chapter:

Research Question 5

Which positive integers n have primitive roots?

Note: The proof of this conjecture is quite difficult. It would be truly remarkable for a student to find a proof on his or her own. Unless told otherwise by your instructor, you should concentrate on making a good conjecture here and supporting it in your lab report with numerical evidence.

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