Primitive Roots and the Group Structure of $\qu{n}$§

Previously, we’ve shown that if $n = \decomp{p}{a}{\ell},$ then $\qu{n} \approx \qu{p_1^{a_1}} \times \dots \times \qu{p_\ell^{a_\ell}}.$ Thus to determine the structure of $\qu{n}$ it is sufficient to consider the case of $\qu{p^a}$ for $p$ prime. We begin by considering the basic case of $\qu{p}.$

Lemma 1

Let $f(x) \in k[ x ],$ where $k$ is a field. Sps. that $\deg f(x) = n.$ Then $f$ has at most $n$ distinct roots.

We prove this result by induction on $n.$ For $n = 1,$ the result is trivial. Assume that for polynomials with degree $n - 1$ that the lemma holds. If $f(x)$ has no roots in $k$, done. If $\alpha$ is a root, $f(x) = q(x)(x - \alpha) + r,$ where $r$ is some constant. Setting $x = \alpha$ we see that $r = 0.$ Thus, $f(x) = q(x)(x - \alpha)$ and $\deg q(x) = n - 1.$ If $\beta$ is another distinct root of $f(x),$ then $0 = f(\beta) = (\beta - \alpha)q(\beta),$ implying $q(\beta) = 0.$ Since by induction $q(x)$ has at most $n - 1$ roots, $f(x)$ has at most $n$ distinct roots.

Corollary 1

Let $f(x), g(x) \in k[ x ]$ with degrees equal to $n.$ If $f(\alpha_i) = g(\alpha_i)$ for $n + 1$ distinct elements $\alpha_1, \alpha_2, \dots, \alpha_n, \alpha_{n + 1},$ then $f(x) = g(x).$

Apply lemma 1 to $f(x) - g(x).$

Proposition 1

$$ x^{p-1} - 1 \equiv_p (x - 1)(x - 2)\dots(x - p + 1). $$

Let $\overline{a}$ denote the residue class of $a \in \qr{m},$ then the using congruence classes we can rewrite the statement $$ x^{p - 1} - \overline{1} = (x - \overline{1})(x - \overline{2})\dots(x - \overline{(p - 1)}) \in \qr{p}[ x ]. $$

Let $f(x) = \big(x^{p - 1} - \overline{1}\big)-\big(x - \overline{1}\big)\big(x - \overline{2}\big)\dots\big(x - \overline{(p - 1)}\big).$ Then $\deg f(x) \leq p - 1$ and has the $p - 1$ roots $\overline{1}, \overline{2}, \dots, \overline{p - 1}$ by Fermat’s Little Theorem. Thus, $f(x)$ is congruent to zero.

