0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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