Is it possible to find a (nonsquare) integer which is a quadratic residues modulo a given infinite list of primes?

Question

I'm wondering if it's possible, given a prime p and an infinite list of primes $q_1$, $q_2$, ... to find an integer d which (1) is not a square mod p, but (2) is a square mod $q_i$ for all i. Always, sometimes, never? Probably sometimes --- what are some conditions? In the application I have in mind, the $q_i$ are all the prime divisors of the numbers $p^{2^n}-1$ as n ranges from 1 to infinity, but that's somewhat flexible.

(The application, by the way, involves taking a p-adic interpolation of exponentiation of rational integers, and extending it to rings of integers in towers of number fields.)

[ETA: I forgot to mention that d should also be a square mod 8 for the application, which rules out the answer of -1 given below.]

• For a finite list, d can be constructed using the Chinese Remainder Theorem, but that doesn't seem to help here.

• Given d, quadratic reciprocity gives an infinite set of primes for which d is a square, but I need the primes specified first.

• Grunwald-Wang says, if I understand it correctly, that condition (1) implies that d is not a square modulo $q$ for infinitely many primes $q$, but doesn't say anything about primes which d is a square for.

• The Chebotarov Density Theorem seems to imply that the set of possible d has density zero, but doesn't rule out (or imply) that one such d exists.

Thanks for any help, sources, or advice!

----Josh

Answer 1

It depends on the given list of primes. A simpler but necessary condition is that there be a $d$ so that all the primes of the list (greater than $d$) are concentrated in a few congruence classes $\bmod 4d.$ We can stick to odd prime divisors since everything is a quadratic residue $\bmod 2.$

If the list is all primes congruent to $1 \bmod 4$ then $-1$ is a common quadratic residue. That probably doesn't seem very exciting.

If the list is all odd prime divisors of $3^{2^n}-1$ as $n$ ranges over the positive integers then $-1$ is again a common quadratic residue. That is the kind of thing you were mentioning. But the reason is that all those primes are $1 \bmod 4$

If I am not mistaken, and for the same reason, $-1$ is a common quadratic residue of of the prime divisors of $p^{2^n}-1$ as $n$ ranges over the integers starting at $2.$

For certain primes , such as $5,7,17,19,31,53,59$ we can expand the list to all prime divisors of $p^{2^n}-1$ with the exception of $3.$ In general it is sufficient to discard any divisors of $p^2-1$ which are $3 \bmod 4.$

The facts behind this are

• $p^{2^n}-1=(p-1)(p+1)(p^2+1)(p^4+1)\cdots(p^{2^{n-1}}+1)$
• every odd factor of $p^{2^m}+1$ is of the form $2^{m+1}q+1$
• $-1$ is a quadratic residue for primes which are $1 \bmod 4.$

---

Think first about this (easy) question. For fixed $d$ what are the odd primes $q$ such that $d$ is a quadratic residue $\bmod q?$ Call this set $G_d.$ We may assume that $d$ is squarefree.

Then the members of $G_d$ are the prime divisors of $d$ along with those primes in a union of certain congruence classes $\bmod 4d.$ Half of the classes $(r \bmod 4d)$ with $\gcd(r,4d)=1$

In some cases ($d$ even or $d$ odd with all divisors $1 \bmod 4$) it suffices to consider congruence classes $\bmod 2d$. However what is written is still correct. I will ignore your $p$ on the assumption that the goal was to rule out $d$ being a square.

Then the specific $d$ works for a particular instance of your problem, precisely if the chosen list is one of the uncountably many infinite subsets of $G_d.$

On the other hand, suppose it is given that the members of the list (other than the divisors of $d$ in the list, if any) are chosen from some $k \ll \phi(d)$ of the congruence classes $\bmod 4d$. Then, if the $k$ are chosen at random, the chance that $d$ will work is less than $2^{-k}$.

So starting from a list $\mathbf{q}=q_1,q_2,\cdots$ the first question is "Is there some reason to suspect that there is an $M$ so that all the members of $\mathbf{q}$ (prime to $M$) are concentrated in a few of the congruence classes $\bmod M?$" If that does not happen, then there is no hope. If it does happen for a certain $M,$ then chances still may be low.

So it very much depends on where $\mathbf{q}$ comes from.

By the way, the problem of finding a $d$ which is a quadratic non-residue relative to all $q \in \mathbf{q},$ is equally difficult.