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

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.

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

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.

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

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.

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

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

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

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.

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.

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

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

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.

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

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