The Research Questions in the previous section assumed that an integer

nhad a primitive root. In this section, we shall consider the problem of determining which integersnhave primitive roots, and which do not. A good place to start your investigation is with an applet from a previous chapter. It displays each elementathat is relatively prime to the inputn, along with the value of ord_{n}(a). Here is a sample of its output:

Try it out, and watch for values of

nfor which there is an element of order_{}(n). To make this task easier, you can use the following enhanced version of the previous applet, which includes a computation of_{}(n) in the output:

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

n30 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

nhave 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

nhave 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

Copyright © 2001 by W. H. Freeman and Company