question is as follows:

Let $p$ be a prime with $p \equiv 1 \mod 4$, and $r$ be a primitive root of $p$. Prove that $-r$ is also a primitive root of $p$.

I have shown that $-r^{\phi(p)} \equiv 1 \mod p$. What I am having trouble showing, however, is that the order of $-r$ modulo $p$ is not some number (dividing $\phi(p)$ that is LESS than ($\phi(p)$).

By way of contradiction, I've shown that the order of $-r$ cannot be an EVEN number less than $\phi(p)$. But my methodology does not work for the hypothetical possibility of an ODD order that is less than $\phi(p)$.

Any and all help appreciated. Happy to show methodology for any of the parts I have managed to do, if requested.


Let $p=4k+1$. Since $r$ is a primitive root of $p$, we have $r^{2k}\equiv -1\pmod{p}$. Thus $(-r)^{2k}\equiv -1\pmod{p}$, and therefore $$(-r)^{2k+1}\equiv (-1)(-r)\equiv r\pmod{p}.$$ Since $r$ is congruent to a power of $-r$, and $r$ is a primitive root of $p$, it follows that $-r$ is a primitive root of $p$.

  • $\begingroup$ How does r^2k ≡ −1 (mod p) follow from the fact that r is a primitive root of p? $\endgroup$ – Chiefy Apr 2 '15 at 3:19
  • 1
    $\begingroup$ We have $r^{4k}\equiv 1$ by Fermat, so $(r^{2k})^2\equiv 1$. The congruence $x^2\equiv 1$ has two solutions, $1$ and $-1$. So $r^{2k}\equiv\pm 1$. But we cannot have $r^{2k}\equiv 1$, since $r$ has order $4k$. $\endgroup$ – André Nicolas Apr 2 '15 at 3:23
  • 2
    $\begingroup$ @AndréNicolas I understand your proof up until your last statement. Why is it that just because a power of -r is congruent to r then -r must be a primitive root? $\endgroup$ – mmm Apr 8 '17 at 21:47

Result: Let $r$ be a primitive root $\pmod{p}$. Then the order of $r^k \pmod{p}$ is $\frac{p-1}{\gcd(k, p-1)}$.

Proof: Let $m$ be the order of $r^k \pmod{p}$. Then $1 \equiv (r^k)^m \equiv r^{km} \pmod{p}$, so $p-1 \mid km$ as $r$ is a primitive root. Thus $\frac{p-1}{\gcd(k, p-1)} \mid \frac{k}{\gcd(k, p-1)}m$ and $\gcd(\frac{p-1}{\gcd(k, p-1)},\frac{k}{\gcd(k, p-1)})=1$ so $\frac{p-1}{\gcd(k, p-1)} \mid m$. On the other hand $(r^k)^{\frac{p-1}{\gcd(k, p-1)}} \equiv (r^{\frac{k}{\gcd(k, p-1)}})^{p-1} \equiv 1 \pmod{p}$ so $m \mid \frac{p-1}{\gcd(k, p-1)}$. Thus $m=\frac{p-1}{\gcd(k, p-1)}$, as desired.

Now note $r^{\frac{p+1}{2}} \equiv r^{\frac{p-1}{2}}r \equiv -r \pmod{p}$.


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.