Order & Primitive Root

Order and primitive roots are important tools for understanding the multiplicative structure of the reduced residue system modulo $m$, $\mathbf Z_m^*$. Based on these, concepts such as discrete logarithm can be defined. More general discussions can be found in the abstract algebra sections on Group Theory and Ring Theory.

Order

In this section, we always assume that the modulus $m\in\mathbf N_+$ and the base $a\in\mathbf Z$ are coprime, i.e., $(a,m)=1$, also denoted as $a\perp m$.

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

Order

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

Note

In Abstract Algebra, this "order" is the order of the element $a$ in the multiplicative group formed by the reduced residue system modulo $m$. The notation $\delta$ for order is specific to this particular group. Many properties below can be directly generalized to the order of group elements in abstract algebra.

There is also the concept of "semi-order", denoted by $\delta^-$ in number theory. It is the smallest positive integer satisfying the congruence $a^n \equiv -1 \pmod m$. Semi-order is not a concept in group theory. Order always exists, while semi-order may not.

Cyclic Structure of Powers

Using order, we can describe the cyclic structure of powers. For the power $a^n\bmod m$, we can perform division with remainder on the exponent $n$ by the order $\delta_m(a)$:

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

Then, using the laws of exponentiation, 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 for any power, we can shift it to the first non-negative cycle. From this, we can derive a series of properties about order.

Property 1

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

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)$. This contradicts the minimality of order, so the original statement holds.

Property 2

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

Proof

As mentioned earlier, $a^{n}\equiv a^{n\bmod\delta_m(a)}\pmod m$. By Property 1, the only $r$ with $0\le r < \delta_m(a)$ such that $a^r\equiv 1\pmod m$ is $r=0$. Therefore, $a^n \equiv 1 \pmod m$ if and only if $n\bmod \delta_m(a) = 0$, i.e., $\delta_m(a)\mid n$.

In Euler's Theorem, the congruence $a^{\varphi(m)}\equiv 1\pmod m$ holds for all $a\perp m$. Combined with Property 2, this shows that for all $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 the orders $\delta_m(a)$ of all $a\perp m$ is denoted $\lambda(m)$, which is the Carmichael function of $m$. Its properties will be discussed in detail later.

Similar to other cyclic structures, we can compute the order of $a^k$ from the order of $a$.

Property 3

For $k,a\in\mathbf Z,m\in\mathbf N_+$ and $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 Products

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

Property 4

For $a,b\in\mathbf Z,m\in\mathbf N_+$ and $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 $\delta_m(a)$ and $\delta_m(b)$, by Property 2, we have

