1. ## Primitive roots

[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]

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

Now we need to prove that if $\displaystyle 1\leq k\leq p-1$ is order of $\displaystyle -r$ then $\displaystyle k=(p-1)/2$.
By the above result we see that $\displaystyle k|(p-1)/2$, since $\displaystyle (p-1)/2$ is odd it follows that $\displaystyle k$ must be odd.
But then, $\displaystyle (-r)^k = -r^k\equiv 1(\bmod p)\implies r^k \equiv -1(\bmod p)$.
Also, $\displaystyle 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 $\displaystyle (p-1)/2 \equiv k(\bmod p-1)\implies k=(p-1)/2$.

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

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

,

,

,

,

### if r is primitive root of p 1 mod 4 then r^{(p-1)/4} x2 1 0 mod p

Click on a term to search for related topics.