If g is a primitive root modulo $N$, then g is a primitive root modulo $D$, where $D|N$.

Question

Let g be a primitive root modulo $N\ge2$ and $D\ge 2$ a divisor of $N$. Show that the reduction modulo D of g is a primitive root modulo D.

I've tried using Gauss' Theorem, but I'm not quite sure how to go on.

Answer 1

Let $\mathbb{Z}/N\mathbb{Z}$ be the ring of integers modulo $N$, and let $(\mathbb{Z}/N\mathbb{Z})^{\ast} \subseteq \mathbb{Z}/N\mathbb{Z}$ denote the group of units modulo $N$. The map $x + N\mathbb{Z} \mapsto x + D \mathbb{Z}$ defines a group homomorphism

$$(\mathbb{Z}/N\mathbb{Z})^{\ast} \rightarrow (\mathbb{Z}/D\mathbb{Z})^{\ast}$$

If you can show this homomorphism is surjective, you are done. This is because if $\phi: G \rightarrow H$ is a surjective homomorphism of groups, then generating sets of $G$ are mapped to generating sets of $H$ by $\phi$.

Thus for every integer $x$ which is relatively prime to $D$, you need to find an integer $y$ which is relatively prime to $N$, with the property that $x \equiv y \pmod{D}$. One way to do this is using the Chinese remainder theorem.