1. ## Primitive roots

Hi, another question again, pls help!!!

Let r be a primitive root of the prime p with p congruent to 1 (mod 4). Show that -r is also a primitive root.

2. Originally Posted by suedenation
Hi, another question again, pls help!!!

Let r be a primitive root of the prime p with p congruent to 1 (mod 4). Show that -r is also a primitive root.

Let, $r$ be a primitive root.
What is the order of $-r$?
Assume, $0 and arrive at contradiction.
We have,
$(-r)^k\equiv 1(\mbox{ mod }p)$

If, $k$ is even then we can drop the negative sign,
$r^k\equiv 1(\mbox{ mod }p)$

If, $k$ is odd then some difficultly arises.
So we cannot drop the negative sign,
$r^k\equiv -1(\mbox{ mod }p)$
Multiply through by $r$,
$r^{k+1}\equiv -r(\mbox{ mod }p)$
Since, $k$ odd we have $k+1$ even.
Thus, we can write,
$(r^{\frac{k+1}{2}})^2\equiv -r (\mbox{ mod }p)$
We see that $-r$ is a quadradic residue of $p$.
Hence the Legendre symbol,
$(-r/p)=1$
Since the Legendre symbol is multiplicative,
$(-1/p)(r/p)=1$
Since, $p\equiv 1(\mbox{ mod }4)$
We know that, $(-1/p)=1$
Thus,
$(r/p)=1$
Then by Euler's criterion we have,
$r^{\frac{p-1}{2}}\equiv 1(\mbox{ mod }p)$
But, $r$ is a primitive root
And, $\frac{p-1}{2}.
Thus $k$ can never be odd.
That means the only possible choice is $k=p$.