\[ (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, we get

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

This gives the divisibility relation on the right.

Conversely, since

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

applying Property 2, we get $\delta_m(a)\mid\delta_m(ab)\delta_m(b)$. Canceling $(\delta_m(a),\delta_m(b))$ from both sides, we obtain

\[ \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 common factors, the two fractions are coprime, so we have

\[ \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, we have

\[ \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 gives the divisibility relation on the left.

When the orders of $a$ and $b$ are coprime, this result has a simpler form.

Property 4'

For $a,b\in\mathbf Z,m\in\mathbf N_+$ and $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 divisibility relations in Property 4 become 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 by Property 4,

\[ \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$, i.e., $\delta_m(a)\perp\delta_m(b)$.

In the general case, the bounds given by Property 4 are already tight. It is easy to construct examples where the order of the product attains the lower bound: e.g., for $(a,b,m)=(3,5,7)$, $\delta_m(a)=\delta_m(b)=6$, but the order of their product $\delta_m(ab)=1$.

Although in general the order of $ab$ may not be the least common multiple of their orders, we can always find an element whose order equals this least common multiple.

Property 5

For $a,b\in\mathbf Z,m\in\mathbf N_+$ and $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 prime factorizations:

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

Using the sizes of $\alpha_p$ and $\beta_p$, we can divide all prime factors into two categories:

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

Accordingly, set

\[ \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$, by Property 4', we have

\[ \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 of order $[\delta_m(a),\delta_m(b)]$.

This result is often used to construct elements of specified order.

Primitive Roots

Primitive roots are special elements—their order equals the size of 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$. Here, $\varphi(m)$ is the Euler totient function.

Not all positive integers $m$ have a primitive root modulo $m$. By Property 1, if a primitive root $g$ modulo $m$ exists, then the residue classes of $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. This concept is called "primitive root" only in the multiplicative group formed by the reduced residue system modulo $m$. In general cyclic groups, it is called a "generator". Not every multiplicative group of the reduced residue system modulo $m$ is cyclic. The existence of a primitive root indicates it is isomorphic to a cyclic group; if no primitive root exists, it is not isomorphic.

When the modulus is $1$, the multiplicative group modulo $1$ is $\{0\}$. This is clearly a cyclic group, so the 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 integer $m\ge 3$ and $g\perp m$, $g$ is a primitive root modulo $m$ if and only if for every prime factor $p$ of $\varphi(m)$,

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

Proof

Necessity is obvious. For sufficiency, we use 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, we get

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

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

Number of Primitive Roots

If primitive roots exist, they may not be unique. Generally, for all possible orders of elements in the reduced residue system modulo $m$ and the number of elements of a given order, we have the following result:

Theorem

If a positive integer $m$ has a primitive root $g$, then an element of order $d$ modulo $m$ exists if and only if $d\mid\varphi(m)$, 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 primitive root, all reduced residue classes modulo $m$ can be written as $g^k\bmod m$, with $k$ being one of $1,2,\cdots,\varphi(m)$. By Property 3, the order of these elements is

\[ \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)$. Moreover, 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 $k'=k/d'$ are exactly the positive integers not exceeding $d$ and coprime to $d$. By the definition of Euler's totient function, there are $\varphi(d)$ such elements.

Existence Theorem for Primitive Roots

This section establishes the following existence theorem for primitive roots:

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 prove this, we discuss the following four cases separately:

$m=1,2,4$. Primitive roots are $g=0,1,3$, respectively, which obviously exist.
$m=p^{e}$ is a power of an odd prime, where $p$ is an odd prime and $e\in\mathbf N_+$.

Lemma 1

For an odd prime $p$, a primitive root modulo $p$ exists.

Proof

The proof is in 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$. Consider the polynomial

\[ f(x) = x^{d(k-1)} + x^{d(k-2)} + \cdots + x^d + 1. \]

By Euler's Theorem, 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)$. By Lagrange's Theorem, 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. This shows that $x^d\equiv 1\pmod p$ has exactly $d$ distinct solutions.

Step 2: For $d\mid(p-1)$, there are exactly $\varphi(d)$ elements of order $d$.

Order all divisors of $\varphi(p)$ and use induction. Since the only element of order $1$ is $1$, the base case holds. For $d\mid(p-1)$, by Property 2, solutions to $x^d\equiv 1\pmod p$ satisfy $\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 by the induction hypothesis, and the third is a property of Euler's totient function. By induction, for all $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.

Lemma 2

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

Proof

The proof is in three steps.

Step 1: There exists a primitive root $g$ modulo $p$ such that $g^{p-1}\not\equiv 1\pmod{p^2}$.

Take any primitive root $g$ modulo $p$. If it does not satisfy the condition, i.e., $g^{p-1}\equiv 1\pmod{p^2}$, then we can show that $g+p$ satisfies the condition: $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, for any $e\ge 1$, we have $g^{\varphi(p^e)}\not\equiv 1\pmod{p^{e+1}}$.

The choice of $g$ ensures this holds for $e=1$. Assume it holds for $e$. We prove it for $e+1$. For any $e \ge 1$, by Euler's theorem, there exists $\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)$, we have

\[ 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}}. \]

Since $\lambda\perp p$, we have $g^{\varphi(p^{e+1})}\not\equiv 1\pmod{p^{e+2}}$. By induction, the statement holds.

Step 3: For the $g$ chosen above, for any $e\ge 1$, $g$ is a primitive root modulo $p^e$.

The choice of $g$ ensures the statement holds for $e=1$. Assume it holds for $e$. We prove it for $e+1$. Denote $\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, we have $\varphi(p^e)\mid\delta$. Also, by Euler's theorem, $\delta\mid\varphi(p^{e+1})$. But $\varphi(p^{e+1})=p\varphi(p^e)$. Thus, there are only two possibilities: $\delta=\varphi(p^e)$ or $\delta=\varphi(p^{e+1})$. However, Step 2 shows that $g^{\varphi(p^e)}\not\equiv 1\pmod{p^{e+1}}$. Therefore, $\delta=\varphi(p^e)$ is impossible. The only possibility is $\delta=\varphi(p^{e+1})$. This shows $g$ is a primitive root modulo $p^{e+1}$. By induction, the statement holds for all $e\ge 1$.
$m=2p^{e}$, where $p$ is an odd prime and $e\in\mathbf N_+$.

Lemma 3

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

Proof

Let $g$ be a primitive root modulo $p^{e}$. Then $g+p^e$ is also a primitive root modulo $p^{e}$. One of them must be odd; assume it is $g$. Clearly, $(g,2p^e)=1$. Let $\delta=\delta_{2p^e}(g)$. We need to show $\delta=\varphi(2p^e)$. By Euler's theorem, $\delta\mid\varphi(2p^e)$. Also, by definition $g^\delta\equiv 1\pmod{2p^e}$, so $g^\delta\equiv 1\pmod{p^e}$. Therefore, by Property 2 and the choice of $g$, $\delta_{p^e}(g)=\varphi(p^e)\mid \delta$. From the expression for Euler's totient function, $\varphi(2p^e) = \varphi(p^e)$. Thus, $\delta=\delta_{2p^e}(g)=\varphi(p^e)$. This shows $\delta$ is a primitive root modulo $2p^e$.
$m\ne 1,2,4,p^{e},2p^{e}$, where $p$ is an odd prime and $e\in\mathbf N_+$.

Lemma 4

Assume $m\neq 1,2,4$ and there is no odd prime $p$ and positive integer $e$ such that $m=p^e$ or $m=2p^e$. Then no primitive root modulo $m$ exists.

Proof

For $m=2^e$ with $e\ge 3$, suppose a primitive root $g$ modulo $m$ exists. Since $g\perp m$, it must be odd. Let $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 second last line, since $k$ and $(2^{e-2}-1)k^2$ have the same parity, their sum is even. By the definition of order, $\delta_{2^{e}}(g)\le 2^{e-2}< \varphi(2^{e}) = 2^{e-1}$. This contradicts the assumption that $g$ is a primitive root. By contradiction, such a primitive root does not exist.

Assume $m$ satisfies the given conditions and is not a power of $2$. Then there exist $2 < m_1 < m_2$ with $m_1\perp m_2$ such that $m=m_1m_2$. Suppose a primitive root $g$ modulo $m$ exists. Since $g\perp m$, for $i=1,2$, we have $g\perp m_i$. By Euler's theorem,

\[ 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,

\[ g^{\frac{1}{2}\varphi(m_1)\varphi(m_2)} \equiv 1 \pmod{m}. \]

Since $\varphi(m)=\varphi(m_1)\varphi(m_2)$, by the definition of order,

\[ \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$. By contradiction, no primitive root modulo $m$ exists.

Combining these four lemmas, we have given a necessary and sufficient condition for a number to have a primitive root.

Algorithm for Finding Primitive Roots

For any modulus $m$ that has a primitive root, to find a primitive root $g$, we only need to enumerate possible positive integers and check each one. There are two common approaches: enumerating from small to large, or randomly generating positive integers. Both are practically efficient.

When enumerating from small to large, we obtain the smallest primitive root $g_m$ modulo $m$. Thus, the complexity of enumeration depends on the size of $g_m$. We have the following estimates:

Upper bound: Wang Yuan[^yuan1959note] and Burgess[^burgess1962character] proved that for a prime $p$, the smallest primitive root $g_p=O\left(p^{0.25+\epsilon}\right)$, where $\epsilon>0$. Cohen, Odoni, and Stothers[^cohen1974least] and Elliott and Murata[^elliott1998least] proved that this estimate also holds for moduli $p^2$ and $2p^2$, 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)$ holds for all cases.
Lower bound: Fridlander[^fridlender1949least] and Salié[^salie1949kleinsten] proved that there exists $C>0$ such that for infinitely many primes $p$, the smallest primitive root $g_p > C\log p$.
Average case: Burgess and Elliott[^burgess1968average] proved that on average, the smallest primitive root $g_p$ for a prime $p$ is $O((\log p)^2(\log\log p)^4)$. Elliott and Murata[^elliott1997average] further conjectured that the average smallest primitive root for primes $p$ is a constant, approximately $4.926$ based on numerical evidence[^more-evidence]. Later, Elliott and Murata[^elliott1998least] extended this conjecture to moduli $2p^2$.

Based on these analyses, the complexity $O(g_m(\log m)^2)$ for brute-force search of the smallest primitive root is acceptable.

Besides enumerating from small to large, we can also find primitive roots by randomly generating positive integers and verifying them. The density of primitive roots is not low:[^density-prim-root]

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

Thus, the expected complexity of the enumeration part using random methods is $O((\log m)^2\log\log m)$.

Note that to test for primitive roots, we need the prime factorization of $\varphi(m)$. In competitive programming, the optimal complexity algorithm for prime factorization is Pollard Rho, which takes $O(m^{1/4+\varepsilon})$ time. Therefore, as long as the prime factorization of $\varphi(m)$ is unknown, regardless of the enumeration method, the bottleneck in finding primitive roots is the factorization step, not the enumeration and verification part.

Carmichael Function

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

Carmichael Function

For $m\in\mathbf N_+$, define $\lambda(m)$ as the smallest positive integer $n$ such that the congruence $a^n\equiv 1\pmod m$ holds for all $a\perp m$. The function $\lambda:\mathbf N_+\to\mathbf N_+$ is called the Carmichael function.

By Property 2, having $a^n\equiv 1\pmod m$ for all $a\perp m$ means $\delta_m(a)\mid n$ for all $a\perp m$. That is, any positive integer $n$ satisfying this condition is a common multiple of all $\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 often used as an equivalent definition of the Carmichael function.

Repeatedly applying Property 5 shows that there exists some $a\perp m$ such that $\delta_m(a)=\lambda(m)$. Therefore, the above can also be written as

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

An element $a\perp m$ achieving this maximum is called a $\lambda$-primitive root modulo $m$. It exists for all moduli $m$.

Recurrence Formula

The Carmichael function is an arithmetic function. This section discusses a recurrence formula for it and gives another proof of the primitive root existence theorem.

Although not multiplicative, the Carmichael function can be computed separately for coprime factors.

Lemma

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

Proof

Let $a_1$ and $a_2$ be $\lambda$-primitive roots modulo $m_1$ and $m_2$, respectively. Let $m=m_1m_2$. By the Chinese Remainder Theorem, there exists $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}$. Then by Property 2 and the choice of $a_i$, $\lambda(m_i)=\delta_{m_i}(a_i)\mid \lambda(m)$. This shows $[\lambda(m_1),\lambda(m_2)]\mid\lambda(m)$.

Conversely, for any $a\perp m$ and $i=1,2$, we have $a^{[\lambda(m_1),\lambda(m_2)]} \equiv 1 \pmod{m_i}$. Applying the Chinese Remainder Theorem, we get $a^{[\lambda(m_1),\lambda(m_2)]} \equiv 1 \pmod{m}$ for all $a\perp m$. By the definition of the Carmichael function, $\lambda(m)\mid [\lambda(m_1),\lambda(m_2)]$.

Thus, the equality holds.

Therefore, we only need to compute the Carmichael function at prime powers. First, handle powers of $2$.

Lemma

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

Proof

The cases $m=2,4$ are trivial. For $m=2^e$ with $e\ge 3$, first repeat the first part of the proof of Lemma 4 to get $\lambda(m)\le 2^{e-2}$. Then we only need to show there exists an element of order $2^{e-2}$. For this,

$$ 5^{2{e-3}} = (1 + 2²⁾{2^{

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用