Showing existence in congruence $q\equiv d^k+\frac{mp_n\#}d\pmod{p_n\#}$

116 Views Asked by At

The basic (updated) problem is

Given $n\in\Bbb N,q:(q,p_n\#)=1$, show that there exist $d\mid p_n\#,k\ge 1,m\in [1,p_n-1]$ such that $q\equiv d^k+\frac{mp_n\#}d\pmod{p_n\#}$.

(Note that $d$ is allowed to be negative. Here $p_n\#$ refers to the primorial of the $n$th prime.)

So far I've got proof for $n=3, p_n\#=30$, and I'm using that as the base case for an inductive approach. So taking $n\ge 3, q_1:(q_1,p_{n+1}\#)=1$, we have that $\exists d_0\mid p_n\#,k_0\ge 1,m\in[1,p_n-1]$ such that $q_1\equiv d_0^{k_0}+\frac{mp_n\#}{d_0}\pmod {p_n\#}$. Since $(p_{n+1},p_n\#)=1$, there exists $u:p_{n+1}^u\equiv 1\pmod{\frac{p_n\#}{d_0}}$, so we also have $q_1\equiv d_0^{k_0}p_{n+1}^u+\frac{mp_n\#}{d_0}\pmod {p_n\#}$, and I can get really close with $\exists m_1:q_1\equiv d_0^{k_0}p_{n+1}^u+\frac{(d_0m_1+m)p_{n+1}\#}{d_0p_{n+1}}\pmod {p_{n+1}\#}$, but I'm not certain how to show that $\exists f: (d_0p_{n+1})^f\equiv d_0^{k_0}p_{n+1}^u\pmod {p_{n+1}\#}$.

Additionally, I can see that $d_0p_{n+1}q_1\equiv d_0^{k_0+1}p_{n+1}^{u+1}\pmod{p_{n+1}\#}$. This implied form would be excellent if I could prove that it in turn implies the desired form above.

Is there a better approach for this question, or perhaps an additional step I'm not seeing? This is not homework; yes, this does mean that it is possible for the problem statement to be false in general, although the (limited) heuristics I have so far indicate it should hold (up through $n=12$ so far).

1

There are 1 best solutions below

0
On BEST ANSWER

The conjecture as stated joins the previous versions in being false. The question in one edit incorrectly states that the conjecture was proven up through $n=20$, while a programming error caused a missed value for $n=13,q=23$. The most that it is possible to say is that

$$\tag{1}\forall q:(q,p_n\#)=1, \exists d\mid p_n\#,\exists m:(m,d)=1,\exists k_i\in\Bbb N:\\q\equiv\prod_{r'\mid d}r'^{k_{r'}}+\frac{mp_n\#}d\pmod{p_n\#}$$

(Note that $r'$ is read as "$r$ is prime".) This version is effectively proven in the question, but for the sake of clarity here is the full proof: taking that the statement $(1)$ holds by the direct claim in the question for $n=3$, assume that it also holds for some arbitrary $n=s$ and let arbitrary $q:(q,p_{s+1}\#)=1$ be given. Then we have $(q,p_s\#)=1$ also, allowing $\exists d\mid p_s\#,\exists m:(m,d)=1,\exists k_i\in\Bbb N:q\equiv\prod_{r'\mid d}r'^{k_{r'}}+\frac{mp_s\#}d\pmod{p_s\#}$. Since we further have $(p_{s+1},p_s\#)=1$, there is a $u\in\Bbb N:p_{s+1}^u\equiv 1\pmod{p_s\#}$. Then we also have $q\equiv p_{s+1}^u\prod_{r'\mid d}r'^{k_{r'}}+\frac{mp_{s+1}\#}{dp_{s+1}}\pmod{p_s\#}$, which can be finally combined with a multiple of $p_s\#$ as $\exists m_1\in[1,p_{s+1}-1]:q\equiv \prod_{r'\mid dp_{s+1}}r'^{k_{r'}}+\frac{(m_1d+m)p_{s+1}\#}{dp_{s+1}}\pmod{p_{s+1}\#}$. This is the required form, and $q$ was arbitrary within the correct range, proving the statement $(1)$.