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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s