Quadratic reciprocity, exercised

Here is an amusing elementary property:

Let n and m be odd integers, and d such that n+m=d2, and d is congruent to 2 modulo 4; then
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left(\frac{d}{n}\right)=-\left(\frac{d}{m}\right)
where the left and right-hand sides are Jacobi symbols.

If n and m happen to be odd primes, then we have Legendre symbols, and then this property means that one, and only one, of the equations

y^2=d\ \mbox{mod}\ n


y^2=d\ \mbox{mod}\ m

has a solution. (For general n and m, we can only deduce that one of those equations has no solution).

Here is a hint for the proof: compute


using the reciprocity law for Jacobi symbols to check that it is  –(d/n). This requires to use all cases of the reciprocity law (namely, the “generic” law for odd moduli, and the supplementary laws for (2/d) and (-1/d) if d is odd). There might be another proof than this, of course, but it doesn’t seem easy to use, for instance, the concrete interpretation above, in the case where n and m are primes.

I don’t know if this is a well-known factlet about quadratic reciprocity. I only noticed it using computer experiments (then, of course, it wasn’t very long before I found the easy proof using the reciprocity law), as I wanted to check that, roughly, among the expressions d2=n+m, with d even and n and m odd primes, roughly half of the values of n were such that d is not a quadratic residue modulo n. When d was congruent to 2 modulo 4, the computer indicated that this was true of exactly half of the values, which only seemed plausible if the property above was true…

Incidentally, it is known by work of Perelli that, for any monic integral polynomial P of positive degree, which does not always take odd values, then for “most” positive integers n, P(n) is a Goldbach number if it is even, i.e., it is a sum of two primes, so for most d congruent to 2 modulo 4, we can indeed write d2=n+m with n and m both primes. This result refines, in a sense, the well-known fact – which goes back to van der Corput, Tchudakov and Estermann at least – that most even integers are sums of two primes; one proof of this, which is more or less a consequence of a suitably strong version of Vinogradov’s theorem on representations of odd integers as sums of three primes, is given in Chapter 19 of my book with Henryk Iwaniec.

(As to why I looked at this bizarre question, it is because of a question of Nguyen Ngoc Dong Quan, involving slightly more complicated conditions).

Published by


I am a professor of mathematics at ETH Zürich since 2008.

Leave a Reply

Your email address will not be published. Required fields are marked *