# $g^q-q$ and $g^q-gq$ are primitive roots modulo $q^2$

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.

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

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)$.