Very elementary things today. Recently when looking at the introductory materials in our college, this result just became tempting to formulate and review. (Sometimes their problems are pretty good.)
This is basically produced by hand so the approach might be bad. We start with the obvious property of primitive roots.
Proposition 1. If the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic, its generators are called the primitive roots $\operatorname{mod}n$. If they exist, there are $\varphi(\varphi(n))$ of them.
Proof. $\left|(\mathbb{Z}/n\mathbb{Z})^\times\right|=\varphi(n)$.
Proposition 2. For a prime $p$ there exists primitive roots $\operatorname{mod} p$.
Proof. By the well known classification of finitely generated modules over a PID, we see that there exists $d_1|d_2|\cdots|d_k$ such that
\[(\mathbb{Z}/p\mathbb{Z})^\times\simeq(\mathbb{Z}/d_1\mathbb{Z})\times(\mathbb{Z}/d_2\mathbb{Z})\times\cdots\times(\mathbb{Z}/d_k\mathbb{Z}).\]In particular, every element of $(\mathbb{Z}/p\mathbb{Z})^\times$ is a root of $x^{d_k}-1$. As $\mathbb{Z}/p\mathbb{Z}$ is a field, we conclude that $d_k\geq p-1$, and so $k=1$.
I’m not sure if this strategy works in general. In any case, we can do the following.
Notice that a primitive root $\operatorname{mod} p^s$ is also a primitive root $\operatorname{mod} p^t$ if $t\leq s$. This is because a surjective homomorphism between cyclic groups sends all generators to generators.
Lemma 1. If elements $a$, $b$ of a abelian group has coprime finite orders, then $\operatorname{ord}(ab)=\operatorname{ord}(a)\operatorname{ord}(b)$.
Proof. Follows from criterion of internal direct product.
Proposition 3. If $n=p^k$ is a power of an odd prime $p$, then there exists primitive roots $\operatorname{mod} n$.
Proof. Use induction on $k\geq 1$. Given a primitive root $a\operatorname{mod} p^k$, we want to lift it to a primitive root $\operatorname{mod}p^{k+1}$.
If $\operatorname{ord}_{p^{k+1}}(a)=\varphi(p^{k+1})=p^k(p-1)$ then there’s nothing to prove. The only other possibility is $\operatorname{ord}(a)=\varphi(p^k)=p^{k-1}(p-1)$. In view of Lemma 1., we only need to construct an element $b$ of with order $p^k$, so that
\[\operatorname{ord}(a^{p^{k-1}}b)=\operatorname{ord}(a^{p^{k-1}})\operatorname{ord}(b)=p^k(p-1)\]as desired. $b$ is given by the following lemma.
Lemma 2. If $p$ is an odd prime, then for any $k\geq 0$,
\[(1+p)^{p^k}=1+dp^{k+1}\]for some $d$ satisfying $d\equiv 1\operatorname{mod}p$. In particular,
\[\operatorname{ord}_{p^{k+1}}(1+p)=p^k.\]Proof. Direct computation. Since
\[(1+p)^{p^k}=1+p^{k+1}+\sum_{i\geq 2}\binom{p^k}{i}p^i,\]we need to show that $\nu(\binom{p^k}{i})+i\ge k+2$ for $i\geq 2$. In fact, the first term is $(k-\nu(i))$, and the result follows from the monotonicity of $(i-\nu(i))$ and that $2-\nu(2)=2$. To prove that we can simply compute
\[\begin{align*} \nu(\frac{p^k!}{i!(p^k-i)!}) &= \sum_{r=0}^\infty\left(\lfloor p^{k-r}\rfloor-\lfloor\frac{i}{p^r}\rfloor-\lfloor\frac{p^k-i}{p^r}\rfloor\right) \\ &= \sum_{r=0}^k\left(\lceil\frac{i}{p^r}\rceil-\lfloor\frac{i}{p^r}\rfloor\right) \\ &= k-\nu(i). \end{align*}\]
Proposition 4. If $a,b\geq 3$ are coprime factors of $n$, then there’s no primitive root $\operatorname{mod}n$. If $n=2p^k$ where $p$ is an odd prime, then primitive roots $\operatorname{mod}n$ exist.
Proof. If $a$, $b$ are coprime, then
\[\mathbb{Z}/ab\mathbb{Z}\simeq(\mathbb{Z}/a\mathbb{Z})\times(\mathbb{Z}/b\mathbb{Z}),\] \[(\mathbb{Z}/ab\mathbb{Z})^\times\simeq(\mathbb{Z}/a\mathbb{Z})^\times\times(\mathbb{Z}/b\mathbb{Z})^\times.\]Any number $\geq 3$ has an even $\varphi$, so $(\varphi(a),\varphi(b))\neq 1$. On the other hand, of course $(\varphi(2),\varphi(p^k))=1$.
The only numbers left by Proposition 2,3,4. are powers of $2$. We deal with them now with the following proposition and the only theorem in this article.
Proposition 5. If $k>2$ then there’s no primitive root $\operatorname{mod}2^k$.
Proof. $(\mathbb{Z}/2^k\mathbb{Z})^\times$ cannot be cyclic since we have three different elements of order $2$: $-1$ and $2^{k-1}\pm 1$.
Theorem. A primitive root $\operatorname{mod}4$ exists.
Proof (sketch). Look at $3$.
We conclude that $(\mathbb{Z}/n\mathbb{Z})^\times$ is explicitly computed for every $n$, and it is a cyclic group if and only if $n$ is $2$ or $4$, or of the form $p^k$ or $2p^k$, where $p$ is an odd prime.
Post date: 2024/11/06
Home page