1
$\begingroup$

What are the proofs for the following:

Let $p$ and $q$ be odd prime numbers with $q=2p+1.$

(a) Prove that $-4$ is a primitive root modulo $q$.

(b) If $p\equiv 1\pmod 4$, prove that $2$ is a primitive root modulo $q$.

(c) If $p\equiv 3\pmod 4$, prove that $-2$ is a primitive root modulo $q$.

$\endgroup$

closed as off-topic by leo, Bruno Joyal, Dominic Michaelis, Daniel Robert-Nicoud, egreg Nov 13 '13 at 21:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – leo, Bruno Joyal, Dominic Michaelis, Daniel Robert-Nicoud, egreg
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

I believe you want to specify that $p$ and $q$ are prime. For one thing, if $q$ is not prime it may not even have a primitive root. We continue, on the assumption $p$ and $q$ are odd primes. We solve the first problem only, in detail, in the hope that will help you deal with the other two. (They use very similar ideas.)

Note that since $p$ is odd, $q$ is of the shape $4k+3$.

There are $\varphi(\varphi(q))$ primitive roots of $q$. This is $\varphi(2p)$, which is $p-1$. There are $((2p+1)-1)/2=p$ quadratic non-residues of $q$.

Since every primitive root is a NR, all non-residues except one are primitive roots. Note that $-1$ is a NR of $q$, since $q$ is of the form $4k+3$.

Thus every NR except $-1$ is a primitive root of $q$. Since $-1$ is a NR, so is $-4$. It follows that $-4$ is a primitive root of $q$.

$\endgroup$

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