In Cox's book "Primes of form $x^2 + ny^2$", I stumbled upon a lemma
$
\newcommand{\Z}{\mathbb{Z}}
$
Lemma 1.14: If $D \equiv 0,1 \pmod{4}$ is a nonzero integer, then there is a unique homomorphism $\chi:(\Z/D\Z)^* \longrightarrow \{\pm 1\}$ such that $\chi([p]) = (D/p)$ for odd primes $p$ not dividing $D$. Furthermore, $\chi([-1]) = \operatorname{sign}(D)$.
One can prove this using quadratic reciprocity. But later on in one of the exercises, Cox suggests to prove quadratic reciprocity using this lemma – Problem 1.13 – we assume Lemma 1.14 holds for all nonzero $D\equiv 0,1 \mod4 $ and using this assumption we prove quadratic reciprocity.
He gives a hint, for two primes $p,q$, use $D=q^*=q(-1)^\frac{q-1}{2}$. Then $\chi = (q^*/\cdot)$ is one homomorphism, and $(\cdot/q)$ is another homomorphism from $(\Z/q\Z)^*$ to $\{\pm 1\}$. Since $(\Z/q\Z)^*$ is cyclic, there are only two homomorphisms from $(\Z/q\Z)^*$ to $\{\pm 1\}$. One of them is the trivial homomorphism, and the other one is the Legendre symbol, which is non-trivial. If they were equal then $\chi([p]) = (q^*/p)=(p/q)$ which proves quadratic reciprocity.
The only thing left to finish the proof would be to show that $\chi$ is not trivial. One way to do it is by showing that $\pm q$ is not a square modulo at least one prime coprime to $q$, but the only way I know to do that is either by using quadratic reciprocity or with an overkill using Chebotaryev.
Is there a simpler method to prove
For every odd prime $q$ there exists an odd prime $p$ such that $(q^*/p) = -1$.
or just
The unique homomorphism $\chi:(\Z/D\Z)^* \longrightarrow \{\pm 1\}$ that satisfies $\chi([p]) = (D/p)$ is not trivial when $D = q^*$.
Best Answer
If $D\equiv 0, 1\pmod{4}$, write $\chi_D$ for the homomorphism guaranteed by Lemma 1.14. Claim that if $q$ is an odd prime and $\chi_{q^*}$ is nontrivial, we have $\left(\frac{q^*}{p}\right) = \left(\frac{p}{q}\right)$ for any odd prime $p\ne q$. To prove the claim, note that both $\left(\frac{q^*}{\cdot}\right) = \chi_{q^*}$ and $\left(\frac{\cdot}{q}\right)$ are nontrivial homomorphisms from the cyclic group $(\mathbb{Z}/q\mathbb{Z})^*$ to $\{\pm 1\}$, so they must both be $-1$ on a generator and thus are the same map.
Now, let $p$ and $q$ be distinct odd primes. If at least one of them is $\equiv 3\pmod{4}$, assume WLOG that $q\equiv 3\pmod{4}$. Then $q^*<0$, so that $\chi_{q^*}$ is nontrivial (by the definition of $\chi([-1])$) and we are done. Otherwise, $p\equiv q\equiv 1\pmod{4}$, and $q^*=q$. If $\left(\frac{p}{q}\right)\ne \left(\frac{q}{p}\right)$, then exactly one of them is $-1$, say $\left(\frac{q}{p}\right)$ so that $\chi_{q^*}=\chi_q$ is nontrivial (since $\chi([p]) = -1$) and thus \begin{equation*} -1 = \left(\frac{q}{p}\right) = \left(\frac{q^*}{p}\right) = \left(\frac{p}{q}\right) \end{equation*} by the claim above, which is a contradiction.
(This is not my proof; in fact I got it from the author when I wrote him to ask about exactly this problem.)