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, a2, a3, … 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 ai ≡ aj (mod m) for some 0 < i < j. And since (a, m) = 1, we can perform cancellation by ai to obtain aj-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 ap-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 ci between 0 and m-1 such that . Now all the ci‘s are distinct: indeed if ci = cj then and since a is coprime to m, we get , which is a contradiction. Hence, the ci‘s are just a permutation of the bi‘s. If we take the product of them all, we get:
Since each bi 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 ordm(a) for the smallest positive integer d for which . In other words, ordm(a) is the length of the cycle when we consider the successive powers of a modulo m. Hence, the above examples give us ord11(2) = 10, ord35(3) = 12. Note that we always have ordm(1) = 1.
Caution. The notation ordm(a) is sometimes used for another wholly different concept. When p is a prime, ordp(a) is also used to denote the highest r for which pr divides a. Thus, ord5(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 = ordm(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 …