Order and Primitive Elements

The Order of a Unit#

Recall that $\mathbb{Z}_n^*$ is the set of units of $\mathbb{Z}_n$; the elements $a \in \mathbb{Z}_n$ with $\gcd(a,n) = 1$, i.e. exactly the elements that have a multiplicative inverse. Recall also Euler's Theorem: for any $a \in \mathbb{Z}_n^*$,

$$a^{\phi(n)} = 1 \text{ in } \mathbb{Z}_n.$$

So some power of every unit eventually equals $1$; it is natural to ask for the first time this happens.

Basically, the order of $a$ measures how long the powers $a, a^2, a^3, \dots$ take to first return to $1$; after that point the powers just repeat the same cycle forever. Other notation for the order of $a \in \mathbb{Z}_n^*$ includes $\operatorname{ord}_{\mathbb{Z}_n}(a)$, $o_n(a)$ and $|a|$.

Be careful: "order" can mean something different depending on context; the order of a finite field $F$ sometimes refers to the number of elements in $F$.

It is important to note that the order is only defined for units; if $\gcd(a,n) \neq 1$, then no power of $a$ ever reaches $1$.

Example. Explain why $\operatorname{ord}_{15}(6)$ does not exist.
Notice that $\gcd(6,15) = 3 \neq 1$, so $6 \notin \mathbb{Z}_{15}^*$. Watching the powers directly,

$$\begin{align*} 6^2 &= 36 \\ &= 2 \times 15 + 6 \\ &= 6 \text{ in } \mathbb{Z}_{15}, \end{align*}$$

so every power of $6$ collapses back to $6$ itself and can never equal $1$. More generally, $3 \mid 6^k$ for every $k \in \mathbb{Z}^+$, but $3 \nmid (15m + 1)$ for any $m$; so $6^k = 1$ in $\mathbb{Z}_{15}$ is impossible. Therefore $\operatorname{ord}_{15}(6)$ does not exist; always check that $a$ is a unit before talking about its order.

Example. Find the orders of each of the elements in $\mathbb{Z}_7^*$.
We previously found the power table for $\mathbb{Z}_7^*$:

Reading along each row until the first $1$ appears,

$$\begin{align*} \operatorname{ord}_7(1) &= 1, \\ \operatorname{ord}_7(2) &= 3, \\ \operatorname{ord}_7(3) &= 6, \\ \operatorname{ord}_7(4) &= 3, \\ \operatorname{ord}_7(5) &= 6, \\ \operatorname{ord}_7(6) &= 2. \end{align*}$$

Notice how every order that shows up ($1, 2, 3$ and $6$) is a divisor of $6 = \phi(7)$; this is not a coincidence, as we are about to see.

Order Divides the Totient#

Before the main theorem, we need a small lemma that describes exactly which powers of a unit equal $1$.

Proof. Let $d = \operatorname{ord}_n(a)$.
($\Leftarrow$) Suppose $d \mid k$; then $k = dq$ for some $q \in \mathbb{N}$, so

$$\begin{align*} a^k &= a^{dq} \\ &= (a^d)^q \\ &= 1^q \\ &= 1 \text{ in } \mathbb{Z}_n. \end{align*}$$

($\Rightarrow$) Suppose $a^k = 1$. By the Division Theorem we can write $k = qd + r$ with $0 \leq r < d$, so

$$\begin{align*} 1 &= a^k \\ &= (a^d)^q \, a^r \\ &= 1^q \, a^r \\ &= a^r. \end{align*}$$

But $d$ is the smallest positive exponent giving $1$, and $r < d$; the only way out is $r = 0$. Hence $k = qd$; that is, $d \mid k$. $\blacksquare$

Basically, the powers of $a$ hit $1$ at $d, 2d, 3d, \dots$ and nowhere else; the sequence of powers is periodic with period exactly $\operatorname{ord}_n(a)$. Since $a$ is invertible, $a^i = a^j$ (for $i \geq j$) is the same as $a^{i-j} = 1$, which gives a fact worth boxing:

$$\boxed{a^i = a^j \text{ in } \mathbb{Z}_n \iff i \equiv j \pmod{\operatorname{ord}_n(a)}.}$$

