# $r$ primitive root of prime $p$, where $p \equiv 1 \mod 4$: prove $-r$ is also a primitive root

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.

## 2 Answers

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

• How does r^2k ≡ −1 (mod p) follow from the fact that r is a primitive root of p? – Chiefy Apr 2 '15 at 3:19
• 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$. – André Nicolas Apr 2 '15 at 3:23
• @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? – 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}$.