Order & Primitive Roots

Prerequisites: Fermat's little theorem, Euler's theorem, and Lagrange's theorem

Order and primitive roots are important tools for understanding the multiplicative structure of the reduced residue system modulo $m$, $\mathbf Z_m^*$. They provide a basis for defining concepts such as the discrete logarithm. More general discussions can be found in the relevant sections on group theory and ring theory in abstract algebra.

Order

Throughout this section, assume that the modulus $m\in\mathbf N_+$ and the base $a\in\mathbf Z$ are coprime, that is, $(a,m)=1$, also written as $a\perp m$.

For $n\in\mathbf Z$, the powers $a^n\bmod m$ exhibit a cyclic structure. The minimum length of this cycle is the order of $a$ modulo $m$. The order is defined as the exponent at which the power $a^n \bmod m$ first returns to its starting point $a^0\bmod m = 1$:

Order

For $a\in\mathbf Z,m\in\mathbf N_+$ with $a\perp m$, the smallest positive integer satisfying $a^n \equiv 1 \pmod m$, namely $n$, is called $a$ modulo $m$'s order (the order of $a$ modulo $m$), denoted by $\delta_m(a)$ or $\operatorname{ord}_m(a)$.

Note

In abstract algebra, the “order” here is the order of the element in the group formed by the reduced residue system modulo $m$ under multiplication, where that element is $a$. The notation $\delta$ for order is specific to this particular group. Many of the properties below generalize directly to the properties of the order of a group element in abstract algebra.

There is also the concept of “half-order”, denoted by $\delta^-$ in number theory. It is the smallest positive integer satisfying $a^n \equiv -1 \pmod m$. Half-order is not a group-theoretic concept. An order always exists, whereas a half-order need not.

Cyclic structure of powers

The order can be used to characterize the cyclic structure of powers. For $a^n\bmod m$, divide the exponent $n$ by the order $\delta_m(a)$ with remainder:

$$n = \delta_m(a)q + r, ~ 0\le r < \delta_m(a).$$

Then, using the laws of exponents, we obtain

$$a^n = a^{\delta_m(a)q + r} = (a^{\delta_m(a)})^q \cdot a^r \equiv a^r \pmod m.$$

This shows that a power with any exponent can be shifted into the first nonnegative cycle. From this, we obtain a series of properties of order.

Property 1

For $a\in\mathbf Z,m\in\mathbf N_+$ with $a\perp m$, the powers $a^0(=1),a,a^2,\cdots,a^{\delta_m(a)-1}$ are pairwise incongruent modulo $m$.

Proof

Consider a proof by contradiction. Suppose there exist two numbers $0\le i< j<\delta_m(a)$ such that $a^i\equiv a^j\pmod m$. Then $a^{j - i}\equiv 1\pmod m$. However, $0 < j - i < \delta_m(a)$, contradicting the minimality of the order. Thus the proposition holds.

Property 2

For $a,n\in\mathbf Z,m\in\mathbf N_+$ with $a\perp m$, the congruence $a^n \equiv 1 \pmod m$ holds if and only if $\delta_m(a)\mid n$.

Proof

As stated above, $a^{n}\equiv a^{n\bmod\delta_m(a)}\pmod m$. By Property 1, among $0\le r < \delta_m(a)$ the unique value for which $a^r\equiv 1\pmod m$ holds is $r$, namely $r=0$. Therefore, $a^n \equiv 1 \pmod m$ if and only if $n\bmod \delta_m(a) = 0$, that is, $\delta_m(a)\mid n$.

In Euler's theorem, the congruence $a^{\varphi(m)}\equiv 1\pmod m$ holds for every $a\perp m$. Combined with Property 2, this means that for every $a\perp m$, $\delta_m(a)\mid\varphi(m)$. In other words, $\varphi(m)$ is a common multiple of the orders of all $a\perp m$. For a positive integer $m$, the least common multiple of all $a\perp m$ orders $\delta_m(a)$ is denoted by $\lambda(m)$; it is the Carmichael function of $m$. Its properties will be discussed in detail below.

As with other cyclic structures, from the order of $a$ we can calculate the order of $a^k$.

Property 3

For $k,a\in\mathbf Z,m\in\mathbf N_+$ with $a\perp m$, we have

$$\delta_m(a^k) = \dfrac{\delta_m(a)}{(\delta_m(a),k)}.$$

Proof

By Property 2, the congruence $(a^k)^n = a^{kn} \equiv 1\pmod m$ holds if and only if $\delta_m(a) \mid kn$. This condition is equivalent to

$$\dfrac{\delta_m(a)}{\left(\delta_m(a),k\right)} \mid n.$$

The smallest positive integer satisfying this condition is

$$\delta_m(a^k)=\dfrac{\delta_m(a)}{\left(\delta_m(a),k\right)}.$$

Order of a product

Let $a,b$ be distinct integers coprime to $m$. If the orders $\delta_m(a)$ and $\delta_m(b)$ are known, then we can likewise obtain information about the order of their product $ab$, denoted by $\delta_{m}(ab)$.

Property 4

For $a,b\in\mathbf Z,m\in\mathbf N_+$ with $a,b\perp m$, we have

