+0  
 
0
193
2
avatar

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.

Guest Feb 15, 2018
 #1
avatar+20022 
+1

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}\)

 

 

laugh

heureka  Feb 15, 2018
edited by heureka  Feb 15, 2018
 #2
avatar
0

A*105 + 104 =B*111 + 110=C*121 + 111 =D*122 + 111

By simple iteration A=124,985, B = 118,229, C = 108,458, D = 107,569

N = 105 x 124,985 +104 =13,123,529 - the smallest positive integer.

Since the LCM of {105, 111, 121, 122} =57,350,370, therefore:

N = 57,350,370 n + 13,123,529, where n =0, 1, 2, 3...........etc.

Guest Feb 15, 2018

27 Online Users

avatar
avatar
avatar

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.