Primitive root modulo $2p$

elementary-number-theorymodulesprime numbersprimitive-rootstotient-function

The question: Let $a,p \in \Bbb N$,$ \ $ $p$ is an odd prime, $a$ is a primitive root modulo $p$. prove that:

  1. if $a$ is odd, $a$ is primitive root modulo $2p$.
  2. if $a$ is even, $a+p$ is primitive root modulo $2p$.

Thank you

Best Answer

$\textbf{First one:}$ Since,$\phi(2p)=p-1$. So,First we prove that $a^{p-1} \equiv 1 \pmod{2p}$

But since $a^{p-1} \equiv 1 \pmod{p}$ and $a^{p-1} \equiv 1 \pmod{2}$ for a being odd.

The result follows immediately from chinese remainder theorem.

If $a^d \equiv 1 \pmod{2p}$ for smaller d. Then, $2p \mid a^d-1 \implies p \mid a^d-1 \implies a^d \equiv 1 \pmod{p}$ contradiction.

For the second one,

First we prove that $(a+p)^{p-1} \equiv 1 \pmod{2p}$

But since $(a+p)^{p-1} \equiv a^{p-1} \equiv 1 \pmod{p}$ and $(a+p)^{p-1} \equiv 1 \pmod{2}$ for $a+p$ being odd.

The result follows immediately from chinese remainder theorem.

If $(a+p)^d \equiv 1 \pmod{2p}$ for smaller d. Then, $2p \mid (a+p)^d-1 \implies p \mid (a+p)^d-1 \implies p \mid a^{p-1}-1\implies a^d \equiv 1 \pmod{p}$ contradiction.

Related Question