$$\dfrac{[\delta_m(a),\delta_m(b)]}{(\delta_m(a),\delta_m(b))} \mid \delta_m(ab) \mid [\delta_m(a),\delta_m(b)].$$

Proof

Since $[\delta_m(a),\delta_m(b)]$ is a multiple of both $\delta_m(a)$ and $\delta_m(b)$, Property 2 gives

$$(ab)^{[\delta_m(a),\delta_m(b)]} = a^{[\delta_m(a),\delta_m(b)]} b^{[\delta_m(a),\delta_m(b)]} \equiv 1 \pmod m.$$

Applying Property 2 again gives

$$\delta_m(ab) \mid [\delta_m(a),\delta_m(b)].$$

This proves the divisibility relation on the right.

Conversely,

$$1 \equiv (ab)^{\delta_m(ab)\delta_m(b)} \equiv a^{\delta_m(ab)\delta_m(b)} \pmod m,$$

so Property 2 gives $\delta_m(a)\mid\delta_m(ab)\delta_m(b)$. Canceling $(\delta_m(a),\delta_m(b))$ from both sides yields

$$\dfrac{\delta_m(a)}{(\delta_m(a),\delta_m(b))}\mid\delta_m(ab)\dfrac{\delta_m(b)}{(\delta_m(a),\delta_m(b))}.$$

After canceling the common factor, the two fractions are coprime, so

$$\dfrac{\delta_m(a)}{(\delta_m(a),\delta_m(b))}\mid\delta_m(ab).$$

Similarly,

$$\dfrac{\delta_m(b)}{(\delta_m(a),\delta_m(b))}\mid\delta_m(ab).$$

Since the left-hand sides of these two divisibility relations are coprime,

$$\dfrac{[\delta_m(a),\delta_m(b)]}{(\delta_m(a),\delta_m(b))} =\dfrac{\delta_m(a)\delta_m(b)}{(\delta_m(a),\delta_m(b))^2}\mid\delta_m(ab).$$

This proves the divisibility relation on the left.

When the orders of $a$ and $b$ are coprime, this conclusion takes a simpler form.

Property 4'

For $a,b\in\mathbf Z,m\in\mathbf N_+$ with $a,b\perp m$, we have

$$\delta_m(ab) = \delta_m(a)\delta_m(b) \iff \delta_m(a)\perp\delta_m(b).$$

Proof

If $\delta_m(a)\perp\delta_m(b)$, then all the divisibility relations in Property 4 are equalities, so

$$\delta_m(ab) = [\delta_m(a),\delta_m(b)] = \delta_m(a)\delta_m(b).$$

Conversely, if $\delta_m(ab)=\delta_m(a)\delta_m(b)$, then Property 4 gives

$$\delta_m(a)\delta_m(b) = \delta_m(ab) \mid [\delta_m(a),\delta_m(b)].$$

This immediately implies $(\delta_m(a),\delta_m(b))=1$, namely $\delta_m(a)\perp\delta_m(b)$.

In general, the bounds obtained in Property 4 are tight. The lower bound for the order of a product is easy to attain: for example, when $(a,b,m)=(3,5,7)$, $\delta_m(a)=\delta_m(b)=6$, but the order of their product is $\delta_m(ab)=1$.

Although the order of the product $ab$ is not necessarily the least common multiple of their orders in general, it is always possible to find an element whose order equals this least common multiple.

Property 5

For $a,b\in\mathbf Z,m\in\mathbf N_+$ with $a,b\perp m$, there always exists $c\in\mathbf Z$ with $c\perp m$ such that

$$\delta_m(c) = [\delta_m(a),\delta_m(b)].$$

Proof

Consider the prime factorizations:

$$\delta_m(a) = \prod_p p^{\alpha_p},~ \delta_m(b) = \prod_p p^{\beta_p}.$$

According to the relative sizes of $\alpha_p$ and $\beta_p$, divide all prime factors into two classes:

$$A = \{p : \alpha_p \ge \beta_p\}, ~ B = \{p : \alpha_p < \beta_p\}.$$

Define

$$\gamma_A = \prod_{p\in A}p^{\alpha_p},~\gamma_B = \prod_{p\in B}p^{\alpha_p},~\eta_A = \prod_{p\in A}p^{\beta_p},~\eta_B = \prod_{p\in B}p^{\beta_p},$$

so that $\delta_m(a) = \gamma_A\gamma_B$ and $\delta_m(b)=\eta_A\eta_B$. By Property 3,

$$\begin{aligned} \delta_m(a^{\gamma_B}) &= \dfrac{\delta_m(a)}{(\delta_m(a),\gamma_B)} = \dfrac{\delta_m(a)}{\gamma_B} = \gamma_A,\\ \delta_m(b^{\eta_A}) &= \dfrac{\delta_m(b)}{(\delta_m(b),\eta_A)} = \dfrac{\delta_m(b)}{\eta_A} = \eta_B. \end{aligned}$$

Since $\gamma_A\perp\eta_B$, Property 4' gives

$$\delta_m(a^{\gamma_B}b^{\eta_A}) = \gamma_A\eta_B = \prod_p p^{\max\{\alpha_p,\beta_p\}} = [\delta_m(a),\delta_m(b)].$$

