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
    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
    Aug 30, 2019 at 10:53
  • $\begingroup$ Ah, right. Read the question backwards. Sorry about that. $\endgroup$
    – lulu
    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
    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
    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
    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
    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
    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
    Aug 30, 2019 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.