# The Structure of $U(\mathbb{Z}/n\mathbb{Z})$

## 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).

Hooley

^{1}in 1967 showed a conditional proof of Artin’s conjecture that is dependent on the generalized Riemann hypothesis.Heath-Brown

^{2}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,

- 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}.$
- 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.

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. ↩︎

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. ↩︎