Order of an Element & Primitive Roots

Multiplicative order, its divisibility of (n), and generators of the units.

The idea

The order of a residue measures how long its powers take to return to $1$. Let $n$ be a positive integer and let $a$ be coprime to $n$. Euler's totient theorem guarantees that $a^{\phi(n)} \equiv 1 \pmod{n}$, where $\phi(n)$ counts the residues coprime to $n$, so the powers $a, a^{2}, a^{3}, \ldots$ reach $1$ and then cycle.

Definition (Order of a residue).

For a positive integer $n$ and an integer $a$ coprime to $n$, the order of $a$ modulo $n$, written $\operatorname{ord}_n(a)$, is the least positive integer $k$ with $a^{k} \equiv 1 \pmod{n}.$

Theorem (Order divides the totient).

For every $a$ coprime to $n$, $\operatorname{ord}_n(a)$ divides $\phi(n)$.

This restricts the candidates to the divisors of $\phi(n)$, so computing an order means testing a short list of exponents.

The largest possible order is $\phi(n)$ itself. A residue that attains it is a primitive root modulo $n$: its powers run through every residue coprime to $n$ before returning to $1$, so this one element generates them all. Not every modulus has a primitive root, but every prime does.

Ways to work on it

• Walkthrough. Order of a unit, why it divides (n), and what a primitive root is.
• Practice. Compute the multiplicative order of a unit modulo a prime.
• Hardest. Count primitive roots and generate one from another.

Not sure where to start? Take the ten-question placement test.