This theorem is what makes computing orders fast. Instead of grinding through $a, a^2, a^3, \dots$ one power at a time, you only ever need to test the exponents $k$ that divide $\phi(n)$; the order must be one of those divisors, and it is the smallest one that works.

Example. Find $\operatorname{ord}_{15}(7)$.
First, $\phi(15) = \phi(3)\phi(5) = 2 \times 4 = 8$, so $\operatorname{ord}_{15}(7) \in \{1, 2, 4, 8\}$. Testing the divisors in increasing order,

$$\begin{align*} 7^1 &= 7 \neq 1, \\ 7^2 &= 49 \\ &= 3 \times 15 + 4 \\ &= 4 \neq 1, \\ 7^4 &= (7^2)^2 \\ &= 4^2 \\ &= 16 \\ &= 1 \text{ in } \mathbb{Z}_{15}. \end{align*}$$

Therefore, $\operatorname{ord}_{15}(7) = 4$.

Example. Find $\operatorname{ord}_{18}(5)$.
Here $\phi(18) = \phi(2)\phi(9) = 1 \times 6 = 6$, so the order is one of $1, 2, 3, 6$. Testing,

$$\begin{align*} 5^1 &= 5 \neq 1, \\ 5^2 &= 25 \\ &= 7 \neq 1, \\ 5^3 &= 5 \times 7 \\ &= 35 \\ &= 17 \\ &= -1 \neq 1 \text{ in } \mathbb{Z}_{18}. \end{align*}$$

Every proper divisor of $6$ has failed, so the order is forced to be $\phi(18)$ itself; we do not even need to compute $5^6$, since Euler's Theorem already guarantees $5^6 = 1$. Therefore, $\operatorname{ord}_{18}(5) = 6$.

Notice how landing on $-1$ was a bonus; once you see $a^k = -1$, you immediately know $a^{2k} = 1$, and that no smaller multiple of $k$ can give $1$ along that chain. Keep an eye out for $-1$; it saves a lot of arithmetic.

Example. Find $7^{2026}$ in $\mathbb{Z}_{15}$.
From earlier, $\operatorname{ord}_{15}(7) = 4$, so the powers of $7$ repeat with period $4$; we only care about $2026$ modulo the order:

$$\begin{align*} 2026 &= 4 \times 506 + 2, \\ 7^{2026} &= (7^4)^{506} \times 7^2 \\ &= 1^{506} \times 4 \\ &= 4 \text{ in } \mathbb{Z}_{15}. \end{align*}$$

Therefore, $7^{2026} = 4$ in $\mathbb{Z}_{15}$. You could also have reduced the exponent modulo $\phi(15) = 8$ (Euler), but the order gives the tightest possible reduction. Reduce the exponent modulo the order, never modulo $n$; $2026 \equiv 1 \pmod{15}$ tells you nothing about $7^{2026}$.

Primitive Elements#

Since the order of a unit always divides $\phi(n)$, the largest an order can possibly be is $\phi(n)$ itself. The units that actually achieve this maximum get a special name.

Basically, a primitive element is a unit whose powers take the longest possible route before cycling back to $1$; as we will see shortly, its powers visit every unit along the way.

Example. The primitive elements of $\mathbb{Z}_7^*$ are $3$ and $5$, since we saw in the order table that $\operatorname{ord}_7(3) = \operatorname{ord}_7(5) = 6 = \phi(7)$.

Example. What are the primitive elements of $\mathbb{Z}_6^*$?
Here $\mathbb{Z}_6^* = \{1, 5\}$ and $\phi(6) = 2$. Clearly $\operatorname{ord}_6(1) = 1 \neq 2$, and

$$\begin{align*} 5^2 &= 25 \\ &= 4 \times 6 + 1 \\ &= 1 \text{ in } \mathbb{Z}_6, \end{align*}$$

so $\operatorname{ord}_6(5) = 2 = \phi(6)$. Therefore, the only primitive element of $\mathbb{Z}_6^*$ is $5$.

Example. What are the primitive elements of $\mathbb{Z}_8^*$?
Here $\mathbb{Z}_8^* = \{1, 3, 5, 7\}$ and $\phi(8) = 4$. Squaring each unit,

