Show that if p is a prime and p=2q+1, where q is an odd prime and a is a positive integer with 1 < a < p-1, then p-$\displaystyle a^2 $is a primitive root modulo p.
Note that $\displaystyle p \equiv 3 (\bmod. 4)$ what does this tell you about $\displaystyle -1$ ? and about $\displaystyle p-a^2$ ?
Next, prove that all non-quadratic residues module p (except for -1) must be primitive roots module $\displaystyle p$.
Hint : Count
Link the two parts.