Pick a number a and a modulus n with \gcd(a, n) = 1. Now start multiplying a by itself, over and over, reducing modulo n at every step: a, a^2, a^3, \dots. Because there are only finitely many residues to land on, this sequence is doomed to repeat eventually — and in fact it always cycles back round to 1 at some point. The natural question is: how many steps does that take?

That count has a name — the order of a — and it hides a beautiful piece of structure: whatever the order turns out to be, it is never some arbitrary number. It always divides \varphi(n) exactly, tying every element's private cycle length to the totient Euler's theorem already told us about. This idea is the backbone of how cryptographers build "one-way" puzzles that are easy to compute forward and (believed) hard to undo.

Think of it like a clock face with n-ish hours marked on it, except the "hours" are the residues coprime to n, and instead of ticking forward by one each time, a jumps forward by a fixed multiplicative step. Some starting numbers visit almost every hour before returning to 1; others loop back after just one or two jumps. The order is simply the length of whichever loop a happens to trace.

Definition

The order of a modulo n (with \gcd(a,n)=1) is the smallest positive k with

Modulo 7, the powers of 2 go 2, 4, 1 and repeat — so 2 has order 3. The powers of 3 go 3, 2, 6, 4, 5, 1 — order 6, the longest possible. Same modulus, same finite set of residues to visit, but wildly different cycle lengths — the order genuinely depends on which number you pick, not just which modulus you're working in.

Worked example: the order of 2 modulo 7

Let's do this one carefully, step by step, listing every power of 2 modulo 7 until we first hit 1:

We hit 1 at the third power and nowhere sooner, so the order of 2 modulo 7 is exactly 3. From here on, the powers just repeat the same three-step cycle 2, 4, 1, 2, 4, 1, \dots forever — the cycle never grows longer or changes shape, it just loops.

Now check the divisibility law before we've even stated it formally: \varphi(7) = 6 (since 7 is prime, all six residues 1,\dots,6 are coprime to it). Does 3 divide 6? Yes — 6 = 2 \times 3. The order of an element that we found by brute-force listing already obeys the pattern the theorem below guarantees.

The divisibility law

Why? Suppose a^{k} \equiv 1 \pmod n but the order d did not divide k. Using the division algorithm, write k = qd + r with 0 < r < d. Then

so a^{r} \equiv 1 with r strictly smaller than the order d — contradicting the fact that d was the smallest such exponent. So the remainder r must be 0, meaning d divides k exactly. Since a^{\varphi(n)} \equiv 1 \pmod n by Euler's theorem, setting k = \varphi(n) tells us the order always divides \varphi(n) in particular.

Worked example: the possible orders modulo 9

Here's the divisibility law used as a shortcut rather than a brute-force check. Modulo n = 9, the totient is \varphi(9) = 6 (the residues coprime to 9 are 1, 2, 4, 5, 7, 8). Before computing a single power, the theorem already tells us that every order modulo 9 must be a divisor of 6 — so the order of any element coprime to 9 can only ever be 1, 2, 3, or 6. No element could possibly have order 4 or 5, and we know that before doing any arithmetic at all.

Checking a = 2: powers go 2, 4, 8, 16 \equiv 7, 14 \equiv 5, 10 \equiv 1 \pmod 9 — order 6, the maximum allowed, confirming 2 is a primitive root modulo 9. Checking a = 8 \equiv -1: 8^2 = 64 \equiv 1 \pmod 9, so its order is just 2 — also one of the allowed divisors, just a much shorter cycle.

Why order matters: hunting for primitive roots

The order tells you the size of the cyclic "orbit" that a traces out under repeated multiplication. Most elements have an order somewhere in the middle of the divisors of \varphi(n), but elements of maximal order — equal to \varphi(n) itself, visiting every coprime residue before returning to 1 — are special enough to earn their own name: primitive roots. Knowing that every order must divide \varphi(n) turns the hunt for a primitive root from blind guessing into an organised search: you only ever need to rule out the handful of proper divisors of \varphi(n), rather than test every exponent up to \varphi(n) one at a time.

Worked example: a toy key exchange

Here's a miniature version of the Diffie–Hellman idea, small enough to do by hand, to show exactly where "order" earns its keep. Agree publicly on the prime p = 11 and the base g = 2 — and since 2 has order 10 = \varphi(11) modulo 11 (you can check this the same way as the order-of-2-mod-9 example above), it is a primitive root: its powers sweep out every residue from 1 to 10 before repeating, so nothing is wasted.

Say Alice secretly picks a = 4 and Bob secretly picks b = 3 — neither tells the other. Alice publicly broadcasts A = 2^{4} = 16 \equiv 5 \pmod{11}, and Bob publicly broadcasts B = 2^{3} = 8 \pmod{11}. Anyone listening now knows p, g, A = 5, and B = 8 — but not the secret exponents.

Alice takes Bob's broadcast and raises it to her own secret power: B^{a} = 8^{4} = 4096 \equiv 4 \pmod{11} (since 4096 = 11 \times 372 + 4). Bob takes Alice's broadcast and raises it to his own secret power: A^{b} = 5^{3} = 125 \equiv 4 \pmod{11} (since 125 = 11 \times 11 + 4). Both land on 4 — the same shared secret — because B^{a} = (g^{b})^{a} = g^{ab} = (g^{a})^{b} = A^{b}: exponents multiply in either order. An eavesdropper who saw 5 and 8 travel across the wire has no efficient way to recover a or b from them — that's the discrete logarithm problem, and for a real modulus with hundreds of digits instead of just 11, nobody knows how to solve it quickly.