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$


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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.