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:
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]](equiv.gif)
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):
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 2Find a characterization, in terms of ord(a),
for all exponents i such that ai |
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 |
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.