Quadratic non-residues

First quadratic reciprocity and CRT tells us that there is a congruence class for p that ensures (2/p) = 1 but (q/p) = -1 for each prime q from 3 to 31 inclusive (for instance, choose p to be 1 mod 8 and congruent to a non-residue mod q for each choice of q). Dirichlet's theorem ensures that primes indeed exist in this congruence class, and we easily verify that the 20 numbers $\{3,5,6,7,10,11,12,13,14,17,19,20,22,23,24,26,27,28,29,31\}$ are non-residues mod p.

It remains to show that 31 is minimal, so we want to show there are at most 19 non-residues in {1,2,...,30} for any choice of p, or at least 11 residues. For our purposes we'll consider 0 to be a quadratic residue. Then 5 perfect squares are obvious, so we need to identify at least 6 more residues among the non-squares up to 30.

Suppose that 2 is a NON-residue mod p. Then at least one of each pair (3,6), (5,10), (7,14), (11,22), (13,26), (15,30) is a residue (possibly both if p divides them). Since none of these was counted as a square, this gives us the required 6.

We may henceforth assume that 2 is a quadratic residue, and thus so are 8 and 18, and we only need 3 more specimens. Like before, if 3 is a NON-residue mod p then at least one of (5,15), (7,11), and (10,30) is a residue, giving the required 3.

Finally, if both 2 and 3 are residues mod p, then so are 6, 12, and 24, again giving us 3 further residues. In all cases we have at least 11 quadratic residues in {1,...,30}, so having 20 non-residues is impossible.

Let's start with showing that the solution $n$ can not be less than 31.

We use the fact that:

