For the remainder of this chapter, we will restrict to integers

awhich have an order modulon.## 8.2.1 A Sample Calculation

As mentioned above and used in the Prelab section, we can apply knowledge of the order of

amodulon) and the first few powers ofato quickly compute very large powers modulon. For example, we can see the first few powers of 7 modulo 10 by executing the next function:

Suppose we wanted to know the final digit of 7

^{12344}. (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, ord_{10}(7) = 4.) So, we can see that 7^{4}1 (mod 10), 7^{8}1 (mod 10), 7^{12}1 (mod 10), . . . , 7^{12344}1 (mod 10) because 12344 0 (mod 4). Thus,7

^{12345}= 7^{12344+1}= 7^{12344}· 7 7 (mod 10).We can check this result by computing 7

^{12345}and looking at the last digit (this may take a little while):

As you can see, the last digit is, in fact, 7 (Yippee!). Clearly, the method using ord

_{10}(7) is simpler (and faster) than actually computing 7^{12345}.## 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), forallexponentsisuch thata1 (mod^{i}n).

## Research Question 3

Generalize your conjecture for Research Question 2 to give a necessary and sufficient condition for

jandk(in terms of ord(a)) so thata^{j}a(mod^{k}n).Since the answers to both of these questions are related to ord

_{n}(a), they tell us that the order ofamodulonis really the key to understanding all of the powers ofa.

Section 8.1 | Section 8.2 | Section 8.3 | Section 8.4

Copyright © 2001 by W. H. Freeman and Company