What is the smallest solution to $x = 2 \operatorname{mod} (6y+1)$, $x = 3 \operatorname{mod} (12y+1)$, $x= 3 \operatorname{mod} (18y+1)$?

Question

I'd like to solve a system of modular equations, but it's a somewhat unusual system. Specifically, what is the smallest natural number $x$ for which $x = 2\pmod{6y+1}$, and $x=3\pmod{12y+1}$, and $1 \pmod{18y+1}$ for some natural number $y$?

If $y=1$, then WolframAlpha tells me that $x=1654$. But is it possible that a bigger choice of $y$ could yield a smaller value of $x$? This came up in the context of Godel coding, by the way.

Answer 1

\begin{align} x &\equiv 2\pmod{ 6y+1} \\ x &\equiv 3\pmod{12y+1} \\ x &\equiv 1\pmod{18y+1} \end{align}

Note \begin{align} 2( 6y+1) - 1(12y+1) &= 1 \\ 3(12y+1) - 2(18y+1) &= 1 \\ -2(18y+1) + 3( 6y+1) &= 1 \\ \end{align}

So the numbers $6y+1, 12y+1$, and $18y+1$ are pairwise prime.

\begin{align} (12y+1)(18y+1) &\equiv 216y^2+30y+1 \pmod{6y+1} \\ &\equiv (216y^2+30y+1)\pmod{6y+1} \\ &\equiv (36y-1)(6y+1) + 2 \pmod{6y+1} \\ &\equiv 2 \pmod{6y+1} \\ &\equiv 0 \pmod{12y+1} \\ &\equiv 0 \pmod{18y+1} \end{align}

\begin{align} -12(6y+1)(18y+1) &\equiv (-1296y^2-288y-12) \pmod{12y+1} \\ &\equiv (-108y - 15)(12y + 1) + 3 \pmod{12y+1} \\ &\equiv 0 \pmod{6y+1} \\ &\equiv 3 \pmod{12y+1} \\ &\equiv 0 \pmod{18y+1} \end{align}

\begin{align} (9y+5)(6y+1)(12y+1) &\equiv 648y^3 + 522y^2 + 99y + 5 \\ &\equiv (36y^2 + 27y + 4)(18y + 1) + 1 \pmod{18y+1} \\ &\equiv 0 \pmod{6y+1} \\ &\equiv 0 \pmod{12y+1} \\ &\equiv 1 \pmod{18y+1} \end{align}

\begin{array}{c} (12y+1)(18y+1)-12(6y+1)(18y+1)+(9y+5)(6y+1)(12y+1) \\ = 648y^3-558y^2-159y-6 \end{array}

So, a solution is $$648y^3-558y^2-159y-6 \pmod{(6y+1)(12y+1)(18y+1)}$$

Answer 2

The bases, call them $p,q$ and $r$, are coprime, so try to solve $$aqr=2\pmod p\\ bpr=3\pmod q\\ cpq=1\pmod r$$ The answer is $aqr+bpr+cpq\pmod{pqr}$

Answer 3

I don't have reputation to comment, so trying to answer here.

To make all 3 modulo co-prime to each other. we take smallest y>0. naturally if we take y=1 then we have modulo as {7,13,19} and they are prime numbers. so, choice of y seems good.

• Now the smallest number should be within ${7*13*19=1729}$, so 1654 is the smallest answer you get.
• I don't know what could be the technique which gives higher value of y and smaller value of x.