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!


  • 3
    $\begingroup$ 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. $\endgroup$
    – Asvin
    Aug 16, 2020 at 20:21
  • 3
    $\begingroup$ 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))$. $\endgroup$
    – Asvin
    Aug 16, 2020 at 20:23
  • 3
    $\begingroup$ 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. $\endgroup$
    – Asvin
    Aug 16, 2020 at 20:50

1 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.

  • $\begingroup$ Thanks very much, Aaron! In your example, I'm assuming that you took $p=3$ and $d=7$ just as convenient small numbers? $\endgroup$ Aug 20, 2020 at 3:42
  • $\begingroup$ 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.$ $\endgroup$ Aug 20, 2020 at 18:43
  • $\begingroup$ 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! $\endgroup$ Aug 27, 2020 at 19:12
  • $\begingroup$ (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!) $\endgroup$ Aug 27, 2020 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.