Primitive roots - annoying problem

[RichardCypher]

Let r be a primitive root of a prime number p \geq 3. Prove that if p \equiv 1 (mod 4), then -r is also a primitive root of p.

I've been told it's quite easy, but I can't see why it's true for the life of me :frown:

[robert Ihnot]

If r is a primitive root, then r^[(p-1)/2] is not equal to 1. The question is about -r.

[RichardCypher]

thanks for the reply :smile:
if r is a primitve root then r^[(p-1)/2] is -1 (mod p). However, (-r)^[(p-1)/2] is the same since (p-1)/2 is even, am I right?

Where do we go from here? Maybe I could say that the order of (-r) couldn't be lower than (p-1), because if it was so, ord(-r)|(p-1)/2 and then (-r)^[(p-1)/2]=1(mod p) contradicting the fact that p \neq 2?
Am I on the right track?

Thanks again! :smile:

[robert Ihnot]

Richard Cypher: Am I on the right track?

Sounds O.K. to me. Take, (-r)^2 = r^2, well then what power is necessry to raise r^2 to 1?

[RichardCypher]

OK, I got it!
Bunch of thanks for your help!:biggrin: