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 [Congruent to] 1 (mod 10), 78 [Congruent
             to] 1 (mod 10), 712 [Congruent to] 1 (mod 10), . . . , 712344 [Congruent to] 1 (mod 10) because 12344 [Congruent to] 0 (mod 4). Thus,

712345 = 712344+1 = 712344 · 7 [Congruent to] 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 [Congruent to] 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 [Congruent
                                to]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

Chapter 8 | DNT Table of Contents

Copyright © 2001 by W. H. Freeman and Company