Question 9.2.11 Elementary number theory David M burton

Question

The following question is from textbook David M Burton ( Elementary number theory) on page 185.

Given that $p$ and $q=4p+1$ are both primes, then prove any quadratic non-residue of $q$ is either a primitive root of $q$ or has order $4\pmod q$.

As a is quadratic non-residue so $-1 =a/q\equiv a^{2p} \pmod q $ but if I let that a is not a primitive root then how can I prove that a has order 4.

$a^{2p}\equiv -1 $ impllies order is not p, 2 , 2p but $ a^{4p}\equiv 1 \pmod q$ .

How to use both of these to prove that order is 4 mod q?

Can you please help!!

Answer 1

You have already proved that $a^{2p}\equiv -1\mod q$. Then $a^{4p}=1 \mod q$. Consider the multiplicative group $1,2,...,q-1$ modulo $q$. We have that $a^{4p}=1$ in that group. Hence the order of $a$ in that group divides $4p$. Hence the order is either $2$ or $4$ or $p$ or $2p$ or $4p$. Order $2$, $p$ or $2p$ are not possible because $a^{2p}=(a^2)^p\equiv -1\ne 1 (\mod q)$. Thus either the order of $a$ is $4$ or it is $4p=q-1$ modulo $q$. In the latter case $a$ is a primitive root.

Answer 2

It looks like it's pretty much done. And @player3236 pointed it out. Since $a^{4p}\equiv1\bmod q$, we know that the order of $a$ divides $4p$. Since you have ruled out everything else, the order must be $4$.