# No canonical non-quadratic residue for primes $\equiv 1 \bmod 8$?

Let $p$ be an odd prime number.

• If $p \equiv 3 \bmod 8$ or $p \equiv 5 \bmod 8$, $2$ is not a square mod $p$.
• If $p \equiv 3 \bmod 8$ or $p \equiv 7 \bmod 8$, $-1$ is not a square mod $p$.

If $p \equiv 1 \bmod 8$, there seems to be no way to choose a single $n \in \mathbb{Z}$ such that $n$ is not a square mod $p$ regardless of the choice of $p$. Can one prove that this is not the case? What if we continue searching for residues mod 16?

In fact, the more general question I would like to know the answer to, is the following: Can there be a finite set of natural numbers $S$ such that that for each prime number $p$, there exists an $n \in S$ such that $n$ is not a square mod $p$?

• I suspect not ... probably that follows from quadratic reciprocity. Apr 4, 2018 at 17:47

In other words given a finite set of numbers $$S$$ find a prime $$p$$ such that for all $$n\in S$$, $$n$$ is a quadratic residue modulo $$p$$. Now from quadratic reciprocity we have that

$$\left(\frac{n}{p}\right)=1 \Leftrightarrow p\equiv a_i \text{ (mod 4n)}$$ where $$a_i$$ are some numbers depending on $$n$$.

It then follows from Dirichlet's theorem on primes in an arithmetic progression that there are infinitely many such primes.

• This is not quite right, but the idea is fine and the details can be salvaged. If $n$ is odd then reciprocity only gives you a list of residues modulo $4n$, not $n$. So you do need to take more care in reconciling the congruences since they are not relatively prime moduli. You also do not have a priori any assumption that the values of $S$ are relatively prime, so it does depend somewhat on how $a_i$ are distributed. Apr 4, 2018 at 18:20
• @ErickWong This is a spurious criticism, in fact there is no problem with the moduli. If you want both residues and non residues the you need some assumptions. Anyway this is a well known result in algebraic number theory. Apr 4, 2018 at 18:24
• It is not a spurious criticism. You wrote down an if-and-only-if condition that is patently false (what is the list of $a_i$ for $n=2$ or $n=3$?). Of course I know it is a well-known result: my first sentence was that the idea can be salvaged, indicating that the final result is true. Apr 4, 2018 at 18:25
• I have removed my downvote, but I still feel there is a gap between the existence of $a_i$ and the appeal to Dirichlet's theorem. It should be justified that we won't encounter a situation where, say, $p$ must be simultaneously one of $1,5 \pmod {8}$ and also $3,7,11 \pmod {12}$, which are inconsistent. tt's true that this won't actually happen as a consequence of the $a_i$ arising purely from quadratic residuosity constraints, but it isn't stated anywhere that there are any constraints on the $a_i$. Apr 5, 2018 at 1:57
• @ErickWong Thank-you. My answer was not intented as a line by line complete proof. However the argument I have in mind is to add to the set $-1$ (and $2$ if you wish) and to replace all other numbers by their prime divisors. Then you have for a candidate $p$, $\left(\frac{q}{p}\right)=\left(\frac{p}{q}\right)$ and to make this latter $+1$ chose any residue classes and then use the Chinese remainder theorem. The modulus and class will be relatively prime, assuming you do not chose a class $\equiv 0(\mod q)$. But as you point out in your answer chosing $\equiv 1$ in all cases in much simpler. Apr 5, 2018 at 2:54

A simple consequence of quadratic reciprocity is that if $n$ is odd, then $$p \equiv 1 \pmod{4n} \implies \left(\frac{n}{p}\right)=1.$$

Pair this together with $p \equiv 1 \pmod 8 \implies \left(\frac{-1}{p}\right)=\left(\frac{2}{p}\right)=1$, and it's easy to see that for any finite set $S$, we can take $N$ to be the lcm of all elements of $S$, and then for any prime $p \equiv 1 \pmod{8N}$ the entirety of $S$ will be quadratic residues modulo $p$.

This also helps to explain why you are having particular difficulty finding a generic non-residue for primes congruent to $1$ mod $8$.

• Downvote reason? Apr 4, 2018 at 18:34
• Why do you have $4n$ ? Cause $n$ may be negative ? Apr 4, 2018 at 18:43
• Oh, I think I get your point now. Apr 4, 2018 at 18:50
• @ReneSchipperus It's because the characters of $p$ and $n$ mod $4$ are key to the statement of quadratic reciprocity. Apr 4, 2018 at 18:50