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, $\displaystyle r$ be a primitive root.
What is the order of $\displaystyle -r$?
Assume, $\displaystyle 0<k<p$ and arrive at contradiction.
We have,
$\displaystyle (-r)^k\equiv 1(\mbox{ mod }p)$

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

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