Primitive roots

**suedenation** · November 20th 2006, 09:29 PM

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.

Thanks for your help!!!

**ThePerfectHacker** · November 21st 2006, 07:05 AM

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.

Thanks for your help!!!

Let, $r$ be a primitive root.
What is the order of $-r$ ?
Assume, $0<k<p$ 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)$
Contradiction.

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}<p$ .
Thus, we have another contradiction.
Thus $k$ can never be odd.

That means the only possible choice is $k=p$ .

Thread: Primitive roots

LinkBack

Thread Tools

Display

Primitive roots

Similar Math Help Forum Discussions

[SOLVED] Primitive roots

Primitive Roots

Primitive roots

Primitive roots

Primitive Roots

Search Tags