Suppose p and q4p1 are both primes If a is a quadratic nonre

Suppose p and q=(4p+1) are both primes. If a is a quadratic non-residue of q, show that a is either a primitive root of q, or that a has order 4.

Solution

By Fermat\'s little theorem the order of a divides q-1 = 4p.

Since (Z/q)* is cyclic generated by some primitive root g, and a is a nonresidue mod q then a = g^(odd power), and a^(2p) = a^((q-1)/2) = (g^(2r+1))^((q-1)/2) g^((q-1)/2) -1 mod q. This implies that a^p 1 mod q and a^2 1 mod q.

So the possible orders of a are 4p and 4, and if a has order 4p = q-1 then it is also primitive root mod