Primitive roots

**Etrain27** · May 6th 2008, 06:25 AM

[FONT='Times New Roman','serif']Let r be a primitive root of the odd prime p . Prove the following.[/FONT]
[FONT='Times New Roman','serif']If p is congruent to 3(mod 4), then -r has order (p-1)/2 modulo p.[/FONT]

**ThePerfectHacker** · May 6th 2008, 06:55 AM

Originally Posted by Etrain27

[FONT='Times New Roman','serif']Let r be a primitive root of the odd prime p . Prove the following.[/FONT]
[FONT='Times New Roman','serif']If p is congruent to 3(mod 4), then -r has order (p-1)/2 modulo p.[/FONT]

$r^{p-1} \equiv 1(\bmod p) \implies (r^{(p-1)/2} -1)(r^{(p-1)/2}+1)\equiv 0(\bmod p)$ .
Thus, $r^{(p-1)/2}\equiv 1,-1(\bmod p)$ it cannot be $1$ because the order of $r$ is $p-1$ .
Thus, $r^{(p-1)/2}\equiv -1(\bmod p)$ .
This tells us, $\left( -r \right)^{(p-1)/2} = (-1)^{(p-1)/2}r^{(p-1)/2}\equiv (-1)(-1) = 1(\bmod p)$ because $p\equiv 3(\bmod 4)$ .

Now we need to prove that if $1\leq k\leq p-1$ is order of $-r$ then $k=(p-1)/2$ .
By the above result we see that $k|(p-1)/2$ , since $(p-1)/2$ is odd it follows that $k$ must be odd.
But then, $(-r)^k = -r^k\equiv 1(\bmod p)\implies r^k \equiv -1(\bmod p)$ .
Also, $r^{(p-1)/2} \equiv -1(\bmod p)\implies r^{(p-1)/2} \equiv r^k (\bmod p)$ .
Using properties of primitive roots and orders it means $(p-1)/2 \equiv k(\bmod p-1)\implies k=(p-1)/2$ .

**theotheleo** · May 6th 2008, 07:39 AM

Looking at your reply to the question in this thread, I have a question very similiar to the one posted originally and am sure that you would be able to help me out also quite simply.

Let r be a primitive root of the odd prime p. If p=1(mod 4), then -r is also a primitive root of p.

I would appreciate the help on this question, I am sure there will be a similar question on my final next week.

**ThePerfectHacker** · May 6th 2008, 09:00 AM

Originally Posted by theotheleo

Let r be a primitive root of the odd prime p. If p=1(mod 4), then -r is also a primitive root of p.

Let $k$ be the order of $-r$ .
We claim that $k$ cannot be odd. Suppose that $k$ is odd.
Then $(-r)^k = -r^k \equiv 1(\bmod p) \implies r^k \equiv -1(\bmod p)$ .
Again $r^{(p-1)/2}\equiv -1(\bmod p)$ which will force $k=(p-1)/2$ .
But that is a contradiction because $p\equiv 1(\bmod 4)$ so $(p-1)/2$ is even.
Since $k$ is even it mean $(-r)^k = r^k$ and so the order must be the same as $r$ , i.e. $p-1$ .

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