# Can an element be a quadratic residue and a generator (mod p)?

i.e. is is possible for

• $g$ to be a generator$\mod{p}$, and
• $g \equiv x^2 \mod{p}$ for some $x$

I'm guessing not, as I think $x$ can't be expressed as a power of $g$, contradicting g being a generator?

-
Dear malikyo_o: Your argument is almost complete! You should try harder! – Pierre-Yves Gaillard Feb 5 '12 at 14:15

If $p$ is an odd prime, then no. $\varphi(p)=p-1$ is even and the multiplicative group $\!\!\!\pmod{p}$ has order $\varphi(p)$. If $g=x^2$, then $g^{(p-1)/2}=x^{p-1}=1\pmod{p}$. But if $g$ is a generator of the multiplicative group $\!\!\!\pmod{p}$, $g^k\not=1\pmod{p}$ for $0<k<p-1$.
In fact, the only $p$ for which $\varphi(p)$ is odd is $p=2$, and $1=1^2$ is a generator for the multiplicative group $\!\!\!\pmod{2}$. For all other $p$, $g=x^2$ cannot be a generator of the multiplicative group $\!\!\!\pmod{p}$.
If you consider $p=2$ to be a prime number (and I wouldn't know how you could defend not doing so) then you will see that $1$ is both a quadratic residue and a generator mod $2$ (admittedly not very spectacular, but true nontheless). This is the only case, as explained the answer by robjohn.
I have added that $p$ is an odd prime in the first paragraph. Thanks for keeping me on my toes. – robjohn Feb 5 '12 at 14:53