Section 8.1: Order, Order, Who Has an Order?

8.1 Order, Order, Who Has an Order?

In the Prelab exercises, you started looking at powers of a modulo n (for fixed a and n). The first property these powers have is that they always repeat (eventually). The function below allows us to see many powers of a modulo n at once to observe this. To compute the remainders of 3¹, 3², 3³, . . . , 3³⁰, when divided by 180, use the following applet.

Your browser does not support java.
Notice that the powers ultimately repeat. The repetition may not start with the very first term, as in the case shown. Recall that the terms before the repetition start are called the preperiod. In this case, the preperiod has a length of 1. After the preperiod, the sequence 9, 27, 81, 63 repeats from there on. The sequence is periodic starting with the second term and its minimal period is 4 (because the length of this repeating block is 4). Experiment with different values for a and n to see different combinations of periods and preperiods.

Exercise 1

Consider the sequence a⁰, a¹, a², a³, . . . taken modulo n for a fixed integer n.

(a) Show that there exist distinct integers i and j such that aⁱ a^j (mod n).

(b) Show that the sequence above is ultimately periodic. (In other words, if we disregard the first few terms, there exists an integer P > 0 such that a^k a^k+P (mod n) for all k sufficiently large.)

The fact that powers of a fixed integer ultimately repeat modulo n makes the powers much more accessible. It makes it easy to compute very large powers of an integer mod n since one can extrapolate from the small powers.

We will now focus on powers of elements which have an order. As defined in the Prelab section, an integer a has order m if m is the least positive integer such that a^m 1 (mod n). So, an integer a has an order if some power of a is congruent to 1 modulo n. Our first order of business is to determine which elements have an order. To assist you in your investigation, we provide a function which shows the powers modulo n for every congruence class a.

For example, to see the first 15 powers for each of the congruence classes modulo 6, execute the next function:

Your browser does not support java.
Each row of the output corresponds to a different congruence class a. In a given row, we have a¹, a², a³, a⁴, . . . , a¹⁵. You can easily see the value of a for a given row by looking at the first entry, a¹.

A congruence class a has an order if 1 appears in the row corresponding to a. Note, that there is no guarantee that 15 powers will be sufficient in all cases, so you may need to vary the second parameter M to see the whole story.

Research Question 1

Let n be a positive integer. Which integers a have an order?

Section 8.1 | Section 8.2 | Section 8.3 | Section 8.4
Chapter 8 | DNT Table of Contents