$$\begin{align*} 3^2 &= 9 = 1 \text{ in } \mathbb{Z}_8, \\ 5^2 &= 25 = 1 \text{ in } \mathbb{Z}_8, \\ 7^2 &= 49 = 1 \text{ in } \mathbb{Z}_8, \end{align*}$$

so every unit other than $1$ has order $2$, and $\operatorname{ord}_8(1) = 1$; no element has order $\phi(8) = 4$. Therefore, $\mathbb{Z}_8^*$ has no primitive elements. Not every $\mathbb{Z}_n^*$ has a primitive element; never assume one exists without checking.

Primitive Elements as Generators#

Proof. Each power $a^k$ is a product of units and hence a unit, so $\langle a \rangle \subseteq \mathbb{Z}_n^*$. Now suppose two of the listed powers were equal; say $a^i = a^j$ with $0 \leq i < j \leq \phi(n) - 1$. Since $a$ is invertible, we can multiply both sides by $(a^i)^{-1}$ to get

$$\begin{align*} a^{j-i} &= 1, \quad \text{where } 0 < j - i < \phi(n). \end{align*}$$

But $a$ is primitive, so $\operatorname{ord}_n(a) = \phi(n)$; there is no positive exponent smaller than $\phi(n)$ giving $1$, which is a contradiction. Hence the powers $a^0, a^1, \dots, a^{\phi(n)-1}$ are $\phi(n)$ distinct elements of $\mathbb{Z}_n^*$; and since $\mathbb{Z}_n^*$ only has $\phi(n)$ elements in total, the two sets must be equal. $\blacksquare$

Basically, a primitive element generates the whole unit group; every single unit mod $n$ is some power of $a$. This is exactly why primitive elements are so useful: one element single-handedly produces everything.

For example, the first six powers of either primitive element of $\mathbb{Z}_7^*$ sweep out all of $\mathbb{Z}_7^*$; all six units appear in the rows for $3$ and $5$:

Contrast this with $2$, which is not primitive; its powers $2, 4, 1, 2, 4, 1, \dots$ only ever produce $\{1, 2, 4\}$, i.e. $\langle 2 \rangle \neq \mathbb{Z}_7^*$.

Multiplication with Primitive Elements#

In $\mathbb{Z}_p$ for any prime $p$, we can use the fact that the powers of a primitive element generate $\mathbb{Z}_p^*$ to build a method for multiplication in $\mathbb{Z}_p$ that is very time-efficient for very large $p$.

Suppose we know $a$ is a primitive element of $\mathbb{Z}_p^*$ and have recorded the powers of $a$ in a lookup table. Then we can multiply two numbers $x, y \in \mathbb{Z}_p^*$ as follows:

• Use the lookup table to find $i$ and $j$ such that $x = a^i$ and $y = a^j$ in $\mathbb{Z}_p$.
• Calculate $(i + j) \bmod (p-1)$.
• Use the lookup table to find $a^{(i+j) \bmod (p-1)} = xy$ in $\mathbb{Z}_p$.

The reason we reduce the exponent mod $p - 1$ is that $\operatorname{ord}_p(a) = \phi(p) = p - 1$, so by our boxed fact the exponents only matter modulo $p - 1$. The efficiency of this method for large $p$ (and $x,y$) comes from the fact that the only calculation required is addition, which is computationally much cheaper than multiplication; this is basically how logarithm tables worked before calculators, with $i$ playing the role of $\log_a(x)$.

Example. Given the powers of $2$ in $\mathbb{Z}_{11}$, find $5 \times 10$ and $7 \times 9$ in $\mathbb{Z}_{11}$.

For $5 \times 10$: from the table, $5 = 2^4$ and $10 = 2^5$, so

$$\begin{align*} 5 \times 10 &= 2^4 \times 2^5 \\ &= 2^{(4+5) \bmod 10} \\ &= 2^9 \\ &= 6 \text{ in } \mathbb{Z}_{11}. \end{align*}$$

For $7 \times 9$: from the table, $7 = 2^7$ and $9 = 2^6$, so

