Background required : modular arithmetic

If you’ve any experience observing powers of numbers, you’d have noticed that the last digit runs in cycles: e.g. if you take the last digits of successive powers of 7, you get 7 → 9 → 3 → 1 → 7 → 9 → 3 → 1 → … . More generally, if you start with a positive integer *m* and take an *a* which is coprime to *m* then it’s not hard to see that the successive powers 1, *a*, *a*^{2}, *a*^{3}, … modulo *m* must run in a cycle eventually. *Why? Because since each of these powers is congruent to some c mod m, 0 ≤ c **≤ m-1, and there are only finitely many possibilities of c, eventually we have a ^{i} ≡ a^{j} (mod m) for some 0 < i < j. And since (a, m) = 1, we can perform cancellation by a^{i} to obtain a^{j-i} ≡ 1 (mod m).*

E.g. if we pick mod 11, and *a* = 2, the cycle is given by:

1 → 2 → 4 → 8 → 5 → 10 → 9 → 7 → 3 → 6 → 1

Or if we pick mod 35 and *a* = 3, we get:

1 → 3 → 9 → 27 → 11 → 33 → 29 → 17 → 16 → 13 → 4 → 12 → 1

Recall that Fermat’s Little Theorem gave us an upper bound for the length of the cycle when *p* is prime, since *a*^{p-1} ≡ 1 (mod *p*) if *a* is not divisible by *p*. For the general case, we have Euler’s Theorem:

**Theorem**. Let *m* be a positive integer and (*a*, *m*) = 1. Then , where *φ*(*m*) = Euler’s totient function = the number of *i* between 0 and *m*-1 inclusive such that *i* and *m* are coprime.

**Proof**. Let be the distinct elements in [0, *m*-1] which are coprime to *m*. Consider the products . For each *i* = 1, 2, …, *φ*(*m*), we can pick *c _{i}* between 0 and

*m*-1 such that . Now all the

*c*‘s are distinct: indeed if

_{i}*c*=

_{i}*c*then and since

_{j}*a*is coprime to

*m*, we get , which is a contradiction. Hence, the

*c*‘s are just a permutation of the

_{i}*b*‘s. If we take the product of them all, we get:

_{i}Since each *b _{i}* is coprime to

*m*, we can apply cancellation to obtain . ♦

Thus, Euler’s theorem gives us an upper bound on the length of a cycle when we take the successive powers of an element modulo m.

Let *a* be an integer coprime to *m* – we write ord* _{m}*(

*a*) for the smallest positive integer

*d*for which . In other words, ord

*(*

_{m}*a*) is the length of the cycle when we consider the successive powers of

*a*modulo

*m*. Hence, the above examples give us ord

_{11}(2) = 10, ord

_{35}(3) = 12. Note that we always have ord

*(1) = 1.*

_{m} **Caution**. The notation ord* _{m}*(

*a*) is sometimes used for another wholly different concept. When

*p*is a prime, ord

*(*

_{p}*a*) is also used to denote the highest

*r*for which

*p*divides

^{r}*a*. Thus, ord

_{5}(500) = 3 for example. It’s thus safer to describe in words:

*let d be the multiplicative order of a modulo m …*

The key property we shall make use of is as below.

Let d = ord

(_{m}a). Suppose k is some positive integer such that . Then k must be a multiple of d.

From the cycle diagram this should be obvious, but let’s give a quick proof anyway.

**Proof**. Dividing *k* by *d*, we can write *k* = *qd* + *r*, where 0 ≤ *r* ≤ *d*-1. Then we get:

and so . Since *r* < *d* and we assumed *d* to be the smallest positive integer satisfying , we must have *r* = 0, and so *k* is a multiple of *d*. ♦

Coming up next: applications in problem solving …