Return to Answer

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

Think first about this (easy) question. For fixed $d$ what are the 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

• maybe $2$
• 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. In your case of divisors of $3^{2^k}-1,$ I would guess against. There are twelve residues relatively prime to $28.$ Of these six accept $7$ as a quadratic residue and six do not. Up to $k=8,$ the twelve odd divisors of $3^{2^k}-1,$ are all $5,13,17,25 \bmod 28.$ That seems unlikely to be chance. As it turns out, $7$ is actually a quadratic non-residue relative to eleven of the twelve.

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.

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.

For a specific list of primes it is unlikely to be true unless they are concentrated in a few congruence classes $\bmod 4d$ for some odd square-free $d.$ Even then it is unlikely.

Think first about this (easy) question. For fixed $d$ what are the 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

• maybe $2$
• 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. In your case of divisors of $3^{2^k}-1,$ I would guess against. There are twelve residues relatively prime to $28.$ Of these six accept $7$ as a quadratic residue and six do not. Up to $k=8,$ the twelve odd divisors of $3^{2^k}-1,$ are all $5,13,17,25 \bmod 28.$ That seems unlikely to be chance. As it turns out, $7$ is actually a quadratic non-residue relative to eleven of the twelve.

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.

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

Think first about this (easy) question. For fixed $d$ what are the 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

• maybe $2$
• 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. In your case of divisors of $3^{2^k}-1,$ I would guess against. There are twelve residues relatively prime to $28.$ Of these six accept $7$ as a quadratic residue and six do not. Up to $k=8,$ the twelve odd divisors of $3^{2^k}-1,$ are all $5,13,17,25 \bmod 28.$ That seems unlikely to be chance. As it turns out, $7$ is actually a quadratic non-residue relative to eleven of the twelve.

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.

Think first about this (easy) question. For fixed $d$ what are the 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

• maybe $2$
• 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. In your case of divisors of $3^{2^k}-1,$ I would guess against. It does seem that , up to $k=8,$ the odd divisors are $3,4,5,6 \bmod 7.$ This is more than half the classes but suspicious of not being random.

For a specific list of primes it is unlikely to be true unless they are concentrated in a few congruence classes $\bmod 4d$ for some odd square-free $d.$ Even then it is unlikely.

Think first about this (easy) question. For fixed $d$ what are the 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

• maybe $2$
• 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. In your case of divisors of $3^{2^k}-1,$ I would guess against. There are twelve residues relatively prime to $28.$ Of these six accept $7$ as a quadratic residue and six do not. Up to $k=8,$ the twelve odd divisors of $3^{2^k}-1,$ are all $5,13,17,25 \bmod 28.$ That seems unlikely to be chance. As it turns out, $7$ is actually a quadratic non-residue relative to eleven of the twelve.

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.