Can an integer pretend to be a square and yet not be a square? So let be an integer which is not a square – can it be a quadratic residue modulo every prime? No. Indeed, suppose
is squarefree (square factors don’t alter the property of being a square or quadratic residue) and write
. Suppose none of the
is 2 first. We want to find a prime
such that
. If
(n is prime), it’s easy because of the quadratic reciprocity law: if
,
so we just have to find
which is not a square modulo
, which is the case of about the half of the residues so it shouldn’t be too hard. In general, we can even find
with
and the Legendre symbol equal to +1 for the other primes: indeed,
then and it will be +1 if
. By Chinese remainder theorem, imposing a condition modulo each
(
for
here, and
for a fixed non-quadratic residue
) and modulo 4 amount to imposing a condition
with
.
And by Dirichlet’s theorem, there exists a prime number in this progression. If is even (
, say), we argue similarly except that we must replace the quadratic reciprocity law by
the formula . Thus we can for instance decide that
, thus for the odd factors
and we can ensure these symbols are all 1 by taking a number belonging to suitable classes.
It is not too easy to bound such a . In the case where
is prime, there is the terribly difficult Vinogradov’s conjecture which states that there should exist a
non quadratic residue modulo n. But then you have to find a prime number in the congruence classe
. Linnik’s theorem ensures the existence of a prime number
for some constant L (5.5 would do but it’s quite big, 2 is conjectured to work as well).
However, it’s a classical question in sieve theory (see an exercise in Tenenbaum’s book, chapter 4 or in Luca-de Koninck chapter 12) to ask how many there are such that
is a quadratic residue modulo every prime
. The answer is: between
(the number of squares) and
for some constant
. The necessary restriction to
is a feature of the large sieve. So there are certainly numbers who « pretend to be squares » but which are not.
Laisser un commentaire
Comments feed for this article