$$\begin{align*} 7 \times 9 &= 2^7 \times 2^6 \\ &= 2^{13 \bmod 10} \\ &= 2^3 \\ &= 8 \text{ in } \mathbb{Z}_{11}. \end{align*}$$

As a sanity check, $50 = 4 \times 11 + 6$ and $63 = 5 \times 11 + 8$; both answers agree with direct computation.

The lookup table also lets you run this machine in reverse, which is exactly a discrete logarithm.

Example. Find all $x \in \mathbb{Z}$ such that $2^x = 7$ in $\mathbb{Z}_{11}$.
From the table, $2^7 = 7$; and since the powers of $2$ repeat with period $\operatorname{ord}_{11}(2) = 10$, we have $2^x = 2^7$ if and only if $x \equiv 7 \pmod{10}$. Therefore, the solutions are exactly $x \equiv 7 \pmod{10}$.

Example. Solve $x^4 = 5$ in $\mathbb{Z}_{11}$.
Every non-zero element of $\mathbb{Z}_{11}$ is a power of the primitive element $2$, so write $x = 2^t$; from the table $5 = 2^4$. The equation becomes

$$\begin{align*} 2^{4t} &= 2^4 \\ 4t &\equiv 4 \pmod{10} \\ 2t &\equiv 2 \pmod{5} \\ t &\equiv 1 \pmod 5, \end{align*}$$

where we divided the congruence (and the modulus) by $\gcd(4,10) = 2$, then multiplied by the inverse of $2$ mod $5$. So $t \in \{1, 6\}$ modulo $10$, giving

$$\begin{align*} x &= 2^1 = 2, \\ x &= 2^6 = 9 \text{ in } \mathbb{Z}_{11}. \end{align*}$$

Checking: $9^2 = 81 = 4$ and $4^2 = 16 = 5$ in $\mathbb{Z}_{11}$. Therefore, the solutions are $x = 2$ and $x = 9$. Notice how the primitive element converted a nasty power equation into a linear congruence in the exponent; this is the standard trick for equations of the form $x^k = b$ in $\mathbb{Z}_p$.

Which Unit Groups Have Primitive Elements#

We saw that $\mathbb{Z}_8^*$ has no primitive element, so existence is a genuine question. Fortunately there is a complete answer.

The proof of this one is apparently quite complicated so it's omitted for this course; these questions are just pattern matching against the list. In particular, every prime modulus has a primitive root, which is why the multiplication trick above always works in $\mathbb{Z}_p$.

Example. Do each of the following groups of units have primitive elements?

• $\mathbb{Z}_{10}^*$: here $10 = 2 \times 5 = 2p^k$ with $p = 5$, $k = 1$; so yes. (Indeed $3$ works: its powers in $\mathbb{Z}_{10}$ are $3, 9, 7, 1$, so $\operatorname{ord}_{10}(3) = 4 = \phi(10)$.)
• $\mathbb{Z}_{35}^*$: here $35 = 5 \times 7$ is a product of two distinct odd primes, which is not on the list; so no.
• $\mathbb{Z}_{343}^*$: here $343 = 7^3 = p^k$; so yes.

Example. Show directly that $\mathbb{Z}_{12}^*$ has no primitive element.
Since $12 = 2^2 \times 3$ is not of any of the allowed forms, the theorem says no; but it is worth seeing this happen by hand. We have $\mathbb{Z}_{12}^* = \{1, 5, 7, 11\}$ and $\phi(12) = 4$, and

$$\begin{align*} 5^2 &= 25 = 1 \text{ in } \mathbb{Z}_{12}, \\ 7^2 &= 49 = 1 \text{ in } \mathbb{Z}_{12}, \\ 11^2 &= 121 = 1 \text{ in } \mathbb{Z}_{12}, \end{align*}$$

so every unit has order at most $2 < 4$. This is the same behaviour as $\mathbb{Z}_8^*$; everything squares to $1$, so no single element can generate all four units.

Finding a Primitive Element#

In general, there is no known efficient method to find a primitive element of $\mathbb{Z}_n^*$. The method we use (inefficient, but fine by hand) is:

