# A prime number is not a quadratic residue modulo some prime without quadratic reciprocity

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^*$$.

• If every odd prime, distinct from $q$, was a square then every odd integer, prime to $q$, would be a square.
– lulu
Aug 30, 2019 at 10:43
• That's true, but the question is about $q$ (actually $q^*$) being square modulo other primes $p$, not about the other primes being squares modulo $q$. You proved that $(\cdot/q)$ is not trivial, which I already take for granted. Aug 30, 2019 at 10:53
– lulu
Aug 30, 2019 at 11:07
• As you say, the usual proofs that an integer which is a square for all, or nearly all, primes, is actually a square use quadratic reciprocity or something comparable. I don't see how life gets simpler if you restrict to primes (up to sign).
– lulu
Aug 30, 2019 at 11:10

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.
• I believe you wanted to say "since $\chi([p]) = -1$ in the case when they're both $\equiv 1 \mod{4}$, and that would make it a non-trivial homomorphism which makes it equal to $(\cdot / q)$ so we get a contraddiction because we assumed $\chi([p])=-1\not=1=(p/q)$. Aug 30, 2019 at 14:27
• However there is one little detail. The author says, in the lemma : Furthermore $\chi([-1]) = \operatorname{sign}(D)$. The way this is stated it seems to me that this "furthermore" is provable just from the hypothesis. Can one prove that $\chi([-1]) = -1$ for negative $D$ (or just $-q$ when $q\equiv 3 \mod{4}$). Aug 30, 2019 at 14:30
• Usually when one says "There is a unique $A$ having property $B$. Furthermore $A$ has property $C$", they mean that the property $C$ is implied from $A$ and $B$. Otherwise one would just say $A$ has property $B$ and $C$. In this particular case $C$ being the $\chi([-1])=-1$ is crucial to proving quadratic reciprocity, but maybe it's not needed, and in itself is a corollary of the properties defining $\chi$. Aug 30, 2019 at 14:44
• I agree with the distinction you make, but still don't see how it makes a difference in the proof. In either reading, there is a unique homomorphism, and in either reading, $\chi([-1]) = \mathop{sign}(D)$. If you think something is incorrect in the proof, perhaps you can point to the specific thing that is wrong. Aug 30, 2019 at 14:46