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

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

• Well, if $q$ were the set of all primes (Except p) or even just density more than half, then we know that $d$ is a square in the rationals. So we should assume the $q$ are sparse enough. Aug 16, 2020 at 20:21
• In the other direction, if the sequence $q_i$ is such that for every (squarefree?) $d$, the $q_i$ fill up more than half the residue classes modulo $d$, then again the condition can't be satisfied. Both these observations follow from the fact that for fixed $d$, exactly half the primes (and half the residue classes modulo $d$) split in $\mathbb Q(\sqrt(d))$. Aug 16, 2020 at 20:23
• Note that we can find a sequence of primes $q_i$ that fill up residue classes modulo $d$ for every $d$ but are very sparse among all primes: We just enumerate through each d and each residue class modulo $d$ and the choose the next prime to be in this residue class but very large otherwise. So these two conditions are really independent. Aug 16, 2020 at 20:50

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.

• Thanks very much, Aaron! In your example, I'm assuming that you took $p=3$ and $d=7$ just as convenient small numbers? Aug 20, 2020 at 3:42
• In those now deleted lines I took $p=3$ since it was small and $7$ as a prime which is $1 \bmod 2p.$ I was probably confused and thinking of this fact: The prime factors of $2^p-1$ are all $1 \bmod 2p.$ So you might be able to get results for certain instances of "the list of all prime factors of $2^p-1$ where $p$ is a prime congruent to $u \bmod v.$" But, again, only because that restricts congruence classes $\bmod 2d.$ Aug 20, 2020 at 18:43
• Ah, I see. Thanks for the update! I hadn't thought about the properties of generalized Fermat numbers before. It turns out -1 doesn't quite work for the application I wanted (see edit) but this gives me something I can work with! Aug 27, 2020 at 19:12
• (In particular this shows how to explicitly construct a sequence of integers $d_n$ that work for larger and larger $n$, and that seems like the next best thing. I'm still wondering if there's a single $d$ that works but I admit now that it seems unlikely!) Aug 27, 2020 at 19:21