What is the smallest positive integer that will satisfy the following congruences:
N mod 105 = 104,
N mod 111 = 110,
N mod 121 = 111,
N mod 122 = 111
Thanks for any help.
\(\begin{array}{|l|cll|} \hline \begin{array}{|rcll|} \hline \mathbf{ n } & \mathbf{\equiv} & \mathbf{104 \pmod{105}} \\ \mathbf{ n } & \mathbf{\equiv} & \mathbf{110 \pmod{111}} \\ \hline \end{array} \\ \begin{array}{lrcll} \Rightarrow & n -104 &=& 105x \\ & n -110 &=& 111y \\\\ \Rightarrow & n &=& 104+105x \\ & n &=& 110+111y \\\\ & n=104+105x&=& 110+111y \\ & 104+105x&=& 110+111y \\ & 105x-111y&=& 6 \quad & | \quad : 3 \\ & \mathbf{35x-37y}& \mathbf{=}& \mathbf{2} \qquad x,y \in Z \\ &\rightarrow \quad x &=& -1+37b^{^1)} \qquad b \in Z \\\\ & n &=& 104+105x \\ & n &=& 104+105(-1+37b) \\ & n &=& 104-105+105\cdot 37b \\ & n &=& -1+ 3885b \\ & \mathbf{n} &\mathbf{\equiv}& -1 \mathbf{\pmod{3885}} \qquad (1)\\ \end{array}\\ \hline \end{array}\)
\(\begin{array}{|l|cll|} \hline \begin{array}{|rcll|} \hline \mathbf{ n } & \mathbf{\equiv} & \mathbf{111 \pmod{121}} \\ \mathbf{ n } & \mathbf{\equiv} & \mathbf{111 \pmod{122}} \\ \hline \end{array} \\ \begin{array}{lrcll} \Rightarrow & n -111 &=& 121x \\ & n -111 &=& 122y \\\\ \Rightarrow & n &=& 111+121x \\ & n &=& 111+122y \\\\ & n=111x+121y&=& 111+122y \\ & 111x+121y&=& 111+122y \\\\ & \mathbf{121x-122y}&\mathbf{=}& \mathbf{0} \qquad x,y \in Z \\ &\rightarrow \quad x &=& 122a^{^2)} \qquad a \in Z \\\\ & n &=& 111+121x \\ & n &=& 111+121(122a) \\ & n &=& 111+121\cdot 122a \\ & n &=& 111+14762a \\ & \mathbf{n} &\mathbf{\equiv}& 111 \mathbf{\pmod{14762}} \qquad (2)\\ \end{array} \\ \hline \end{array} \)
After reducing, we have two formulas:
\( \begin{array}{|rcll|} \hline \mathbf{n} &\mathbf{\equiv}& -1 \mathbf{\pmod{3885}} \qquad &(1)\\ \mathbf{n} &\mathbf{\equiv}& 111 \mathbf{\pmod{14762}} \qquad &(2)\\ \hline \end{array} \)
\( \begin{array}{|rcll|} \hline \mathbf{n} &\mathbf{\equiv}& -1 \mathbf{\pmod{3885}} \\ \mathbf{n} &\mathbf{\equiv}& 111 \mathbf{\pmod{14762}} \\ \hline \end{array} \\ \begin{array}{lrcll} \Rightarrow & n +1 &=& 3885x \\ & n -111 &=& 14762y \\\\ \Rightarrow & n &=& -1+3885x \\ & n &=& 111+14762y \\\\ & n=-1+3885x&=& 111+14762y \\ & -1+3885x&=& 111+14762y \\ & \mathbf{3885x-14762y}& \mathbf{=}& \mathbf{112} \qquad x,y \in Z \\ &\rightarrow \quad x &=&3378+14762g^{^3)} \qquad g \in Z \\\\ & n &=& -1+3885x \\ & n &=& -1+3885\cdot (3378+14762g) \\ & n &=& -1+3885\cdot 3378+ 3885\cdot 14762g \\ & \mathbf{n} &\mathbf{=}& \mathbf{13123529 + 57350370g \qquad g \in Z } \\ \end{array}\)
The smallest positive integer is \(\mathbf{13\ 123\ 529}\)
Proof:
\(\begin{array}{|rcll|} \hline \mathbf{13\ 123\ 529} &\text{mod } 105 =& 104\\ \mathbf{13\ 123\ 529} &\text{mod } 111 =& 110\\ \mathbf{13\ 123\ 529} &\text{mod } 121 =& 111 \\ \mathbf{13\ 123\ 529} &\text{mod } 122 =& 111 \\ \hline \end{array} \)
\(\begin{array}{lcll} \hline ^1) \\ \text{Solve of the diophantine equation $35x - 37y = 2$ } \\ \text{The variable with the smallest coefficient is $x$. The equation is transformed after $x$: }\\ \begin{array}{rcll} 35x &=& 2 + 37y \\ \mathbf{x} &\mathbf{=}& \mathbf{\dfrac{ 2 + 37y } {35}} \\ &=& \dfrac{ 2 +35y+2y } {35} \\ &=& \dfrac{ 35y + 2 +2y } {35} \\ &=& \dfrac{35y}{35} + \dfrac{ 2 +2y } {35} \\ x &=& y + \dfrac{ 2 +2y} {35} \\ \end{array}\\ \begin{array}{lrcll} \text{we set:} &a &=& \dfrac{ 2 + 2y } {35} \\ & 35a &=& 2 + 2y \\ \end{array} \\ \text{The variable with the smallest coefficient is $y$. The equation is transformed after $y$: }\\ \begin{array}{rcll} 2y &=& -2 + 35a \\ \mathbf{y} &\mathbf{=}& \mathbf{\dfrac{ -2 + 35a } {2}} \\ &=& \dfrac{ -2 + 34a+a } {2} \\ &=& \dfrac{ 34a - 2 +a } {2} \\ &=& -\dfrac{-2}{2} +\dfrac{34a}{2} + \dfrac{ a } {2} \\ y &=& -1+17a+ \dfrac{ a } {2} \\ \end{array}\\ \begin{array}{lrcll} \text{we set:} &b &=& \dfrac{a} {2} \\ & 2b &=& a \\ \end{array} \\ \text{The variable with the smallest coefficient is $a$. The equation is transformed after $a$: }\\ \begin{array}{lrcll} \text{no fraction there:} & \mathbf{a} &\mathbf{=}& \mathbf{ 2b } \\ \end{array} \end{array} \)
\(\text{Elemination of the unknowns:}\\ \begin{array}{rcll} \mathbf{y} &\mathbf{=}& \mathbf{\dfrac{ -2 + 35a } {2}} \quad & | \quad \mathbf{a = 2b }\\ & = & \dfrac{-2 + 35\cdot (2b) } {2} \\ \mathbf{y} & \mathbf{=} & \mathbf{-1+35b} \\\\ \mathbf{x} &\mathbf{=}& \mathbf{\dfrac{ 2 + 37y } {35}} \quad & | \quad \mathbf{y = -1+35b }\\ & = & \dfrac{ 2 + 37\cdot (-1+35b ) } {11} \\ \mathbf{x} & \mathbf{=} & \mathbf{-1 + 37b } \\ \end{array} \)
\(\begin{array}{lcll} \hline ^2) \\ \text{Solve of the diophantine equation $121x - 122y = 0 $ } \\ \text{The variable with the smallest coefficient is $x$. The equation is transformed after $x$: }\\ \begin{array}{rcll} 121x &=& 122y \\ \mathbf{x} &\mathbf{=}& \mathbf{\dfrac{ 122y } {121}} \\ &=& \dfrac{ 121y+y } {121} \\ &=& \dfrac{121y}{121} + \dfrac{y} {121} \\ x &=& y + \dfrac{ y} {121} \\ \end{array}\\ \begin{array}{lrcll} \text{we set:} &a &=& \dfrac{y} {121} \\ & 121a &=& y \\ \end{array} \\ \text{The variable with the smallest coefficient is $y$. The equation is transformed after $y$: }\\ \begin{array}{lrcll} \text{no fraction there:} & \mathbf{y} &\mathbf{=}& \mathbf{ 121a } \\ \end{array} \end{array} \)
\(\text{Elemination of the unknowns:}\\ \begin{array}{rcll} \mathbf{x} &\mathbf{=}& \mathbf{\dfrac{ 122y } {121}} \quad & | \quad \mathbf{y=121a }\\ & = & \dfrac{122\cdot (121a) } {121} \\ \mathbf{x} & \mathbf{=} & \mathbf{122a} \\ \end{array}\)
\( \begin{array}{lcll} \hline ^3) \\ \text{Solve of the diophantine equation $3885x - 14762y = 112 $ } \\ \text{The variable with the smallest coefficient is $x$. The equation is transformed after $x$: }\\ \begin{array}{rcll} 3885x &=& 112 + 14762y \\ \mathbf{x} &\mathbf{=}& \mathbf{\dfrac{ 112 + 14762y} {3885}} \\ &=& \dfrac{ 112 + 11655y + 3107y } {3885} \\ &=& \dfrac{11655y + 112 + 3107y }{3885} \\ &=& \dfrac{11655y }{3885} + \dfrac{112 + 3107y} {3885} \\ x &=& 3y + \dfrac{ 112 + 3107y } {3885} \\ \end{array}\\ \begin{array}{lrcll} \text{we set:} &a &=& \dfrac{112 + 3107y } {3885} \\ & 3885a &=& 112 + 3107y \\ \end{array} \\ \text{The variable with the smallest coefficient is $y$. The equation is transformed after $y$: }\\ \begin{array}{rcll} 3107y &=& -112 + 3885a \\ \mathbf{y} &\mathbf{=}& \mathbf{\dfrac{ -112 + 3885a} {3107}} \\ &=& \dfrac{ -112 + 3107a + 778a } {3107} \\ &=& \dfrac{3107a - 112 + 778a }{3107} \\ &=& \dfrac{3107a }{3107} + \dfrac{- 112 + 778a} {3107} \\ y &=& 3a + \dfrac{ 112 + 3107a } {3107} \\ \end{array}\\ \begin{array}{lrcll} \text{we set:} &b &=& \dfrac{-112 + 778a } {3107} \\ & 3107b &=& -112 + 778a \\ \end{array} \\ \text{The variable with the smallest coefficient is $a$. The equation is transformed after $a$: }\\ \begin{array}{rcll} 778a &=& 112 + 3107b \\ \mathbf{a} &\mathbf{=}& \mathbf{\dfrac{ 112 + 3107b} {778}} \\ &=& \dfrac{ 112 + 2334b + 773b } {778} \\ &=& \dfrac{2334b +112 + 773b }{778} \\ &=& \dfrac{2334b }{3107} + \dfrac{112 + 773b} {778} \\ a &=& 3b + \dfrac{ 112 + 773b} {778} \\ \end{array}\\ \begin{array}{lrcll} \text{we set:} &c &=& \dfrac{112 + 773b } {778} \\ & 778c &=& 112 + 773b \\ \end{array} \\ \text{The variable with the smallest coefficient is $b$. The equation is transformed after $b$: }\\ \begin{array}{rcll} 773b &=& -112 + 778c\\ \mathbf{b} &\mathbf{=}& \mathbf{\dfrac{ -112 + 778c} {773}} \\ &=& \dfrac{ -112 + 773c + 5c } {773} \\ &=& \dfrac{773c -112 + 5c }{773} \\ &=& \dfrac{773c }{773} + \dfrac{-112 + 5c } {773} \\ b &=& c + \dfrac{ -112 + 5c} {773} \\ \end{array}\\ \begin{array}{lrcll} \text{we set:} &d &=& \dfrac{-112 + 5c } {773} \\ & 773d &=& -112 + 5c \\ \end{array} \\ \text{The variable with the smallest coefficient is $c$. The equation is transformed after $c$: }\\ \begin{array}{rcll} 5c &=& 112 + 773d\\ \mathbf{c} &\mathbf{=}& \mathbf{\dfrac{ 112 + 773d } {5}} \\ &=& \dfrac{ 110+2 + 770d + 3d } {5} \\ &=& \dfrac{110+770d+2 + 5d }{5} \\ &=& \dfrac{110 }{5}+\dfrac{770d }{5} + \dfrac{2 + 3d } {5} \\ c &=& 22 + 154d + \dfrac{2 + 3d } {5} \\ \end{array}\\ \begin{array}{lrcll} \text{we set:} &e &=& \dfrac{ 2 + 3d } {5} \\ & 5e &=& 2 + 3d \\ \end{array} \\ \text{The variable with the smallest coefficient is $d$. The equation is transformed after $d$: }\\ \begin{array}{rcll} 3d &=& -2 + 5e\\ \mathbf{d} &\mathbf{=}& \mathbf{\dfrac{ -2 + 5e } {3}} \\ &=& \dfrac{ -2 + 3e + 2e } {3} \\ &=& \dfrac{3e -2 + 2e}{3} \\ &=& \dfrac{3e }{3} + \dfrac{-2 + 2e} {3} \\ d &=& e + \dfrac{-2 + 2e } {3} \\ \end{array}\\ \begin{array}{lrcll} \text{we set:} &f &=& \dfrac{ -2 + 2e } {3} \\ & 3f &=& -2 + 2e \\ \end{array} \\ \text{The variable with the smallest coefficient is $e$. The equation is transformed after $e$: }\\ \begin{array}{rcll} 2e &=& 2 + 3f\\ \mathbf{e} &\mathbf{=}& \mathbf{\dfrac{2 + 3f } {2}} \\ &=& \dfrac{ 2+2f+f } {2} \\ &=& \dfrac{2 }{2} + \dfrac{2f }{2} + \dfrac{f} {2} \\ e &=& 1 + f + \dfrac{f} {2} \\ \end{array}\\ \begin{array}{lrcll} \text{we set:} &g &=& \dfrac{ f} {2} \\ & 2g &=& f \\ \end{array} \\ \text{The variable with the smallest coefficient is $f$. The equation is transformed after $f$: }\\ \begin{array}{lrcll} \text{no fraction there:} & \mathbf{f} &\mathbf{=}& \mathbf{ 2g } \\ \end{array} \end{array}\)
\(\text{Elemination of the unknowns:}\\ \begin{array}{rcll} \mathbf{e} &\mathbf{=}& \mathbf{\dfrac{ 2 + 3f } {2}} \quad & | \quad \mathbf{f=2g }\\ & = & \dfrac{2 + 3\cdot 2g } {2} \\ \mathbf{e} & \mathbf{=} & \mathbf{1 + 3g } \\\\ \mathbf{d} &\mathbf{=}& \mathbf{\dfrac{ -2 + 5e } {3}} \quad & | \quad \mathbf{e=1 + 3g }\\ & = & \dfrac{-2 + 5\cdot (1 + 3g) } {2} \\ \mathbf{d} & \mathbf{=} & \mathbf{1 + 5g } \\\\ \mathbf{c} &\mathbf{=}& \mathbf{\dfrac{ 112 + 773d } {5}} \quad & | \quad \mathbf{d=1 + 5g }\\ & = & \dfrac{112 + 773\cdot (1 + 5g) } {2} \\ \mathbf{c} & \mathbf{=} & \mathbf{177 + 773g } \\\\ \mathbf{b} &\mathbf{=}& \mathbf{\dfrac{ -112 + 778c } {773}} \quad & | \quad \mathbf{c=177 + 773g }\\ & = & \dfrac{-112 + 778\cdot (177 + 773g) } {773} \\ \mathbf{b} & \mathbf{=} & \mathbf{ 178 + 778g } \\\\ \mathbf{a} &\mathbf{=}& \mathbf{\dfrac{ 112 + 3107b } {778}} \quad & | \quad \mathbf{b=178 + 778g }\\ & = & \dfrac{112 + 3107\cdot (178 + 778g) } {778} \\ \mathbf{a} & \mathbf{=} & \mathbf{ 711 + 3107g } \\\\ \mathbf{y} &\mathbf{=}& \mathbf{\dfrac{ -112 + 3885a } {3107}} \quad & | \quad \mathbf{a=711 + 3107g }\\ & = & \dfrac{-112 + 3885\cdot (711 + 3107g) } {3107} \\ \mathbf{y} & \mathbf{=} & \mathbf{ 889 + 3885g } \\\\ \mathbf{x} &\mathbf{=}& \mathbf{\dfrac{ 112 + 14762y } {3885}} \quad & | \quad \mathbf{y=889 + 3885g }\\ & = & \dfrac{112 + 14762\cdot (889 + 3885g) } {3885} \\ \mathbf{x} & \mathbf{=} & \mathbf{ 3378 + 14762g } \\ \end{array}\)
