8.3   Limitations on Orders

In the last section, we studied the order of a modulo n and the behavior of the powers of a. Here we shall consider the following question:

Given n, what can we say about the possible orders of elements? That is, are all integers really candidates for values of ordn(a) as we keep n fixed and vary a?

To get a start on this question, there are two new functions below to help investigate orders of integers modulo n. The first takes a and n as input, and returns the order of a modulo n. Try it out, taking a = 2 and n = 7:

Your browser does not support java.

The second function will give the order for each integer modulo n that has an order. If n = 30, here's what we get:

Your browser does not support java.

Use these two functions to collect enough data on the order of integers a modulo p, where p is a prime, to formulate a solution to the following question.

Research Question 4

What are the possible orders for an integer a modulo a fixed prime p?

Note: It will be much easier to prove your conjecture after you have completed the remaining research questions. So, do yourself a favor and hold off on this proof until after you've finished the last section. Even then, you might only be able to prove part of your conjecture. If there is some part you cannot prove, give numerical evidence to support your conjecture.

Section 8.1 | Section 8.2 | Section 8.3 | Section 8.4

Chapter 8 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company