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, 06: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, 07:12 PMThePerfectHacker
I think the proof would be a lot easier if you $\displaystyle n$ was an odd prime. Anyway, if $\displaystyle r$ is a primitive root then,

$\displaystyle \{r,r^2,...,r^{n-1} \}$

Contains all the elements of $\displaystyle n$

But since $\displaystyle r$ is a quadradic residue.

That means $\displaystyle r^k$ is a quadradic residue.

Then all numbers $\displaystyle 1\leq j\leq n$ are quadradic residues of $\displaystyle n$, which is surly not possible unless $\displaystyle n=1,2$.

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

$\displaystyle r^{\frac{p-1}{2}}\equiv 1(\mbox{ mod }p)$

But that is not possible because the order of $\displaystyle r$ is $\displaystyle p-1$.