2
$\begingroup$

Suppose that $p$ and $q = 2p + 1$ are both odd primes. Show that the $p − 1$ primitive roots of $q$ are precisely the quadratic non-residues of $q$, other than the quadratic non-residue $2p$ of $q$.

I think I probably need to use the fact that $q$ is congruent to $3 \rm\, mod\, 4$, but I've been fiddling around with definitions and can't quite seem to get anywhere. Any help would be greatly appreciated. Thanks!

$\endgroup$
1
$\begingroup$

You are possibly familiar with the result that says that if $n$ has a primitive root, then $n$ has $\varphi(\varphi(n))$ primitive roots.

In the case $q=2p+1$, the number of primitive roots of $q$ is therefore $\varphi(2p)$, which is $p-1$. But $p-1=\frac{q-1}{2}-1$. Since there are $\frac{q-1}{2}$ quadratic non-residues of $q$, and every primitive root is a non-residue, it follows that all but one of the non-residues is a primitive root.

Since $q$ is of the form $4k+3$, we know that $-1$ is a non-residue. But $-1$ is not a primitive root of $q$, since $q\gt 3$. So $-1$ is the only non-residue which is not a primitive root.

$\endgroup$
0
$\begingroup$

HINT: The multiplicative group of non-zero residues mod $q$ is cyclic and has order $2p$. The possible orders of elements are $1,2,p,2p$ since $p$ is prime [this is where $p$ being prime comes in]. You need to work out which elements have which order, which is simply an analysis of the cyclic group.

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