Modulo a prime, the product of two quadratic residues is a residue, the product of a residue and a nonresidue is a nonresidue, and the product of two nonresidues is a residue. (see e.g. http://en.wikipedia.org/wiki/Quadratic_reciprocity ).

Let's assume that there is an $n$ with $26 \leq n \leq 30$ with the property that for some prime $p$ there are at least 20 quadratic non-residues. It is easy to see that $p$ will be certainly greater than 30 using the fact that half of the positive integers less than $p$ are non-residues (and if not, we can easily check all primes less than 30, that none of them has 20 or more non-residues less than 30).

From the $n$ numbers:

1. The squares 1, 4, 9, 16 and 25 are quadratic residues (since $p > 25$ )
2. If 2 is a non-residue: One number from each of the pairs: (3, 6), (5, 10), (7, 14), (11, 22), (12, 24), (13, 26) will be quadratic residue (based on the facts above about products of residues and non-residues)
3. If 2 is a residue: 8 ( $= 2 \times 4$ ) and 18 ( $= 2 \times 9$ ) are residues. If 3 is a residue, also 6 ( $2 \times 3$ ), 12 ( $2 \times 6$ ) and 24 ( $2 \times 12$ ) will be residues, if 3 is non-residue, one number from each of the pairs (5, 15), (7, 21) and (10, 30) will be residues (the last one only relevant for $n = 30$ ).

In both cases 2 and 3 at least 5 numbers $\leq n$ (and for $n = 30$ : 6 numbers $\leq 30$ ) will be residues, and with the 5 squares from 1 this leaves only space for at most 19 non-residues.

For $n \leq 25$ , with similar reasoning it can be seen much easier that we can not have 20 non-residues $\leq n$ for any prime $p$ .

So we are looking now for an $n$ that is at least 31. Let's try to find if there exists a $p$ such that 20 numbers $\leq 31$ are quadratic non-residues. With similar reasoning as above we can achieve this if we can find (or show that there exists one) prime p, for which 2 is a residue and all other primes between 3 and 31 are non residues. By using the multiplication rules, this would mean that:

• 1, 2, 4, 8, 9, 15, 16, 18, 21 25 and 30 are quadratic residues of p
• 3, 5, 6, 7, 10, 11, 12, 13, 14, 17, 19, 20, 22, 23, 24, 26, 27, 28, 29 and 31 are quadratic non-residues of $p$ (that is 20 numbers $\leq 31$ )

The numbers, modulo which a given prime $p$ is quadratic residue or quadratic non-residue are parts of arithmetic progressions (see e.g. http://en.wikipedia.org/wiki/Quadratic_reciprocity#Euler ), and the step of the progressions for different primes are coprime (except a possible factor 4 if $p \equiv 3$ mod 4). Also, it is important that for $p \equiv 3$ mod 4 (for which we have the factor 4 in the step), there are such progressions both with step $\equiv 3$ mod 4 and step $\equiv 1$ mod 4. Because of these properties, we can combine at least one progression for each of the primes $p$ that we are interested in, and get at least one global arithmetic progression for which 2 is a quadratic residue and all other primes from 3 to 31 are quadratic non-residues.

For better understanding, here a smaller example:

• 2 is residue for $p = 8 * a + 1$
• 3 is non-residue for $p = 12 * b + 5$
• 5 is non-residue for $p = 5 * c + 2$

Combining these gives us: 2 is quadratic residue and 3, 5 quadratic non-residues for every $p = 120 * k + 17$ .

Disclaimer - this last step was only the outline of a proof, it would need some more details for a complete formal proof that we can generate an arithmetic progression that has a specified set of primes being residues and another specified set of primes being non-residues.

Now, after we combine these as outlined above to get an arithmetic progression with numbers, for which 2 is a quadratic residue, and 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 are quadratic non-residues (and the step of the progression is coprime to the offset), with Dirichlet's Theorem on arithmetic progressions ( http://en.wikipedia.org/wiki/Dirichlet theorem on arithmetic progressions ) we see that there will be infinitely many primes in this progression. For these primes, the 20 numbers shown above $\leq 31$ will be quadratic non-residues.

In other words, we found that there must exist a solution with $n = 31$ , and no solution with $n \leq 30$ , so 31 must be the answer.

q.e.d.

First note that for $p = 41$ we get $n$ as small as $40$ , since precisely one half of the numbers upto $40$ will be residues (this is because squaring is a two-to-one map, $x^2 = (-x)^2$ ).

But we can do much better than this. The key observation is that by selecting an appropriate prime $p$ , we can force any of the prime contained in $1,2, \dots, n$ to be either residue or not, as we desire.

This is not obvious but it follows directly from quadratic reciprocity when $p = 4n + 1$ : a prime $q$ is a quadratic residue $\mod p$ precisely when $p$ is a quadratic residue $\mod q$ . Using quadratic reciprocity will then lead to a number of modular equations which can be solved to find $p$ we desired. Note that we don't actually need to find $p$ to solve this problem, fortunatelly. It's enough that such a prime exists.

Another important fact is that product of two numbers is a quadratic residue precisely when both of those numbers are either quadratic residues or quadratic non-residues. If one of the numbers is a quadratic residue and the other isn't, the product is a quadratic non-residue.

Putting all of this together, let us describe the solution: pick a prime $p$ such that $2$ is a quadratic residue $\mod p$ and all other primes in $3, 4, \dots, 40$ are quadratic non-residues. Using the above property of multiplication, it is then easy to find all of the quadratic residues $\mod p$ . They are $1, 2, 4, 8, 9, 15, 16, 18, 21, 25, 30, 32$ (e.g. $15 = 3 \cdot 5$ and both $3$ and $5$ are quadratic non-residues, so $15$ is a quadratic residue). We can stop here, because this already gives the solution $n = 31$ .

Now the only loose strand is whether we cannot do better than this by prescribing which primes are quadratic residues in a different way. This is again not obvious, but intuitively it should be clear: we would like all the primes to be quadratic non-residues but the properties of their multiplication would then force many of the composites to be quadratic residues and ultimately increase $n$ . This is why we picked $2$ to be a quadratic residue -- many even numbers will then be quadratic non-residues.

We will show that the smallest such number $n$ is $31.$

Lemma. There exists a prime $p$ such that the following numbers are quadratic non-residues modulo $p:$ $3,6,12,24,27;5,10,20;7,14,28;11,22;13,26;17;19;23;29;31$

Proof. We are looking for a prime $p$ such that $2$ is quadratic residue modulo $p$ and all odd primes from $3$ to $31$ are quadratic non-residues. Recall that $2$ is a quadratic residue modulo $p$ if an only if $p\equiv \pm 1 \pmod 8.$ We will look for a prime $p$ which is $1 \pmod 8.$ By the quadratic reciprocity law, each of the remaining conditions is equivalent, for such prime $p$ to a non-empty condition on $p$ modulo the corresponding prime. By the Chinese remainder theorem, there exists a number modulo $N=8\cdot 3 \cdot 5\cdot ... \cdot 31$ , coprime to $N,$ such that every prime $p$ with that remainder modulo $N$ satisfies the desired properties. The Dirichlet theorem on primes in arithmetic progression guarantees that such a prime exists.

Note that the above arrangement is more efficient than if we required $2$ to also be a non-residue (we are losing some numbers, like $2,8,18,30$ but gaining more: $6,24,10,14,22,26$ ).

We now want to show that out of the numbers $1,2,...,30$ there can be no more than $19$ quadratic non-residues. This is equivalent to having at least $11$ quadratic residues. We have $5$ of them automatically: $1,4,9,16,25.$ In what follows, we use the fact that the product of two non-residues is a residue. Consider two cases.

Case 1. $2$ is a non-residue. Then from each of the $6$ pairs of numbers $(3,6),$ $(5,10),$ $(7,14),$ $(11,22),$ $(13,26),$ $(15,30),$ exactly one is a quadratic residue. So we have at least $5+6=11$ quadratic residues.

Case 2. $2$ is a quadratic residue. The so are $8$ and $18$ , so we have found $8$ quadratic residues. Consider two sub-cases.

Case 2a. $3$ is a quadratic non-residue. Then one of the numbers in each of the following pairs is a quadratic residue: $(5,15),\ (7,21),\ (10,30).$ Together with the $8$ quadratic residues that we already found, we get $11.$

Case 2b. $3$ is a quadratic residue. Then so are $12$ and $27$ , so, again, we have found $11$ quadratic residues.

So $n$ cannot be $30$ and, therefore, cannot be any smaller number. Therefore, the answer is $31.$

Ricky claims that $p=5297$ satisfies the conditions.

dtju