+0  
 
0
101
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
Sort: 

2+0 Answers

 #1
avatar+19207 
+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

10 Online Users

avatar
avatar
We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details