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:
Try it out, and watch for values of n for 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 n 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