3
$\begingroup$

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?

  • 3
    Dear malikyo_o: Your argument is almost complete! You should try harder!2012-02-05

2 Answers 2

4

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.

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

0

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.

  • 0
    I have added that $p$ is an odd prime in the first paragraph. Thanks for keeping me on my toes.2012-02-05