Order of an Element Modulo m and Applications – Part I

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 $a^{\phi(m)} \equiv 1 \pmod m$, 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 $b_1, b_2, \dots, b_{\phi(m)}$ be the distinct elements in [0, m-1] which are coprime to m. Consider the products $ab_1, ab_2, \dots, ab_{\phi(m)}$. For each i = 1, 2, …, φ(m), we can pick ci between 0 and m-1 such that $c_i \equiv ab_i \pmod m$. Now all the ci‘s are distinct: indeed if cicj then $ab_i \equiv ab_j \pmod m$ and since a is coprime to m, we get $b_i \equiv b_j \pmod m$, 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:

$\displaystyle\prod_{i=1}^{\phi(m)} b_i = \prod_{i=1}^{\phi(m)} c_i \equiv \prod_{i=1}^{\phi(m)} (ab_i) = a^{\phi(m)} \prod_{i=1}^{\phi(m)} b_i \pmod m.$

Since each bi is coprime to m, we can apply cancellation to obtain $a^{\phi(m)} \equiv 1 \pmod m$. ♦

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 $a^d \equiv 1 \pmod m$. 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 $a^k \equiv 1 \pmod m$. 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 ≤ rd-1. Then we get:

$1 \equiv a^k = a^{qd+r} = (a^d)^q\cdot a^r \equiv 1 \cdot a^r \pmod m$

and so $a^r \equiv 1 \pmod m$. Since r < d and we assumed d to be the smallest positive integer satisfying $a^d \equiv 1 \pmod m$, we must have r = 0, and so k is a multiple of d. ♦

Coming up next: applications in problem solving …

This entry was posted in Notes and tagged , , . Bookmark the permalink.