In the Prelab exercises, you started looking at powers of

amodulon(for fixedaandn). The first property these powers have is that they always repeat (eventually). The function below allows us to see many powers ofamodulonat once to observe this. To compute the remainders of 3^{1}, 3^{2}, 3^{3}, . . . , 3^{30}, when divided by 180, use the following applet.

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

aandnto see different combinations of periods and preperiods.

## Exercise 1

Consider the sequence

a^{0},a^{1},a^{2},a^{3}, . . . taken modulonfor a fixed integern.

(a) Show that there exist distinct integersiandjsuch thata^{i}a(mod^{j}n).

(b) Show that the sequence above is ultimately periodic. (In other words, if we disregard the first few terms, there exists an integerP> 0 such thata^{k}a(mod^{k+P}n) for allksufficiently large.)The fact that powers of a fixed integer ultimately repeat modulo

nmakes the powers much more accessible. It makes it easy to compute very large powers of an integer modnsince 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 integerahas ordermifmis the least positive integer such thata1 (mod^{m}n). So, an integerahas an order if some power ofais congruent to 1 modulon. 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 modulonfor every congruence classa.For example, to see the first 15 powers for each of the congruence classes modulo 6, execute the next function:

Each row of the output corresponds to a different congruence class

a. In a given row, we havea^{1},a^{2},a^{3},a^{4}, . . . ,a^{15}. You can easily see the value ofafor a given row by looking at the first entry,a^{1}.A congruence class

ahas an order if 1 appears in the row corresponding toa. Note, that there is no guarantee that 15 powers will be sufficient in all cases, so you may need to vary the second parameterMto see the whole story.

## Research Question 1

Let

nbe a positive integer. Which integersahave an order?

Section 8.1 | Section 8.2 | Section 8.3 | Section 8.4

Copyright © 2001 by W. H. Freeman and Company