1

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

Gary H
  • 81
  • 1
    please verify $(b),(c)$ – lab bhattacharjee Nov 12 '13 at 19:22
  • 3
    It would be nice of you to post your effort, and specify which are your doubts. – Ana Galois Nov 12 '13 at 19:25
  • Related : http://math.stackexchange.com/questions/256853/quadratic-reciprocity-and-proving-a-number-is-a-primitive-root, http://math.stackexchange.com/questions/517433/primitive-root-modulo-p-8t-3, http://math.stackexchange.com/questions/222098/let-p-q-be-odd-primes-with-p-2q-1-show-that-2-is-a-primitive-root-mod, http://math.stackexchange.com/questions/505737/primitive-root-modulo-4q-1 – lab bhattacharjee Nov 13 '13 at 16:08

1 Answers1

1

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

André Nicolas
  • 507,029