4
$\begingroup$

This is my proof of the title statement. Is it correct?

Suppose $a$ is a primitive root and quadratic residue modulo $p$. Then by definition $$\operatorname{ord}_p(a)=p-1$$ But Euler's criterion states that $$a^{(p-1)/2}\equiv1\bmod p$$ which is impossible ($\frac{p-1}2<p-1$ for all odd primes $p$) and leads to a contradiction. Therefore, every primitive root is a quadratic nonresidue modulo an odd prime $p$.

I have another question. Is every quadratic nonresidue a primitive root?

$\endgroup$
  • 2
    $\begingroup$ Your proof is correct, provided that you can argue why your congruence is impossible. But the converse does not hold: not every quadratic nonresidue is a primitive root. There are $\left(p-1\right)/2$ quadratic nonresidues but only $\varphi\left(p-1\right)$ primitive roots. $\endgroup$ – darij grinberg Oct 24 '16 at 4:30
  • 1
    $\begingroup$ For your last question, note that if $p\equiv3\pmod4$ then $-1$ is a quadratic nonresidue that is never a primitive root if $p>3$. You could also simply enumerate the primitive roots and quadratic (non)residues modulo $13$, for example, to gain some insight. $\endgroup$ – Greg Martin Oct 24 '16 at 4:46
2
$\begingroup$

Using Euler's criterion might be correct but seems a little overpowered. You could fairly easily achieve the result by assuming that $a$ is a quadratic residue and then considering the order of $b$ (defined by $b^2 \equiv a \bmod p$):

Suppose $b$ is a primitive root. Then $b^{p-1}\equiv 1 \bmod p$, but since we know that $p-1$ is even, it will be the case that $a^{(p-1)/2} \equiv b^{p-1}\equiv 1$ also, so $a$ is not a primitive root.

Now suppose $b$ is not a primitive root; therefore there is some $k<p-1$ such that $b^k \equiv 1$. Then $a^k \equiv b^{2k} \equiv 1^2 \equiv 1$ and $a$ is again not a primitive root.

This gives us: $a$ is a quadratic residue$\bmod p \implies a$ is not a primitive root$\bmod p$. Since $a$ cannot be both a quadratic residue and a primitive root, this proves the title claim.

To answer your other question, consider a prime $p>3$ with $p\equiv 3 \bmod 4$. Then $-1$ is a quadratic nonresidue but is of course not a primitive root. (In general there are plenty of quadratic nonresidues that are not primitive roots, but this is easy to demonstrate).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.