• Choose $a$ to be a small element of $\mathbb{Z}_n^*$, taking candidates from the list of numbers that are not pure powers: $2, 3, 5, 6, 7, 10, 11, \dots$ in order.
• For each prime divisor $p_i$ of $\phi(n)$, compute $a^{\phi(n)/p_i}$ in $\mathbb{Z}_n$.
• If $a^{\phi(n)/p_i} \neq 1$ in $\mathbb{Z}_n$ for all prime divisors $p_i$ of $\phi(n)$, then (and only then) $a$ is a primitive element of $\mathbb{Z}_n^*$.

The reason this works comes back to order dividing the totient. If $\operatorname{ord}_n(a) \neq \phi(n)$, then $\operatorname{ord}_n(a)$ is a proper divisor of $\phi(n)$; its prime factorisation must be missing at least one copy of some prime divisor $p_i$ of $\phi(n)$, so $\operatorname{ord}_n(a) \mid \phi(n)/p_i$, and hence $a^{\phi(n)/p_i} = 1$ by the Lemma. Conversely, if $a$ is primitive then no exponent smaller than $\phi(n)$ can give $1$. So testing just those few exponents $\phi(n)/p_i$ detects primitivity exactly; you never have to check every divisor of $\phi(n)$.

We skip pure powers like $4, 8, 9$ in the candidate list because they can never succeed after their base has failed; if $4 = 2^2$ were primitive, then $\operatorname{ord}_n(2)$ would already have to be $\phi(n)$ (a power of $2$ can't cycle for longer than $2$ does), so $2$ would have been primitive first.

Example. Find a primitive element of $\mathbb{Z}_{31}^*$.
Here $\phi(31) = 30 = 2 \times 3 \times 5$, so the exponents to test are

$$\frac{30}{2} = 15, \quad \frac{30}{3} = 10, \quad \frac{30}{5} = 6.$$

Candidate $a = 2$:

$$\begin{align*} 2^5 &= 32 \\ &= 1 \text{ in } \mathbb{Z}_{31}, \\ 2^{15} &= (2^5)^3 \\ &= 1 \text{ in } \mathbb{Z}_{31}, \end{align*}$$

so $2$ fails the test (in fact $\operatorname{ord}_{31}(2) = 5$) and is not primitive.
Candidate $a = 3$: first note $3^5 = 243 = 7 \times 31 + 26 = 26 = -5$ in $\mathbb{Z}_{31}$, then

$$\begin{align*} 3^6 &= 3^5 \times 3 \\ &= -15 \\ &= 16 \neq 1, \\ 3^{10} &= (3^5)^2 \\ &= (-5)^2 \\ &= 25 \neq 1, \\ 3^{15} &= 3^{10} \times 3^5 \\ &= 25 \times (-5) \\ &= -125 \\ &= -1 \neq 1 \text{ in } \mathbb{Z}_{31}, \end{align*}$$

since $-125 + 4 \times 31 = -1$. All three tests pass; therefore $3$ is a primitive element of $\mathbb{Z}_{31}^*$. Notice how writing $26$ as $-5$ made every one of these computations painless; working with small negative representatives is almost always faster than working with large positive ones.

Finding All Primitive Elements#

Once you have found one primitive element, you get all the others essentially for free.

Proof. Let $g = \gcd(k, \phi(n))$ and let $m = \operatorname{ord}_n(a^k)$. Since $\operatorname{ord}_n(a) = \phi(n)$, the Lemma from earlier gives

$$(a^k)^m = a^{km} = 1 \iff \phi(n) \mid km.$$

Dividing both $\phi(n)$ and $k$ by $g$, this is equivalent to $\frac{\phi(n)}{g} \mid \frac{k}{g}m$; and since $\gcd\!\left(\frac{\phi(n)}{g}, \frac{k}{g}\right) = 1$, this happens exactly when $\frac{\phi(n)}{g} \mid m$. The smallest positive such $m$ is $\frac{\phi(n)}{g}$, so

$$\operatorname{ord}_n(a^k) = \frac{\phi(n)}{\gcd(k, \phi(n))},$$

which equals $\phi(n)$ precisely when $\gcd(k, \phi(n)) = 1$. $\blacksquare$

The exact same argument works with $\phi(n)$ replaced by the order of any unit, giving a formula that is genuinely worth memorising:

$$\boxed{\operatorname{ord}_n(a^k) = \frac{\operatorname{ord}_n(a)}{\gcd(k, \operatorname{ord}_n(a))}.}$$

Basically, raising $a$ to the power $k$ shrinks its cycle by exactly the factor $\gcd(k, \operatorname{ord}_n(a))$; if $k$ shares no factors with the order, the cycle length is untouched.

$$\boxed{\text{If } \mathbb{Z}_n^* \text{ has a primitive element, it has exactly } \phi(\phi(n)) \text{ of them.}}$$

This matches everything we have seen so far: $\mathbb{Z}_6^*$ has $1$ primitive element ($5$) and $\phi(\phi(6)) = \phi(2) = 1$, while $\mathbb{Z}_7^*$ has $2$ primitive elements ($3$ and $5$) and $\phi(\phi(7)) = \phi(6) = 2$.

Example. Given $2$ is a primitive element of $\mathbb{Z}_9^*$, find all the primitive elements of $\mathbb{Z}_9^*$.
Here $\phi(9) = 9 - 3 = 6$, and $\mathbb{Z}_6^* = \{1, 5\}$; so by the corollary, the primitive elements are exactly $2^1$ and $2^5$:

$$\begin{align*} 2^1 &= 2, \\ 2^5 &= 32 \\ &= 3 \times 9 + 5 \\ &= 5 \text{ in } \mathbb{Z}_9. \end{align*}$$

Therefore, the primitive elements of $\mathbb{Z}_9^*$ are $2$ and $5$; as a check, $\phi(\phi(9)) = \phi(6) = 2$ elements, as expected.

Example. Find all primitive elements of $\mathbb{Z}_{31}^*$.
From the previous section, $3$ is a primitive element of $\mathbb{Z}_{31}^*$ and $\phi(31) = 30$. The units mod $30 = 2 \times 3 \times 5$ are the numbers coprime to $2$, $3$ and $5$:

$$\mathbb{Z}_{30}^* = \{1, 7, 11, 13, 17, 19, 23, 29\},$$

which has $\phi(30) = \phi(2)\phi(3)\phi(5) = 1 \times 2 \times 4 = 8$ elements; so there are exactly $8$ primitive elements, namely $3^k$ for each $k \in \mathbb{Z}_{30}^*$. First tabulate the powers of $3$ up to $3^{15} = -1$:

The exponents up to $15$ can be read straight off the table, and since $3^{15} = -1$, every later power is just the negative of an earlier one; $3^{15+j} = -3^j$:

$$\begin{align*} 3^1 &= 3, \\ 3^7 &= 17, \\ 3^{11} &= 13, \\ 3^{13} &= 24, \\ 3^{17} &= -3^2 = -9 = 22, \\ 3^{19} &= -3^4 = -19 = 12, \\ 3^{23} &= -3^8 = -20 = 11, \\ 3^{29} &= -3^{14} = -10 = 21 \text{ in } \mathbb{Z}_{31}. \end{align*}$$

Therefore, the primitive elements of $\mathbb{Z}_{31}^*$ are

$$\{3, 11, 12, 13, 17, 21, 22, 24\},$$

and there are $8 = \phi(\phi(31))$ of them, as expected.

Example. Construct the full order table for $\mathbb{Z}_{13}^*$ and hence find all primitive elements of $\mathbb{Z}_{13}^*$.
The lazy way is to compute the whole $12 \times 12$ power table; the smart way is to find one primitive element and then use the boxed formula for $\operatorname{ord}_n(a^k)$.

First, $\phi(13) = 12 = 2^2 \times 3$, so the prime divisors of $\phi(13)$ are $2$ and $3$ and we test the exponents $\frac{12}{2} = 6$ and $\frac{12}{3} = 4$. Trying $a = 2$:

$$\begin{align*} 2^4 &= 16 \\ &= 3 \neq 1, \\ 2^6 &= 64 \\ &= 12 \\ &= -1 \neq 1 \text{ in } \mathbb{Z}_{13}, \end{align*}$$

so $2$ is a primitive element of $\mathbb{Z}_{13}^*$. Its powers are: