2
$\begingroup$

Let $g$ be a primitive root modulo an odd prime $q$. Then, both $g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$.

I read this question somewhere and the first thing that came to my mind as a solution is the proof of the theorem that $U_{q^e}$ is cyclic for all $e\ge 1$. But I did not seem to make a connection.

$\endgroup$
  • $\begingroup$ Using $g$ and $q$ is confusing! $\endgroup$ – Aryabhata May 4 '15 at 21:05
5
$\begingroup$

Let $a=g^p-cp$ with $c\not\equiv 0\pmod p$. First observe that $g^p-cp\equiv g\pmod p$ by Fermat. Since the order of $g$ modulo $p$ is $p-1$, the order of $a$ modulo $p^2$ is certainly a multiple of $p-1$. We compute $$a^{p}=g^{p^2}-cp^2g^{p(p-1)}+{p\choose 2}c^2p^2g^{p(p-2)}\mp\ldots\equiv g^{p^2}\pmod{p^2},$$ and because of $g^{p^2}=g^{p+\phi(p^2)}\equiv g^p$, we see that $a^p\equiv a+cp\not\equiv a\pmod{p^2}$. Therefore $a^{p-1}\not\equiv 1\pmod{p^2}$ so that the order of $a$ is a proper multiple of $p-1$. As it must also be a divisor of $\phi(p^2)=p\cdot(p-1)$, we conlcude that the order equals $p\cdot(p-1)$.

$\endgroup$

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.