Combining disjoint congruences: $q\equiv \prod_ip_{u_i}^{r_{u_i}}\mod d$ and $q\equiv \prod_ip_{u_i}^{s_{u_i}}\mod p_{n+1}$

Question

I have partitioned the prime factors of $p_n\#$ -- using the typical primorial definition: $x\#$ is the product of all primes not greater than $x$ -- into two sets identified by product: $d,\frac{p_n\#}d$; assume that $d\gt 1$ and $\frac{p_n\#}d\gt 1$. I have reduced the problem I am working on down to the following: given $q,n$ such that $(q,p_{n+1}\#)=1$ and taking the sequence of prime factors of $\frac{p_n\#}d$ as $p_{u_i}$,

If there exist non-negative integers $r_{u_i},s_{u_i},i=1,2,\dots,\omega\left(\frac{p_n\#}d\right)$ such that $q\equiv \prod_ip_{u_i}^{r_{u_i}}\mod d$ and $q\equiv \prod_ip_{u_i}^{s_{u_i}}\mod p_{n+1}$, do there exist non-negative integers $t_{u_i}$ such that $q\equiv \prod_ip_{u_i}^{t_{u_i}}\mod dp_{n+1}$?

The potential counter-example I can think of involves $\varphi(d)=\varphi(p_{n+1})$, such as $d=55,p_{n+1}=41$, but where $q$ is a residue in different phases of $d,p_{n+1}$ so that there are no such $t_{u_i}$. Is this a reasonable scenario? If not, is there some way to conclude that $t_{u_i}$ must exist given the above conditions? Note that we can use induction since we have that the integers $t_{u_i}$ exist for $n=3$, so it is possible to work from that base case.

In particular, we can guarantee that $r_{u_i},s_{u_i}$ exist by induction, noting that there is at least one primitive root $z$ modulo $p_{n+1}$ which divides either $d$ or $\frac{p_n\#}d$; swap $d$ with $\frac{p_n\#}d$ if $z\mid d$.

Tough problem. I would maybe first start with $d=p_n#$ and seeing if it is true in that particular case. Have you been able to show just that case? — user551774, Aug 30 '21 at 18:19
The sequences $r_{\mu_i}, s_{\mu_i}$ can be finite, correct? It seems there is always such a sequence $s_{\mu_i}$. Since $(q,p_n#)=1$, you can take $q\equiv 2^k \mod p_{n+1}$ for some $k$. You can always do this since $2$ generates the multiplicative group of units modulo $p_{n+1}$..There may always be a sequence $r_{\mu_i}$ as well but I’m not sure. — user551774, Aug 30 '21 at 18:29
The sequences as listed are finite, I failed to note that $\forall i:p_{u_i}\mid \frac{p_n#}d$. I know for certain that there is not a generation sequence for any $d$ except when $d=p_k$ or $d=2p_k$ for some $k$, so it becomes a question whether the sequence $r_{u_i}$ always exists, but I think that question is nearly equal to the original. — abiessu, Aug 30 '21 at 18:36
@apelt001: since the products would be empty for $d=p_n#$, I'll just say that we can assume $\frac{p_n#}d\gt 1$. — abiessu, Aug 30 '21 at 18:43
If I may suggest a reformulation of the beginning of the statement as follows: If there exist non-negative integers $r_{\mu_i},\ s_{\mu_i}$ $i=1,…\omega(\frac{p_n#}{d})$ such that… — user551774, Aug 30 '21 at 18:46
This problem’s hard. I don’t think I will think about it too much. Good Luck! — user551774, Aug 30 '21 at 18:48
@apelt001: for reference, I misspoke about whether the leading integers might exist; we can guarantee their existence by induction. — abiessu, Aug 30 '21 at 19:21
@apelt001: further side-comment... $2$ is not a generator for the multiplicative group modulo $p_n$ for every $n$, note $23$... — abiessu, Aug 30 '21 at 22:38

abiessu · Accepted Answer · 2021-10-03T05:30:19.960

There is a counterexample to this conjecture, therefore as stated it is false. In particular, let $n=4,p_{n+1}=11$ with $d=5\cdot 7$ and $\frac{p_n\#}d=2\cdot 3$. Then some of the $q$ which were constructible under $n=3$ have associated values $q+ap_n\#$ which are not constructible for some $a$ under $n=4$ for this $d$. In particular, note that there are no $a,b\in\Bbb Z^+: 2^a3^b\equiv 211\mod 385$. By contrast, there are $a,b$ such that $5^a7^b\equiv 7\mod 66$ (trivially), but further investigation is required.

Combining disjoint congruences: $q\equiv \prod_ip_{u_i}^{r_{u_i}}\mod d$ and $q\equiv \prod_ip_{u_i}^{s_{u_i}}\mod p_{n+1}$

1 Answers1