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!!!
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$.