Can an integer pretend to be a square and yet not be a square? So let $n$ be an integer which is not a square – can it be a quadratic residue modulo every prime? No. Indeed, suppose $n$ is squarefree (square factors don’t alter the property of being a square or quadratic residue) and write $n=p_1\cdots p_k$. Suppose none of the $p_i$ is 2 first. We want to find a prime $q$ such that $(\frac{n}{q})=\prod (\frac{p_i}{q})=-1$. If $k=1$ (n is prime), it’s easy because of the quadratic reciprocity law: if $n=1 [4]$, $(\frac{n}{q})=(\frac{q}{n})$ so we just have to find $q$ which is not a square modulo $n$, which is the case of about the half of the residues so it shouldn’t be too hard. In general, we can even find $q=1[4]$ with $(\frac{p_1}{q})=-1$ and the Legendre symbol equal to +1 for the other primes: indeed, $(\frac{p_i}{q})=(\frac{q}{p_i})$ then and it will be +1 if $q=1[p_i]$. By Chinese remainder theorem, imposing a condition modulo each $p_i$ ($q=1[p_i]$ for $i>1$ here, and $q=a_{p_1}[p_1]$ for a fixed non-quadratic residue $a_{p_1}$) and modulo 4 amount to imposing a condition $q=b[4n]$ with $b\leq 4n$.
And by Dirichlet’s theorem, there exists a prime number in this progression. If $n$ is even ($p_1=2$, say), we argue similarly except that we must replace the quadratic reciprocity law by
the formula $(\frac{2}{q})=(-1)^{\frac{q^2-1}{8}}$. Thus we can for instance decide that $q=5[8]$, thus for the odd factors $(\frac{p_i}{q})=(\frac{q}{p_i})$ 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 $q$. In the case where $n$ is prime, there is the terribly difficult Vinogradov’s conjecture which states that there should exist a $q\leq\sqrt{n}$ non quadratic residue modulo n. But then you have to find a prime number in the congruence classe $q \text{ mod } n$. Linnik’s theorem ensures the existence of a prime number $\ll n^L$ 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 $n\leq x$ there are such that $n$ is a quadratic residue modulo every prime $p\leq\sqrt{x}$. The answer is: between $\lfloor\sqrt{x}\rfloor$ (the number of squares) and $C\sqrt{x}$ for some constant $C$. The necessary restriction to $p\leq\sqrt{x}$ is a feature of the large sieve. So there are certainly numbers who « pretend to be squares » but which are not.

Publicités