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

  • 1
    $\begingroup$ If every odd prime, distinct from $q$, was a square then every odd integer, prime to $q$, would be a square. $\endgroup$
    – lulu
    Commented Aug 30, 2019 at 10:43
  • $\begingroup$ 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. $\endgroup$
    – Kolja
    Commented Aug 30, 2019 at 10:53
  • $\begingroup$ Ah, right. Read the question backwards. Sorry about that. $\endgroup$
    – lulu
    Commented Aug 30, 2019 at 11:07
  • 2
    $\begingroup$ 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). $\endgroup$
    – lulu
    Commented Aug 30, 2019 at 11:10

1 Answer 1


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.)

  • $\begingroup$ 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)$. $\endgroup$
    – Kolja
    Commented Aug 30, 2019 at 14:27
  • $\begingroup$ 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}$). $\endgroup$
    – Kolja
    Commented Aug 30, 2019 at 14:30
  • 1
    $\begingroup$ @Kolja: Fixed for your first comment. For the second, I'm not sure I understand. We are assuming that Lemma 1.14 holds in its entirety, so why does that statement need to be justified? $\endgroup$
    – rogerl
    Commented Aug 30, 2019 at 14:37
  • $\begingroup$ 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$. $\endgroup$
    – Kolja
    Commented Aug 30, 2019 at 14:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – rogerl
    Commented Aug 30, 2019 at 14:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .