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², a³, … 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ⁱ ≡ a^j (mod m) for some 0 < i < j. And since (a, m) = 1, we can perform cancellation by aⁱ 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_i‘s are distinct: indeed if c_i = c_j then and since a is coprime to m, we get , which is a contradiction. Hence, the c_i‘s are just a permutation of the b_i‘s. If we take the product of them all, we get:

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₁₁(2) = 10, ord₃₅(3) = 12. Note that we always have ord_m(1) = 1.

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^r divides a. Thus, ord₅(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 …