## 8.2   Benefits of Order

For the remainder of this chapter, we will restrict to integers a which have an order modulo n.

### 8.2.1  A Sample Calculation

As mentioned above and used in the Prelab section, we can apply knowledge of the order of a modulo n) and the first few powers of a to quickly compute very large powers modulo n. For example, we can see the first few powers of 7 modulo 10 by executing the next function:

Your browser does not support java.

Suppose we wanted to know the final digit of 712344. (The final digit of a number is simply its remainder modulo 10.) We can see from the output above that the powers of 7 taken modulo 10 repeat with period 4. (Moreover, ord10(7) = 4.) So, we can see that 74 1 (mod 10), 78 1 (mod 10), 712 1 (mod 10), . . . , 712344 1 (mod 10) because 12344 0 (mod 4). Thus,

712345 = 712344+1 = 712344 · 7 7 (mod 10).

We can check this result by computing 712345 and looking at the last digit (this may take a little while):

Your browser does not support java.

As you can see, the last digit is, in fact, 7 (Yippee!). Clearly, the method using ord10(7) is simpler (and faster) than actually computing 712345.

### 8.2.2  General Properties

We would like to formalize the properties being used in the calculation above. Experiment with functions above to answer the following questions:

#### Research Question 2

Find a characterization, in terms of ord(a), for all exponents i such that ai 1 (mod n).

#### Research Question 3

Generalize your conjecture for Research Question 2 to give a necessary and sufficient condition for j and k (in terms of ord(a)) so that aj ak (mod n).

Since the answers to both of these questions are related to ordn(a), they tell us that the order of a modulo n is really the key to understanding all of the powers of a.

Section 8.1 | Section 8.2 | Section 8.3 | Section 8.4