The question: Let $a,p \in \Bbb N$,$ \ $ $p$ is an odd prime, $a$ is a primitive root modulo $p$. prove that:
- if $a$ is odd, $a$ is primitive root modulo $2p$.
- if $a$ is even, $a+p$ is primitive root modulo $2p$.
Thank you
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:
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.