Prove that a primitive root r modulo n cannot be a quadratic residue.

I've no idea how to prove it, pls help, thx very much!!! :)

Printable View

- Dec 3rd 2006, 07:34 PMsuedenationprimitive root and quadratic residue
Prove that a primitive root r modulo n cannot be a quadratic residue.

I've no idea how to prove it, pls help, thx very much!!! :) - Dec 3rd 2006, 08:12 PMThePerfectHacker
I think the proof would be a lot easier if you was an odd prime. Anyway, if is a primitive root then,

Contains all the elements of

But since is a quadradic residue.

That means is a quadradic residue.

Then all numbers are quadradic residues of , which is surly not possible unless .

Note: By odd primes the proof is extremely simple if is a quadradic residue then,

But that is not possible because the order of is .