Therefore, $c=a^{\gamma_B}b^{\eta_A}$ is an element whose order is $[\delta_m(a),\delta_m(b)]$.

This conclusion is often used to construct an element of a prescribed order.

Primitive roots

Primitive roots are special elements whose order equals the number of elements in the reduced residue system modulo $m$.

Primitive root

For $m\in\mathbf N_+$, if there exists $g\in\mathbf Z$ with $g\perp m$ such that $\delta_m(g)=|\mathbf Z_m^*|=\varphi(m)$, then $g$ is called a primitive root modulo $m$ (primitive root modulo $m$). Here, $\varphi(m)$ is the Euler totient function.

Not every positive integer $m$ has a primitive root modulo $m$. By Property 1 above, if a primitive root modulo $m$, denoted by $g$, exists, then the congruence classes containing $g,g^2,\cdots,g^{\varphi(m)}$ are all distinct and form the reduced residue system modulo $m$. In particular, for a prime $p$, the residues $g^i\bmod p$ are pairwise distinct for $i=1,2,\cdots,p-1$.

Note

In abstract algebra, a primitive root is a generator of a cyclic group. The name “primitive root” is used only for the group formed by the reduced residue system modulo $m$ under multiplication; in a general cyclic group, the term “generator” is used. The group formed by the reduced residue system modulo $m$ under multiplication is not always cyclic: the existence of a primitive root means that it is isomorphic to a cyclic group, while the absence of a primitive root means that it is not.

When the modulus is $1$, the multiplicative group of integers modulo $1$ is $\{0\}$. This is clearly a cyclic group, so its primitive root is $0$.

Primitive-root criterion

If all prime factors of $\varphi(m)$ are known, it is easy to determine whether a primitive root modulo $m$ exists.

Theorem

For an integer $m\ge 3$ and $g\perp m$, $g$ is a primitive root modulo $m$ if and only if, for every prime factor of $\varphi(m)$, denoted by $p$,

$$g^{\frac{\varphi(m)}{p}}\not\equiv 1 \pmod m.$$

Proof

Necessity is clear. To prove sufficiency, use a proof by contradiction. If $g$ is not a primitive root modulo $m$, then $\delta_m(g)< \varphi(m)$. By Property 2 and Euler's theorem, $\delta_m(g)\mid\varphi(m)$. Let $p$ be a prime factor of $\dfrac{\varphi(m)}{\delta_m(g)}$; then $\delta_m(g)\mid\dfrac{\varphi(m)}{p}$. Applying Property 2 again gives

$$g^{\frac{\varphi(m)}{p}} \equiv 1 \pmod m.$$

But $p$ is also a factor of $\varphi(m)$, contradicting the hypothesis. Thus sufficiency holds.

Number of primitive roots

A primitive root, if it exists, need not be unique. In general, the possible orders of elements in the reduced residue system modulo $m$, and the number of elements of each order, satisfy the following theorem:

Theorem

If a positive integer $m$ has a primitive root $g$, then, when $d\mid\varphi(m)$, an element modulo $m$ of order $d$ exists, and there are exactly $\varphi(d)$ such elements. In particular, the number of primitive roots modulo $m$ is $\varphi(\varphi(m))$.

Proof

By the definition of a primitive root, every reduced residue class modulo $m$ can be written as $g^k\bmod m$, where $k$ is one of $1,2,\cdots,\varphi(m)$. By Property 3, the orders of these elements are

$$\delta_m(g^k) = \dfrac{\varphi(m)}{(\varphi(m),k)}.$$

Therefore, an element of order $d$ exists if and only if $d\mid\varphi(m)$. For $d\mid\varphi(m)$, let $d'=\varphi(m)/d$. The set of these elements is

