# Primitive root relation

This was a true false problem in class quizz today, and it goes if $a$ is a quadratic non residue $\bmod p$ then it is a primitive root $\bmod p$. I said its true but I dont know why can anyone tell me how to show this?

You need to think a bit carefully about this, I think. Have you tried some examples, and what did you find?

Hint: How many elements of a cyclic group of order $p-1$ are generators? How many quadratic non-residues are there $\bmod p$?

Do you know that no easy method is known for finding a primitive root modulo a given prime?

To analyse further.

The number of generators of the multiplicative group of units $\bmod p$ - which is a cyclic group of order $p-1$ - is $\varphi (p-1)$. This in turn is $$(p-1)\prod\frac {q_i-1}{q_i}$$ where the product is taken over the distinct prime factors of $p-1$.

If $p$ is odd, $p-1$ is even and the product contains the factor $\frac 12$. If $p-1$ has a prime factor other than $2$ then $\varphi (p-1) \lt \frac {p-1}2$.

The number of quadratic non-residues is equal to the number of quadratic residues, and is therefore $\frac {p-1}2$.

The only case in which every non-residue is a primitive root is therefore when $p-1$ is a power of $2$ ie is a Fermat Prime - known values are $3,5,17,257,65537$. In other cases there are non-residues which are not primitive roots.

Malcolm's answer comes at this from a different direction, and - given that you have a primitive root - shows how to find counterexamples. The smallest is for $p=7$ ($3$ and $5$ are excluded as counterexamples above). Also implicit in Malcolm's answer is the observation that $-1$ is neither a primitive root nor a quadratic residue modulo any prime $p\equiv 3 \bmod 4$ which gives an easy family of counterexamples.

You cannot prove it because it is false.

Consider any primitive root $g$ $\mod p$ for an odd prime $p$.

$a = g^k \mod p$ is a quadratic non-residue if $k$ is odd.

$a$ is a primitive root iff $\gcd(k,p-1) = 1$.

So any odd $k$ with $\gcd(k,p-1) \neq 1$ will furnish a counter-example.

Example: $-1$ is not a quadratic residue $\mod 7$ ($7 = 3 \mod 4$), but it is also not a primitive root $\mod 7$.

Maybe you meant the other direction? If $a$ is a quadratic residue then $a^{(p-1)/2}=1$, so its order cannot be $p-1$, so it cannot be a primitive root.