Let
\(p\) be a prime of the form
\(p=2q+1\text{,}\) where
\(q\) is prime (recall that
\(q\) is called a Germain prime in this case). Show that
every residue from 1 to
\(p-2\) is either a primitive root of
\(p\) or a quadratic residue. (Hint: Use
Euler’s Criterion, and ask yourself how many possible orders an element of
\(U_p\) can have.)