Có thể tìm được một số nguyên (nonsquare) là một phần dư bậc hai trong một danh sách vô hạn các số nguyên tố đã cho không?

Question

Tôi tự hỏi liệu nó có thể không, với một p nguyên tố và một danh sách vô hạn các số nguyên tố $q_1$, $q_2$, ... để tìm một số nguyên d mà (1) không phải là mod bình phương p, nhưng (2) là mod bình phương$q_i$cho tất cả tôi. Luôn luôn đôi khi không bao giờ? Có lẽ đôi khi --- một số điều kiện là gì? Trong ứng dụng mà tôi nghĩ đến,$q_i$ là tất cả các ước số nguyên tố của các số $p^{2^n}-1$ vì n nằm trong khoảng từ 1 đến vô cùng, nhưng điều đó hơi linh hoạt.

(Nhân tiện, ứng dụng liên quan đến việc thực hiện phép nội suy p-adic của lũy thừa các số nguyên hữu tỉ và mở rộng nó thành các vòng số nguyên trong các tháp của các trường số.)

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