quadratic nonresidue proof with primitive roots

ilikecandy · #1 $Old$ November 14th, 2009, 01:49 PM

Let p be an odd prime. Prove that every primitive root of p is a quadratic nonresidue. Prove that every quadratic nonresidue is a primitive root if and only if $p$ is of the form $2^{2^n} + 1$ where $n$ is a non-negative integer, that is, if and only if $p=3 \mbox{ or } p$ is a Fermat number.

I have no clue what to do.

chiph588@ · #2 $Old$ November 14th, 2009, 02:35 PM

Assume a primitive root $g$ modulo $p$ is a QR. Then there exists an $x$ such that $x^2 \equiv g \mod{p}$ . But then $g^{\frac{p-1}{2}} \equiv (x^2)^{\frac{p-1}{2}} \equiv x^{p-1} \equiv 1 \mod{p}$ . Hence we just showed $g$ has an order less than $\phi(p)=p-1$ . Therefore we've reached a contradiction.