From Apostol Chapter $10$ q$6$:
Assume $m>2$, $(a,m)=1$ and there exists an $x$ such that $x^2\equiv a \pmod m$.
Prove that $x^2\equiv a \pmod m$ has exactly two solutions iff $m$ has a primitive root.
I can do the "if" part by explicitly showing that if $g$ is a primitive root of $m$ then if $g^k$ is a soln then $g^{k+\phi(m)/2}$ is the other distinct soln and any soln is congruent to one or the other.
However no progress on the "only if" part.