$$\begin{aligned} A &= \{g^k : (\varphi(m),k)=d',~1\le k \le\varphi(m)\} \\ &= \{g^k : d'\mid k,~ (d, k/d') = 1,~ 1 \le k/d' \le d\}. \end{aligned}$$

The corresponding values $k'=k/d'$ are precisely the positive integers no greater than $d$ and coprime to $d$. By the definition of the Euler totient function, there are $\varphi(d)$ of them.

Primitive-root existence theorem

This section establishes the following primitive-root existence theorem:

Theorem

A primitive root modulo $m$ exists if and only if $m=1,2,4,p^e,2p^e$, where $p$ is an odd prime and $e\in\mathbf N_+$.

To explain this result, consider the following four cases:

1. For $m=1,2,4$, primitive roots are respectively $g=0,1,3$, so they clearly exist.

2. $m=p^{e}$ is a power of an odd prime, where $p$ is an odd prime and $e\in\mathbf N_+$.

   ???+ note "Lemma 1" For an odd prime $p$, a primitive root modulo $p$ exists.

   ??? note "Proof" The proof has two steps.

   **Step 1**: For $d\mid(p-1)$, the congruence $x^d\equiv 1\pmod p$ has exactly $d$ distinct solutions.
   
   Let $p-1=kd$, and consider the polynomial
   
   $$
   f(x) = x^{d(k-1)} + x^{d(k-2)} + \cdots + x^d + 1. 
   $$
   
   By [Euler's theorem](/knowledge-pages/math-number-theory-fermat#欧拉定理), the congruence $(x^d-1)f(x)=x^{p-1}-1\equiv 0\pmod{p}$ has exactly $p-1$ distinct solutions. These solutions are zeros of $x^d-1$ and $f(x)$ respectively. By [Lagrange's theorem](/knowledge-pages/math-number-theory-congruence-equation#定理-3lagrange-定理), they can have at most $d$ and $d(k-1)$ distinct zeros, respectively. Since $d+d(k-1)=p-1$, the former must have exactly $d$ distinct zeros. Thus $x^d\equiv 1\pmod p$ has exactly $d$ distinct solutions.
   
   **Step 2**: For $d\mid(p-1)$, the elements of order $d$ number exactly $\varphi(d)$.
   
   Sort all divisors of $\varphi(p)$, and then use induction. Since the only element of order $1$ is $1$, the base case holds. For $d\mid(p-1)$, by [Property 2](#ord-prop-2), every solution of $x^d\equiv 1\pmod p$ satisfies $\delta_p(x)\mid d$. Therefore, the number of elements of order $d$ is
   
   $$
   N(d) = d - \sum_{e\mid d,~e\neq d} N(e) =  d - \sum_{e\mid d,~e\neq d} \varphi(e) = \varphi(d).
   $$
   
   The second equality is the induction hypothesis, and the third is a property of the Euler totient function. By mathematical induction, for every $d\mid(p-1)$ there are exactly $\varphi(d)$ elements of order $d$.
   
   In particular, for $d=p-1$, there are exactly $\varphi(p-1)$ elements of order $(p-1)$. Therefore, a primitive root modulo $p$ exists.
   

   ???+ note "Lemma 2" For an odd prime $p$ and $e \in \mathbf{N}_+$, a primitive root modulo $p^e$ exists.

   ??? note "Proof" The proof has three steps.

   **Step 1**: There exists a primitive root modulo $p$, denoted by $g$, such that $g^{p-1}\not\equiv 1\pmod{p^2}$.
   
   Take any primitive root modulo $p$, denoted by $g$. If it does not satisfy the condition, namely if $g^{p-1}\equiv 1\pmod{p^2}$, then one can show that $g+p$ does satisfy it: $g+p$ is also a primitive root modulo $p$, and
   
   $$
   \begin{aligned}
   (g+p)^{p-1} &\equiv \binom{p-1}{0}g^{p-1} + \binom{p-1}{1}g^{p-2}p \\
   &= g^{p-1} + g^{p-2}p(p-1) \\ 
   &\equiv 1 - pg^{p-2} \not\equiv 1 \pmod{p^2}.
   \end{aligned}
   $$
   
   **Step 2**: For the $g$ chosen above and every $e\ge 1$, $g^{\varphi(p^e)}\not\equiv 1\pmod{p^{e+1}}$.
   
   The choice of $g$ ensures that this holds for $e=1$. Assume it holds for $e$; we prove it for $e+1$. For any $e \ge 1$, Euler's theorem gives a $\lambda$ such that
   
   $$
   g^{\varphi(p^e)} = 1 + \lambda p^e
   $$
   
   holds. By the induction hypothesis, $\lambda\perp p$. Since $\varphi(p^{e+1})=p\varphi(p^e)$,
   
   $$
   g^{\varphi(p^{e+1})} = \left(g^{\varphi(p^{e})}\right)^p = (1 + \lambda p^e)^p \equiv 1 + \lambda p^{e+1} \pmod{p^{e+2}}.
   $$
   
   Together with $\lambda\perp p$, this shows that $g^{\varphi(p^{e+1})}\not\equiv 1\pmod{p^{e+2}}$. The claim follows by induction.
   
   **Step 3**: The chosen $g$, for every $e\ge 1$, is a primitive root modulo $p^e$.
   
   The choice of $g$ ensures the claim for $e=1$. Assume it holds for $e$; we prove it for $e+1$. Abbreviate $\delta_{p^{e+1}}(g)$ as $\delta$. Since $g^\delta\equiv 1\pmod{p^{e+1}}$, we also have $g^\delta\equiv 1\pmod{p^e}$. By the induction hypothesis, $\delta_{p^e}(g) = \varphi(p^e)$. Therefore, by [Property 2](#ord-prop-2), $\varphi(p^e)\mid\delta$. Euler's theorem also gives $\delta\mid\varphi(p^{e+1})$. But $\varphi(p^{e+1})=p\varphi(p^e)$, so there are only two possibilities: $\delta=\varphi(p^e)$ or $\delta=\varphi(p^{e+1})$. The conclusion of Step 2 says that $g^{\varphi(p^e)}\not\equiv 1\pmod{p^{e+1}}$, so the possibility $\delta=\varphi(p^e)$ does not hold. The only possibility is $\delta=\varphi(p^{e+1})$. Thus $g$ is a primitive root modulo $p^{e+1}$. The claim follows for every $e\ge 1$ by induction.
   

3. $m=2p^{e}$, where $p$ is an odd prime and $e\in\mathbf N_+$.

   ???+ note "Lemma 3" For an odd prime $p$ and $e \in \mathbf{N}_+$, a primitive root modulo $2p^e$ exists.

   ??? note "Proof" Let $g$ be a primitive root modulo $p^{e}$. Then $g+p^e$ is also a primitive root modulo $p^{e}$. Exactly one of the two is odd; assume without loss of generality that it is $g$. Clearly, $(g,2p^e)=1$. Let $\delta=\delta_{2p^e}(g)$; we need to prove that $\delta=\varphi(2p^e)$. Euler's theorem gives $\delta\mid\varphi(2p^e)$. On the other hand, by definition $g^\delta\equiv 1\pmod{2p^e}$, so $g^\delta\equiv 1\pmod{p^e}$. Thus, by Property 2 and the choice of $g$, $\delta_{p^e}(g)=\varphi(p^e)\mid \delta$. From the formula for the Euler totient function, $\varphi(2p^e) = \varphi(p^e)$. Hence, $\delta=\delta_{2p^e}(g)=\varphi(p^e)$, showing that $\delta$ is the order of a primitive root modulo $2p^e$.

4. $m\ne 1,2,4,p^{e},2p^{e}$, where $p$ is an odd prime and $e\in\mathbf N_+$.

   ???+ note "Lemma 4" Suppose $m\neq 1,2,4$ and there are no odd prime $p$ and positive integer $e$ such that $m=p^e$ or $m=2p^e$. Then no primitive root modulo $m$ exists.

   ??? note "Proof" For $m=2^e$ with $e\ge 3$, suppose that modulo $m$ there exists a primitive root $g$. Since $g\perp m$, it must be odd. Write $g=2k+1$ with $k\in\mathbf N$. Then

   $$
   \begin{aligned}
   g^{2^{e-2}}
   &=(2k+1)^{2^{e-2}} \\
   &\equiv 1 + \binom{2^{e-2}}{1}(2k) + \binom{{2^{e-2}}}{2}(2k)^2 \\
   &= 1 + 2^{e-1}k + 2^{e-1}(2^{e-2}-1)k^2 \\
   &= 1 + 2^{e-1}(k + (2^{e-2}-1)k^2) \\
   &\equiv 1 \pmod{2^{e}}.
   \end{aligned}
   $$
   
   In the penultimate line, $k$ and $(2^{e-2}-1)k^2$ have the same parity, so their sum is even. By the definition of order, $\delta_{2^{e}}(g)\le 2^{e-2}< \varphi(2^{e}) = 2^{e-1}$, contradicting the assumption that $g$ is a primitive root. Thus no such primitive root exists.
   
   Now suppose that $m$ satisfies the stated conditions but is not a power of $2$. Then there must exist $2 < m_1 < m_2$ with $m_1\perp m_2$ such that $m=m_1m_2$. Suppose that a primitive root modulo $m$, denoted by $g$, exists. Since $g\perp m$, for $i=1,2$ we have $g\perp m_i$. Euler's theorem gives
   
   $$
   g^{\varphi(m_i)} \equiv 1 \pmod{m_i}.
   $$
   
   Since $m_i > 2$, $\varphi(m_i)$ is even, so for $i=1,2$,
   
   $$
   g^{\frac{1}{2}\varphi(m_1)\varphi(m_2)} \equiv 1 \pmod{m_i}.
   $$
   
   By the [Chinese remainder theorem](/knowledge-pages/math-number-theory-crt),
   
   $$
   g^{\frac{1}{2}\varphi(m_1)\varphi(m_2)} \equiv 1 \pmod{m}.
   $$
   
   Since $\varphi(m)=\varphi(m_1)\varphi(m_2)$, the definition of order gives
   
   $$
   \delta_m(g) \le \frac{1}{2}\varphi(m_1)\varphi(m_2) = \dfrac{1}{2}\varphi(m) < \varphi(m).
   $$
   
   This contradicts the assumption that $g$ is a primitive root modulo $m$. Therefore, by contradiction, no primitive root modulo $m$ exists.
   

Combining these four lemmas gives the necessary and sufficient condition for a number to have a primitive root.

Algorithm for finding a primitive root

For any modulus $m$ that has a primitive root, finding a primitive root $g$ only requires enumerating possible positive integers and checking them one by one. There are usually two ways to enumerate them: enumerate in increasing order, or generate positive integers at random. These two approaches have comparable practical efficiency.

Enumerating in increasing order yields the smallest primitive root modulo $m$, denoted by $g_m$. Therefore, the complexity of the enumeration depends on the size of $g_m$. The following estimates are known:

• Upper bound: Wang¹ and Burgess² proved that the least primitive root of a prime $p$ satisfies $g_p=O\left(p^{0.25+\epsilon}\right)$, where $\epsilon>0$. Cohen, Odoni, and Stothers³ and Elliott and Murata⁴ proved that this estimate also holds for the moduli $p^2$ and $2p^2$, respectively, where $p$ is an odd prime. Since for $e>2$, a primitive root modulo $p^2$ (or $2p^2$) is also a primitive root modulo $p^e$ (or $2p^e$), the upper bound $O\left(p^{0.25+\epsilon}\right)$ for the least primitive root holds in all cases.
• Lower bound: Fridlander⁵ and Salié⁶ proved that there is a $C>0$ such that, for infinitely many primes $p$, the least primitive root satisfies $g_p > C\log p$.
• Average case: Burgess and Elliott⁷ proved that, on average, the least primitive root of a prime $p$ satisfies $g_p=O((\log p)^2(\log\log p)^4)$. Elliott and Murata⁸ further conjectured that the average value of the least primitive root of a prime $p$ is a constant, and numerical verification⁹ suggests that it is approximately $4.926$. Elliott and Murata⁴ later extended this conjecture to the case of the modulus $2p^2$.

According to these estimates, when the least primitive root is sought by brute force, the enumeration complexity $O(g_m(\log m)^2)$ is acceptable.

In addition to enumerating in increasing order, one can search for a primitive root by randomly generating positive integers and checking them. Primitive roots are not particularly sparse:¹⁰

$$\dfrac{\varphi(\varphi(m))}{m} = \Omega\left(\dfrac{1}{\log\log m}\right).$$

Therefore, when the random method is used, the expected complexity of the enumeration is $O((\log m)^2\log\log m)$.

It should be noted that testing whether an integer is a primitive root requires the prime factorization of $\varphi(m)$. Among the common prime-factorization algorithms in programming contests, even the asymptotically fastest Pollard Rho algorithm requires $O(m^{1/4+\varepsilon})$ time. Thus, whenever the prime factorization of $\varphi(m)$ is unknown, the bottleneck in finding a primitive root, regardless of the enumeration method, is factorization rather than enumeration and verification.

Carmichael function

In contrast to the local concept of the order of an element modulo $m$, the Carmichael function is a global concept. It is the least common cycle length of the powers of all integers coprime to $m$.

Carmichael function

For $m\in\mathbf N_+$, define $\lambda(m)$ to be the smallest positive integer satisfying $a^n\equiv 1\pmod m$ for every $a\perp m$; this integer is $n$. The function $\lambda:\mathbf N_+\to\mathbf N_+$ is called the Carmichael function.

By Property 2, having $a^n\equiv 1\pmod m$ for every $a\perp m$ means that $\delta_m(a)\mid n$ for every $a\perp m$. In other words, every positive integer $n$ satisfying this condition is a common multiple of all the $\delta_m(a)$. Therefore, the smallest such $n$ is their least common multiple:

$$\lambda(m) = \operatorname{lcm}\{\delta_m(a) : a\perp m\}.$$

This is also commonly used as an equivalent definition of the Carmichael function.

Repeated application of Property 5 shows that there is always an element $a\perp m$ with $\delta_m(a)=\lambda(m)$. Therefore, the formula can also be written as

$$\lambda(m) = \max\{\delta_m(a) : a\perp m\}.$$

The element $a\perp m$ attaining this maximum is also called a primitive root modulo $m$ with $\lambda$-order. Such an element exists for every modulus $m$.

Recurrence formula

The Carmichael function is an arithmetic function. This section discusses one of its recurrence formulas and uses it to give another proof of the primitive-root existence theorem.

Although it is not a multiplicative function, the Carmichael function can likewise be computed by handling coprime factors separately.

Lemma

For coprime positive integers $m_1,m_2$, $\lambda(m_1m_2)=[\lambda(m_1),\lambda(m_2)]$.

Proof

Let $a_1$ and $a_2$ be primitive roots modulo $m_1$ and $m_2$, respectively, attaining the corresponding $\lambda$ values. Let $m=m_1m_2$. By the Chinese remainder theorem, there is an $a\perp m$ such that $a\equiv a_i\pmod{m_i}$ for $i=1,2$. Since $a^{\lambda(m)}\equiv 1\pmod m$, for $i=1,2$, we have $a_i^{\lambda(m)} \equiv 1\pmod{m_i}$. Thus, by Property 2 and the choice of $a_i$, $\lambda(m_i)=\delta_{m_i}(a_i)\mid \lambda(m)$. Hence $[\lambda(m_1),\lambda(m_2)]\mid\lambda(m)$.

Conversely, for every $a\perp m$ and $i=1,2$, $a^{[\lambda(m_1),\lambda(m_2)]} \equiv 1 \pmod{m_i}$. Applying the Chinese remainder theorem gives $a^{[\lambda(m_1),\lambda(m_2)]} \equiv 1 \pmod{m}$ for every $a\perp m$. By the definition of the Carmichael function, $\lambda(m)\mid [\lambda(m_1),\lambda(m_2)]$.

Thus the equality in the lemma holds.

It remains to calculate the value of the Carmichael function at prime powers. First consider powers of $2$.

Lemma

For $m=2^e$ with $e\in\mathbf N_+$, $\lambda(2)=1$, $\lambda(4)=2$, and for every $e\ge 3$, $\lambda(m)=2^{e-2}$.

Proof

For $m=2,4$, the cases can be handled separately. For $m=2^e$ with $e\ge 3$, repeat the first part of the proof of Lemma 4 above to obtain $\lambda(m)\le 2^{e-2}$. It remains to prove that an element of order $2^{e-2}$ exists. For this,

$$5^{2^{e-3}} = (1 + 2^2)^{2^{e-3}} = 1 + 2^2\times 2^{e-3} = 1 + 2^{e-1} \not\equiv 1 \pmod{2^e}.$$

This shows that $\delta_m(5)\nmid 2^{e-3}$. Since $\delta_m(5) \mid 2^{e-2}$, $5$ must be an element of order $2^{e-2}$. Hence $\lambda(m)=2^{e-2}$.

The proof of this lemma in fact gives a description of the structure of the reduced residue system modulo $2^e$:

Corollary

Let the modulus be $2^e$ with $e \ge 2$. Then every odd integer is congruent to a unique integer of the form $\pm 5^k$, where $k\in\mathbf N$ and $k < 2^{e-2}$. In other words, $\pm 1,\pm 5,\cdots,\pm 5^{2^{e-2}-1}$ are pairwise incongruent and form a reduced residue system.

Proof

The case $e=2$ is easy to verify. For $e \ge 3$, the proof above has already shown that the order of $5$ modulo $2^e$ is $2^{e-2}$, so $1,5,\cdots,5^{2^{e-2}-1}$ are pairwise incongruent. Since these integers are all congruent modulo $4$ to $1$, while their negatives are congruent modulo $4$ to $3$, the numbers $\pm 1,\pm 5,\cdots,\pm 5^{2^{e-2}-1}$ are pairwise incongruent modulo $2^e$. There are $2^{e-1}$ of them, exactly the size of the reduced residue system modulo $2^{e}$, so they form the reduced residue system itself.

Next consider odd prime powers.

Lemma

For $m=p^e$, where $p$ is an odd prime and $e\in\mathbf N_+$, $\lambda(m)=p^{e-1}(p-1)$.

Proof

First prove the claim for $e=1$, namely for the case where $m=p$ is an odd prime. By the definition of the Carmichael function, all integers coprime to $p$, denoted by $a$, are solutions of $x^{\lambda(p)}\equiv 1\pmod{p}$. In the sense of modulo $p$, this equation has $p-1$ distinct solutions. By Lagrange's theorem, $p-1\le\lambda(p)$. On the other hand, Euler's theorem requires $\lambda(p)\mid\varphi(p)=p-1$. Therefore, $\lambda(p)=p-1$.

For $m=p^e$ with $e> 1$, start by proving that $1+p$ is an element of order $p^{e-1}$. We have

$$(1+p)^{p^{e-1}} \equiv 1,\quad (1+p)^{p^{e-2}} \equiv 1 + p^{e-1} \not\equiv 1 \pmod{p^e}.$$

Hence $\delta_m(1+p)=p^{e-1}$. Also, let a primitive root modulo $p$, denoted by $g$, be given. Since $g^{\delta_m(g)}\equiv 1 \pmod{p}$, Property 2 gives $p-1\mid\delta_m(p)$. By the definition of the Carmichael function and Euler's theorem,

$$p^{e-1}(p-1) = [\delta_m(p),p^{e-1}]\mid\lambda(m) \mid \varphi(m) = p^{e-1}(p-1).$$

Therefore, $\lambda(m)=p^{e-1}(p-1)$.

Summarizing the results of this section gives the recurrence formula for the Carmichael function:

Theorem

For every positive integer $m$,

$$\lambda(m) = \begin{cases} \varphi(m), & \text{if }m=1,2,4,p^e\text{ for odd prime }p\text{ and }e \ge 1,\\ \frac{1}{2}\varphi(m), &\text{if }m=2^e,~e\ge 3,\\ \operatorname{lcm}\{\lambda(p_1^{e_1}),\lambda(p_2^{e_2}),\cdots,\lambda(p_s^{e_s})\}, &\text{if }m = p_1^{e_1}p_2^{e_2}\cdots p_s^{e_s}\text{ for distinct }p_1,p_2,\cdots,p_s. \end{cases}$$

Using this recurrence formula strengthens the preceding result:

Corollary

For positive integers $m_1,m_2$, $\lambda([m_1,m_2])=[\lambda(m_1),\lambda(m_2)]$.

Comparing the definitions of a primitive root and the Carmichael function shows that a primitive root modulo $m$ exists if and only if $\lambda(m)=\varphi(m)$. The recurrence formula for the Carmichael function readily yields the following result by induction:

Corollary

A primitive root modulo $m$ exists if and only if $m=1,2,4,p^e,2p^e$, where $p$ is an odd prime and $e\in\mathbf N_+$.

Since the proof of the recurrence formula in this section did not use the primitive-root existence theorem, this gives another proof of that theorem.

Carmichael numbers

The Carmichael function can be used to study the properties and distribution of Carmichael numbers (OEIS:A002997). These are composite numbers that Fermat primality testing can never correctly reject.

Carmichael number

For a composite number $n$, if for every integer $a\perp n$ the congruence $a^{n-1} \equiv 1 \pmod n$ holds, that number $n$ is called a Carmichael number.

The smallest Carmichael number is $561 = 3 \times 11 \times 17$.

By the definition of the Carmichael function, a composite number $n$ is a Carmichael number if and only if $\lambda(n)\mid n-1$, where $\lambda(n)$ is the Carmichael function. This gives the following test for whether a composite number $n$ is a Carmichael number:

Korselt's criterion¹¹

A composite number $n$ is a Carmichael number if and only if $n$ is square-free and, for each prime factor of $n$, denoted by $p$, $(p-1) \mid (n-1)$.

Proof

First prove necessity. Suppose $\lambda(n)\mid (n-1)$. Examining the recurrence formula for the Carmichael function shows that if $n$ has a squared prime factor $p$, then $p\mid \lambda(n)$. But $p\nmid (n-1)$, a contradiction. Similarly, the recurrence formula shows that $(p-1)\mid \lambda(n)$, and hence $(p-1) \mid (n-1)$.

Now prove sufficiency. Since $n$ is composite, it has an odd prime factor $p$, so $n-1$ is even and $n$ must be odd. For an odd square-free composite number $n$, the recurrence formula for the Carmichael function gives $\lambda(n)=\operatorname{lcm}\{p-1:p\mid n\}$. Therefore, if $(p-1) \mid (n-1)$ holds for every prime factor $p$, then $\lambda(n)\mid (n-1)$.

This criterion gives several simple properties of Carmichael numbers:

Corollary

Carmichael numbers are odd, square-free, and have at least $3$ distinct prime factors.

Proof

The first two properties follow directly from Korselt's criterion and its proof. For the third, it suffices to show that the product of two distinct primes $p_1,p_2$, $n=p_1p_2$ cannot be a Carmichael number. Suppose $n=p_1p_2$ is a Carmichael number. By Korselt's criterion, $(p_i-1)\mid (n-1)$. But

$$n-1=p_1p_2-1\equiv p_2-1 \pmod{p_1-1}.$$

Therefore, $(p_1-1)\mid(p_2-1)$. Similarly, $(p_2-1)\mid(p_1-1)$. Hence $p_1=p_2$, contradicting the assumption. Thus a Carmichael number $n$ has at least $3$ distinct prime factors.

Analytic number theory also gives properties of the distribution of Carmichael numbers. Let $C(n)$ be the number of Carmichael numbers less than or equal to $n$. Alford, Granville, and Pomerance¹² proved that, for sufficiently large $n$, $C(n)>n^{2/7}$. Thus there are infinitely many Carmichael numbers. Earlier, Erdős¹³ had proved that $C(n) < n\exp\left(-c\dfrac{\ln n\ln\ln\ln n}{\ln\ln n}\right)$, where $c$ is a constant. Thus Carmichael numbers are quite sparse in distribution (relative to primes). In fact, ¹⁴ $C(10^9)=646$, $C(10^{18})=1~401~644$.

References and notes

• Primitive root modulo n - Wikipedia
• The order of a unit - Course Notes
• The primitive root theorem - Amin Witno's notes
• Carmichael function - Wikipedia
• Carmichael's Lambda Function - Brilliant Math & Science Wiki
• Carmichael number - Wikipedia
• Carmichael Number - Wolfram MathWorld

Footnotes

1. Wang Y. "On the least primitive root of a prime." (in Chinese). Acta Math Sinica, 1959, 4: 432–441; English transl. inSci. Sinica, 1961, 10: 1–14. ↩

2. BURGESS, David A. "On character sums and primitive roots." Proceedings of the London Mathematical Society, 1962, 3.1: 179-192. ↩

3. Cohen, S. D., R. W. K. Odoni, and W. W. Stothers. "On the least primitive root modulo p 2." Bulletin of the London Mathematical Society 6, no. 1 (1974): 42-46. ↩

4. Elliott, P. D. T. A., and L. Murata. "The least primitive root mod 2p2." Mathematika 45, no. 2 (1998): 371-379. ↩ ↩²

5. FRIDLENDER, V. R. "On the least n-th power non-residue." Dokl. Akad. Nauk SSSR. 1949. p. 351-352. ↩

6. SALIÉ, Hans. "Über den kleinsten positiven quadratischen Nichtrest nach einer Primzahl." Mathematische Nachrichten, 1949, 3.1: 7-8. ↩

7. Burgess, D. A., and P. D. T. A. Elliott. "The average of the least primitive root." Mathematika 15, no. 1 (1968): 39-50. ↩

8. Elliott, Peter DTA, and Leo Murata. "On the average of the least primitive root modulo p." Journal of The london Mathematical Society 56, no. 3 (1997): 435-454. ↩

9. More results can be found in Least prime primitive root of prime numbers. ↩

10. If a primitive root modulo $m$ exists, then $\varphi(m)\ge\dfrac{1}{3}m$, with equality only when $m=2\times 3^e~(e\in\mathbf N_+)$. Furthermore, when $m > 2$, the Euler totient function $\varphi(m)$ satisfies $\varphi(m)>\dfrac{m}{e^{\gamma}\log\log m+\frac{3}{\log\log m}}$. Combining these two estimates gives the expression in the text. For this estimate of the Euler totient function, see Rosser, J. Barkley, and Lowell Schoenfeld. "Approximate formulas for some functions of prime numbers." Illinois Journal of Mathematics 6, no. 1 (1962): 64-94. ↩

11. Korselt, A. R. (1899). "Problème chinois." L'Intermédiaire des Mathématiciens. 6: 142–143. ↩

12. W. R. Alford; Andrew Granville; Carl Pomerance (1994). "There are Infinitely Many Carmichael Numbers." Annals of Mathematics. 140 (3): 703–722. ↩

13. Erdős, P. (1956). "On pseudoprimes and Carmichael numbers." Publ. Math. Debrecen. 4 (3–4): 201–206. ↩

14. PINCH, Richard GE. The Carmichael numbers up to ${10}^{20}$. ↩