Corollary 2 (Wilson's Theorem)

$$ (p - 1)! \equiv_p -1 $$

Let $x = 0$ in the proof of proposition 1.

Note: We also have the result that $(n - 1)! \equiv_n 0$ for composite integers $n \gt 4$ from exercise 10 in Congruences.

Proposition 2

If $d | p - 1,$ then $x^d \equiv_p 1$ has exactly $d$ solutions.

Let $dd’ = p - 1,$ then

$$ \frac{x^{p - 1} - 1}{x^d - 1} = \frac{\left(x^d\right)^{d’} - 1}{x^d - 1} = \left(x^d\right)^{d’ - 1} + \left(x^d\right)^{d’ - 2} + \dots + x^d + 1 = g(x). $$

Then $$ x^{p - 1} - 1 = \big(x^d - 1\big)g\big(x\big), $$ $$ x^{p - 1} - \overline{1} = \big(x^d - \overline{1}\big)\overline{g}\big(x\big). $$

If $x^d - \overline{1}$ had fewer than $d$ roots, then the right-hand side would have fewer than $p - 1$ roots by lemma 1. However, the left-hand side has the $p - 1$ roots, i.e. $\overline{1}, \overline{2}, \dots, \overline{p - 1}$. Therefore $x^d \equiv_p 1$ has exactly $d$ roots.

Theorem 1

$\qu{p}$ is a cyclic group.

For $d | p - 1,$ let $\psi(d)$ denote the number of elements in $\qu{p}$ of order $d.$ By proposition 2, we get that the elements of $\qu{p}$ satisfying $x^d \equiv_p 1$ form a group with order $d.$ Thus, $\sum_{c|d} \psi(c) = d.$ By applying the Möbius inversion theorem, we get $\psi(d) = \sum_{c_d}\mu(c)d/c.$ The right-hand side of this equation is equal to $\varphi(d).$ Particularly, $\psi(p - 1) = \varphi(p - 1),$ which is greater than 1 for $p \gt 2.$ Since $p = 2$ is the trivial case, we have shown in all cases the existence of $\varphi(p - 1)$ elements of order $p - 1.$

Primitive Roots§

Primitive Root

$a \in \qr{p}$ is called a primitive root modulo $p$ if $\overline{a}$ generates the group $\qu{p}.$ Equivalently, $a$ is a primitive root modulo $p$ if $p - 1$ is the smallest positive integer such that $a^{p - 1} \equiv_p 1.$

While we have shown the existence of prime roots, there is no easy method to find primitive roots, however, Artin’s conjecture on primitive roots states that if $a \gt 1$ is not square, then $a$ is a primitive root to infinitely many primes.

Artin’s conjecture was unsolved when Ireland and Rosen wrote this book in 1990, and it remains unsolved today (Jan. 2022).

Hooley1 in 1967 showed a conditional proof of Artin’s conjecture that is dependent on the generalized Riemann hypothesis.

Heath-Brown2 in 1986 proved for any 3-tuple of “multiplicatively independent” integers that Artin’s will hold for at least one of the integers, and there are at most two positive primes that fails Artin’s conjecture.

Note that being a primitive root for an infinitely number of primes does not imply primitive root for all primes.

Consider the prime decomposition $p - 1 = \decomp{q}{e}{t}$ and the congruences

$$ \begin{align} \large x^{q_i^{e_i - 1}} \equiv_p 1,\\ \large x^{q_i^{e_i}} \equiv_p 1. \end{align} $$

All solutions to the first congruence is also a solution to the second. However, there exists solutions to the second that do not satisfy the first. Sps. $g_i$ is a solution to 2 but not 1, then let $g = \prod_{i=1}^{t}g_i.$ Then, $\overline{g_i}$ generates the subgroup $\qu{p}$ of order $q_i^{e_i}.$ It follows that $\overline{g}$ generates a subgroup $\qu{p}$ with order $\decomp{q}{e}{t} = p - 1.$ Thus $g$ is a primitive root and $\qu{p}$ is cyclic.

From a group theoretic approach, $\psi(d) \leq \varphi(d)$ for $d | p - 1.$ Both $\sum_{d | p - 1} \psi(d)$ and $\sum_{d | p - 1} \varphi(d)$ equal $p - 1.$ It follows that $\psi(d) = \varphi(d)$ for all $d | p - 1.$ Particularly, $\psi(p - 1) = \varphi(p - 1).$ For $p \gt 2, \varphi(p - 1) \gt 1,$ implying $\psi(p - 1) \gt 1.$ And the result follows.

The notion of primitive roots can be generalized,

Primitive Root

For $a, n \in \mathbb{Z}$ we say that $a$ is a primitive root modulo $n$ if the residue class $a$ modulo $n$ generates $\qu{n}.$

Equivalently, we can require $a$ and $n$ to be coprime and that $\varphi(n)$ be the smallest positive integer such that $a^{\varphi(n)} \equiv_n 1.$

Generally, $\qu{n}$ is not cyclic, and it follows that not every integer possesses primitive roots.

Lemma 2

If $p$ prime and $1 \leq k \lt p,$ then $p$ divides the binomial coefficient $\binom{p}{k}.$

We can formulate two different proofs,

  1. By definition $$ \begin{align*} \binom{p}{k} &= \frac{p!}{k!(p-k)!},\\ p! &= k!(p-k)!\binom{p}{k}. \end{align*} $$ Now $p | p!,$ but $p \nmid k!(p - k)!$ as the expression is a product of integers less than, thus coprime to $p.$ Therefore, $p | \binom{p}{k}.$
  2. By Fermat’s Little Theorem $a^{p - 1} \equiv_p 1$ if $p \nmid a.$ It follows that $a^p \equiv_p a$ for all $a.$ Particularly, for all $a,$ $(1 + a)^p \equiv 1 + a \equiv 1 + a^p \pmod{p}.$ Thus $(1 + x)^p - 1 - x^p \equiv_p 0$ has $p$ solutions. Since the polynomial has degree less than $p$, it follows from corollary 1 that $(\overline{1} + x)^p - \overline{1} - x^p$ is identical to zero in $\qr{p}[ x ],$ $$ (1 + x)^p - 1 - x^p = \sum_{k = 1}^{p - 1}\binom{p}{k}x^k. $$ Thus $\overline{\binom{p}{k}} = \overline{0}$ for $1 \leq k \leq p - 1,$ implying $p | \binom{p}{k}.$ The key part from this second proof is that we do not make assumptions on $\binom{p}{k}.$

Lemma 3

If $\ell \gt 1$ and $a \equiv b \pmod{p^{ell}},$ then $a^p \equiv b^p \pmod{p^{\ell + 1}}.$

$\exists c \in \mathbb{Z}, a = b + cp’.$ Thus $a^p = b^p + \binom{p}{1}b^{p-1}cp^{\ell} + A,$ where $A \in \mathbb{Z}, p^{\ell + 2} | A.$ The second term is clearly divisible by $p^{\ell + 1},$ and the result follows.

Corollary 3

If $\ell \gt 2$ and $p \neq 2,$ then $\forall a \in \mathbb{Z}, (1 + ap)^{p^{\ell - 2}} \equiv 1 + ap^{\ell - 1} \pmod{p^{\ell}}.$

The proof is by induction on $\ell.$ For $\ell = 2,$ the assertion is trivial. Sps. that it is true for some $\ell \gt 2.$ Then, we will show that it is true for $\ell + 1.$ By applying lemma 3, $$ \big(a + ap\big)^{p^{\ell - 1}} \equiv \big(1 + ap^{\ell - 1}\big)^p \pmod{p^{\ell + 1}}. $$

Then, by the binomial theorem $$ \big(1 + ap^{\ell - 1}\big)^p = 1 + \binom{p}{1}ap^{\ell - 1} + B, $$ where $B$ is the sum of $p - 2$ terms. By lemma 2, we see that all these terms are divisible by $p^{\ell + 2(\ell - 1)}.$ It may not be obvious for the last term, $a^pp^{p(\ell - 1)},$ but since $\ell \gt 2, 1 + 2(\ell - 1) \gt \ell + 1,$ also $p \gt 3, p(\ell - 1) \gt \ell + 1.$ Thus $p^{\ell + 1} | B$ and $(1 + ap)^{p^{\ell - 1}} \equiv 1 + ap^{\ell}\left(p^{\ell + 1}\right),$ which is as required.

Order

Sps. $a, n \in \mathbb{Z}$ and $(a, n) = 1.$ We say that $a$ has order $e$ modulo $n$ if $e$ is the smallest positive integer such that $a^e \equiv_n 1.$ This is equivalent to saying that $\overline{a}$ has order $e$ in the group $\qu{n}.$

Corollary 4

Let $p$ be an odd prime. If $a \in \mathbb{Z}, p \nmid a,$ then $p^{\ell - 1}$ is the order of $1 + ap \pmod {p^{\ell}}.$

By corollary 3, $(1 + ap)^{p^{\ell - 1}} \equiv 1 + ap^{\ell} \pmod{p^{\ell + 1}},$ which implies that $(1 + ap)^{p^{\ell - 1}} \equiv 1 \pmod{p^{\ell}}$ thus $1 + ap$ has order dividing $p^{\ell - 1}.$ $(1 + ap)^{p^{\ell - 2}} \equiv 1 + ap^{\ell - 1} \pmod{p^{\ell}}$ shows that $p^{\ell - 2}$ is not the order of $1 + ap$ due to $p \nmid a.$ Then the result follows.

Often in number theory, we have to treat $2$ separately from the rest of the prime numbers, hence the “$p$ is an odd prime”.

Theorem 2

If $p$ is an odd prime and $\ell \in \mathbb{Z}^{+},$ then $\qu{p^\ell}$ is cyclic; i.e. there exists primitive roots modulo $p^\ell.$

By theorem 1 there exists primitive roots modulo $p.$ If $g \in \mathbb{Z}$ is a primitive root modulo $p,$ then so is $g + p.$ If $g^{p - 1} \equiv 1 \pmod{p^2},$ then $(g + p)^{p - 1} \equiv g^{p - 1} + (p - 1)g^{p - 2}p \equiv 1 + (p - 1)g^{p - 2}p \pmod{p^2}$. Since $p^2$ does not divide $(p - 1) \times g^{p - 2}p$ we can assume from the beginning that $g$ is a primitive root modulo $p$ and that $g^{p - 1} \not\equiv 1 \pmod{p^2}.$

We claimed that $g$ is a primtiive root modulo $p^{\ell}.$ To show that $g$ is indeed a primitive root, it is sufficient to prove that if $g^n \equiv 1 \pmod{p^\ell},$ then $\varphi\left(p^\ell\right) = p^{\ell - 1}\big(p - 1\big) | n.$

$g^{p - 1} = 1 + ap,$ where $p \nmid a.$ By corollary 4, $p^{\ell - 1}$ is the order of $1 + ap \pmod{p^{\ell}}.$ Since $(1 + ap)^n \equiv 1 \pmod{p^\ell}$ we have that $p^{\ell - 1} | n.$

Let $n = p^{\ell - 1}n’.$ Then $g^n = \left(g^{p^{\ell - 1}}\right)^{n’} \equiv g^{n’} \pmod{p},$ therefore $g^n \equiv 1 \pmod{p}.$

Since $g$ is a primitive root modulo $p$, $p - 1 | n’.$ Therefore, $p^{\ell - 1}(p-1) | n.$

Theorem 2'

$2^\ell$ has primitive roots for $\ell \in \{1, 2\}$ but not for $\ell \geq 3.$

If $\ell \geq 3,$ then $\{(-1)^a5^b | a \in \{0, 1\} \text{ and } 0 \leq b \lt 2^{\ell - 2}\}$ constitutes a reduced residue system modulo $2^\ell.$

It follows that for $\ell \geq 3, \qu{2}$ is the direct product of two cyclic groups, one of order $2$ and the other being order $2^{\ell - 2}.$

$1$ is a primitive root modulo $2$ and $3$ a primitive root modulo $4.$ We now assume $\ell \geq 3.$

We claim that $5^{2^{\ell - 3}} \equiv 1 + 2^{\ell - 1} \pmod{2^\ell}\ (\dag).$ This is true for $\ell = 3,$ and assume that it is true for $\ell \geq 3$ and we aim to show that it is true for $\ell + 1.$ First, notice $\left(1 + 2^{\ell - 1}\right)^2 = 1 + 2^\ell + 2^{2\ell - 2}$ and that $2l - 2 \geq \ell + 1$ for $\ell \geq 3.$ By applying lemma 3 to congruence $(\dag)$, and we get $5^{2^{\ell - 2}} \equiv 1 + 2^\ell\left(2^{\ell + 1}\right)\ (\ddag).$ By induction, the claim is established.

From $(\ddag)$ we see $5^{2^{\ell - 2}} \equiv 1 \pmod{2^\ell},$ whilst from $(\dag)$ we get $5^{2^{\ell - 3}} \not\equiv 1 \pmod{2^\ell}.$ Thus $2^{\ell - 2}$ is the order of $5$ modulo $2^\ell.$

Consider the set $\{(-1)^a5^b | a \in \{0, 1\}\text{ and } 0 \leq b \lt 2^{\ell - 2}\}.$ We claim that these $2^{\ell - 1}$ numbers are incongruent to modulo $2^\ell.$ Since $\varphi\left(2^\ell\right) = 2^{\ell - 1}$ this will show that the set is a reduced residue system modulo $2^\ell.$

If $(-1)^a5^b \equiv (-1)^{a’}5^{b’} \pmod{2^\ell},$ then $(-1)^a \equiv (-1)^{a’} \pmod{4},$ which implies that $a \equiv a’ \pmod{2}.$ Thus $a = a’.$ Furthermore, $a = a’$ implies that $5^b = \equiv 5^{b’} \pmod{2^\ell},$ i.e. $5^{b - b’} \equiv 1 \pmod{2^\ell}.$ Therefore, $b \equiv b’ \pmod{2^{\ell - 2}},$ resulting in $b = b’.$

Finally, we notice that $(-1)^a5^b$ raised to the $2^{\ell - 2}$th power is congruent to $1$ modulo $2^\ell.$ Ergo, $2^\ell$ has no primitive roots for $\ell \geq 3.$

For $\ell = 3,$ we get that the reduced residue system consists of $1, 3, 5,$ and $7.$ For $\ell = 4,$ we get the following system, where the $(-)$ indicates the negative powers

$$ \newcommand{\arraystretch}{1.65} \begin{array}{ c | c c} & 5^0 & 5^1 & 5^2 & 5^3\\\hline (+) & 1 & 5 & 9 & 13\\ (-) & 15 & 11 & 7 & 3 \end{array} $$

Finally, for an arbitrary $n,$ we can define the group $\qu{n}$ through theorems 2 and 2'.

Theorem 3

Let $n = 2^a\decomp{p}{a}{\ell}$ be the prime decomposition of $n.$ Then

$$ \qu{n} \approx \qu{2^d} \times \qu{p_1^{a_1}} \times \dots \times \qu{p_\ell^{a_\ell}}. $$

  • $\qu{p_i^{a_i}}$ is a cyclic group of order $p_i^{a_i - 1} \pmod{p_i - 1}.$
  • $\qu{2^a}$ is cyclic of order $1$ and $2$ for $a = 1$ and $2$, respectively.
    • For $a \geq 3,$ then $\qu{2^a}$ is the product of two cyclic groups, one with order $2$ and another of $2^{a-2}.$

Proposition 3

$n$ possesses primitive roots iff $n$ is of the form $2, 4, p^a,$ or $2p^a,$ where $p$ is an odd prime.

By theorem 2’, we can assume wlog. that $n \neq 2^\ell, \ell \geq 3.$ If $n$ is not of a given form, then we see that $n = m_1m_2$ where $(m_1, m_2) = 1,$ and $m_1, m_2 \gt 2.$ Then, $\varphi(m_1)$ and $\varphi(m_2)$ are even, and $\qu{n} \approx \qu{m_1} \times \qu{m_2}.$ Both $\qu{m_1}$ and $\qu{m_2}$ have elements with order $2,$ showing that $\qu{n}$ is not cyclic because a cyclic group can contain at most one element of order $2.$ Thus, $n$ does not possess primitive roots.

We have previously shown that $2, 4,$ and $p^a$ possess primitive roots. Since $\qu{2p^a} \approx \qu{2} \times \qu{p^a} \approx \qu{p^a},$ it follows that $\qu{2p^a}$ is cyclic and contains primitive roots.


$n$th Power Residues§

Power Residues

For $m, n \in \mathbb{Z}^{+},$ where $a \in \mathbb{Z}$ and $(a, m) = 1,$ if $x^n \equiv_m a$ is solvable, then we say that $a$ is an $n$th power residue modulo $m.$

Proposition 4

If $m \in \mathbb{Z}^{+}$ possesses primitive roots and $(a, m) = 1,$ then $a$ is an $n$th power residue modulo $n$ iff $a^{\varphi(m)/d} \equiv_m 1,$ where $d = (n, \varphi(m)).$

Let $g$ be a primitive root modulo $m$ and $a = g^b, x = g^y.$ Then the congruence $x^n \equiv_m a \iff g^{ny} \equiv_m g^b \iff ny \equiv b \pmod{\varphi(m)}.$ The last congruence is solvable iff $d | b.$ Moreover, notice that if there is one solution, there are exactly $d$ solutions.

If $d | b,$ then $a^{\varphi(m)/d} \equiv g^{b\varphi(m)/d} = 1 \pmod{m}.$ Conversely, if $a^{\varphi(m)/d} \equiv_m 1,$ then $g^{b\varphi(m)/d} \equiv_m 1,$ implying that either $\varphi(m) | b\varphi(m)/d$ or $d | b.$

1

As a result, if $x^n \equiv_m a$ is solvable, then there must exist exactly $((n, \varphi(m))$ solutions. Sps. that $m = 2^e\decomp{p}{e}{\ell}.$ Then $x^n \equiv_m a$ is solvable iff the following system of congruences is solvable,

$$ x^n \equiv \begin{cases} a & \mkern-1em\pmod{2^e}\\ a & \mkern-1em\pmod{p_1^{e_1}}\\ &\vdots\\ a & \mkern-1em\pmod{p_\ell^{e_\ell}} \end{cases} $$

Since odd prime powers posses primitive roots we can apply proposition 4 to the last $\ell$ congruences. Then, we need only consider the congruence $x^n \equiv a \pmod{2^e}.$ Since $2$ and $4$ possess primitive roots, we may assume that $e \geq 3.$

Proposition 5

Sps. $a$ odd and $e \geq 3,$ and consider the congruence $x^n \equiv a \pmod{2^e}.$

  • If $n$ odd, then there always exists a unique solution.
  • Otherwise, a solution exists iff $a \equiv 1 \pmod{4},$ and $a^{2^{e-2} / d} \equiv 1 \pmod{2^e},$ where $d = \left(2^{e-2}\right).$

When there exists solutions, there are exactly $2d$ solutions.

todo: This proof was left as an exercise for the reader, I have yet to do it.

It begins by $a \equiv (-1)^s5^t \pmod{2^e}$ and $x \equiv (-1)^y5^z \pmod{2^e}.$

Propositions 4 and 5 help answer “when is an integer $a$ an $n$th power residue modulo $m?$” In some cases, we can go further.

Proposition 6

Sps. $p$ an odd prime, $p \nmid a,$ and $p \nmid n.$ If $x^n \equiv a \pmod{p}$ is solvable, then so is $x^n \equiv a \pmod{p^e}$ for all $e \geq 1$ and all of these congruences have the same number of solutions.

We consider $n \geq 2,$ as $n = 1$ is trivial. Sps. $x^n \equiv a \pmod{p^e}$ is solvable. Let $x_0$ be a solution and set $x_1 = x_0 + bp^e.$ We observe that $x_1^n \equiv x_0^n + nbp^ex_0^{n-1} \pmod{p^{e+1}}.$ We wish to solve $x_1^n \equiv a \pmod{p^{e+1}}.$ This is equivalent to finding an integer $b$ such that $nx_0^{n-1}b \equiv \left(a - x_0^n\right) / p^e \pmod {p}.$ Notice that $\left(a - x_0^n\right)/p^e$ is an integer and $p \nmid nx_0^{n-1}.$ Thus the congruence is uniquely solvable for $b,$ and with this value of $b,$ $x_1^n \equiv a \pmod{p^{e+1}}.$

If $x^n \equiv a \pmod{p}$ has no solutions, then $x^n \equiv a \pmod{p^e}$ has no solutions. On the other hand, if $x^n \equiv a \pmod{p}$ has a solution so do all of the congruences $x^n \equiv a \pmod{p^e}.$ In remark 1, we showed that $x^n \equiv a \pmod{p^e}$ has $\left(n, \varphi\left(p^e\right)\right)$ solutions should they exist. If $p \nmid n,$ then it follows that $(n, \varphi(p)) = \left(n, \varphi\left(p^e\right)\right)$ for all $e \geq 1.$

The proof for powers of $2$ is different.


  1. Hooley, Christopher. “On Artin’s Conjecture.” Journal Für Die Reine Und Angewandte Mathematik (Crelles Journal), vol. 1967, no. 225, 1967, pp. 209–220., https://doi.org/10.1515/crll.1967.225.209↩︎

  2. Heath-Brown, D. R. “Artin’s Conjecture for Primitive Roots.” The Quarterly Journal of Mathematics, vol. 37, no. 1, Mar. 1986, pp. 27–38., https://doi.org/10.1093/qmath/37.1.27↩︎