Primitive Root Proof

464 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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