# Let $p$ be an odd prime. Suppose that $a$ is an odd integer and also $a$ is a primitive root mod $p$. Show that $a$ is also a primitive root mod $2p$.

Let $p$ be an odd prime. Suppose that $a$ is an odd integer and also $a$ is a primitive root modulo $p$. Show that a is also a primitive root modulo $2p$.

Any hints will be appreciated. Thanks very much.

A way is like this (you may have to justify the points a bit):

• There are $p-1$ invertible classes mod $2p$, the same number as for $p$.

• $a$ is invertible mod $2p$.

• The multiplicative order of $a$ mod $p$ is $p-1$.

• The multiplicative order of $a$ mod $2p$ is at least as large as the one mod $p$.

From this you can conclude directly.

The natural projection $\pi:U(2p) \to U(p)$ given by $x \bmod 2p \mapsto x \bmod p$ is a homomorphism of groups.

The kernel of $\pi$ is trivial because $x \equiv 1 \bmod p$ implies $x \equiv 1 \bmod 2p$ since we must have $x \equiv 1 \bmod 2$ if $x \in U(2p)$. By the Chinese remainder theorem, we then have $x \equiv 1 \bmod 2p$.

Thus, $\pi$ is injective and so it is surjective, because $U(2p)$ and $U(p)$ have the same size.

Therefore, $\pi$ is an isomorphism and must map generators to generators.

Concretely, take $a$ as in the question. Then $a \in U(2p)$ and $\pi(a)$ has order $p-1$ in $U(p)$. Therefore, $a$ also has order $p-1$ in $U(2p)$, which is the order of $U(2p)$. Thefore, $a$ is a primitive root mod $2p$.

More generally, if ord$_{m_1}a=d_1$ and ord$_{m_2}a=d_2$ with $(m_1,m_2)=1$

we can prove ord$_{(m_1\cdot m_2)}a=$lcm$(d_1,d_2)$ (Proof below)

Put $m_1=p^k,m_2=2^n$ with prime $p>2$

Then choose $n=1$

Proof: ord$_{m_1}a=d_1\implies a^{d_1}\equiv1\pmod{m_1}$

and ord$_{m_2}a=d_2\implies a^{d_2}\equiv1\pmod{m_2}$

If $(d_1,d_2)=g$ and $\dfrac{d_1}{D_1}=\dfrac{d_2}{D_2}=g$ so that $(D_1,D_2)=1$

lcm$(d_1,d_2)=gD_1D_2$

Clearly, $a^{gD_1D_2}\equiv1\pmod{m_1}$ and $a^{gD_1D_2}\equiv1\pmod{m_2}$

As $(m_1,m_2)=1,a^{gD_1D_2}\equiv1\pmod{m_1m_2}$

If ord$_{m_1\cdot m_2}a=D,D$ must divide $gD_1D_2\ \ \ \ (1)$

Again, $a^D\equiv1\pmod{m_1m_2}\implies a^D\equiv1\pmod{m_1}\implies d_1(=gD_1)$ must divide $D$

Similarly, $d_2(=gD_2)$ must divide $D$

$\implies$lcm$(gD_1,gD_2)=gD_1D_2$ must divide $D\ \ \ \ (2)$

$(1),(2)\implies D=gD_1D_2$