lets consider $\mathbb{Z}_p^*$ with $p = 2 \cdot q + 1$ a safe prime ($p$ and $q$ have to be prime).
Then $\varphi\left(p\right) = 2 \cdot q$ is the order of $\mathbb{Z}_p^*$, and $\varphi\left(\varphi\left(p\right)\right) = q-1$ the number of generators in $\mathbb{Z}_p^*$.
Also there are exactly $\frac{p-1}{2} = q$ quadratic residue and $q$ non quadratic residue in $\mathbb{Z}_p^*$.

Now my question:

Is every non quadratic residue (except $-1$ if it is a nqr) a generator of $\mathbb{Z}_p^*$? (due to the fact, that we have $q-1$ generators and quadratic residues cannot be generators)

An affirmation or compelling arguments, why I am wrong, are very appreciated, thanks!


1 Answer 1


Indeed that is true, your counting argument does it. Since $p\equiv 3\pmod{4}$, we have that $-1$ is a non-residue. It is the only non-residue which is not a primitive root of $p$.

  • $\begingroup$ Very good, thank you. $\endgroup$
    – kaidowei
    May 15, 2012 at 19:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .