Find the smallest positive integer that satisfies the system of congruences
a)
n congruency sign 2 (mod ll)
n congruency sign 3 (mod 17)
b)
n congruency sign 1 (mod 7)
n congruency sign 7 (mod 13)
n congruency sign 13 (mod 20)
b)
n congruency sign 1 (mod 7) n=7p+1
n congruency sign 7 (mod 13) n=13q+7
n congruency sign 13 (mod 20) n=20r+13
13,33,53,73,93,113,133,153,173,193,...............293
which is a multiple of 7
12,32,52,72,92, 112, ....... ...................................292
which is a multiple of 13
6,26,46,66,86,106,126,146,166,186,206,226, 246,266,286,
33+13*20n = 33+260n will satisfy 13(mod20) and 7(mod 13)
33,293,553,813,1073
33+260n which of these will be 1 mod 7
32+260m must be a multiple of 7
32+260m must be a multple of 7
260m+32=7k
292, 552, 812,
812+1=813
813 = 1(mod 7)
813 = 13(mod 20)
813 = 7(mod 13)
The smallest number that meets those criterion is 813
There is probably a much better way to do it though ://
Find the smallest positive integer that satisfies the system of congruences
a)
n congruency sign 2 (mod ll) n= 11p+2
n= 2,13,24,35,46,57,68,79,90,101,112,123,134,145,156,
n congruency sign 3 (mod 17) n=17q+3
n=3,20,37,54,71,88,105,122,139,156,173,190
b)
n congruency sign 1 (mod 7) n=7p+1
n congruency sign 7 (mod 13) n=13q+7
n congruency sign 13 (mod 20) n=20r+13
13,33,53,73,93,113,133,153,173,193,...............293
which is a multiple of 7
12,32,52,72,92, 112, ....... ...................................292
which is a multiple of 13
6,26,46,66,86,106,126,146,166,186,206,226, 246,266,286,
33+13*20n = 33+260n will satisfy 13(mod20) and 7(mod 13)
33,293,553,813,1073
33+260n which of these will be 1 mod 7
32+260m must be a multiple of 7
32+260m must be a multple of 7
260m+32=7k
292, 552, 812,
812+1=813
813 = 1(mod 7)
813 = 13(mod 20)
813 = 7(mod 13)
The smallest number that meets those criterion is 813
There is probably a much better way to do it though ://
Find the smallest positive integer that satisfies the system of congruences
a)
n congruency sign 2 (mod ll)
n congruency sign 3 (mod 17)
\(\begin{array}{rcll} n &\equiv& {\color{red}2} \pmod {{\color{green}11}} \\ n &\equiv& {\color{red}3} \pmod {{\color{green}17}} \\ \text{Let } m &=& 11\cdot 17 = 187 \\\\ \end{array}\)
Because 11 and 17 are relatively prim ( gcd(11,17) = 1! ) we can go on:
\(\begin{array}{rcll} n &=& {\color{red}2} \cdot {\color{green}17} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ {\color{green}17}^{\varphi({\color{green}11})-1} \pmod {{\color{green}11}} ] }_{=\text{modulo inverse 17 mod 11} } }_{=17^{10-1} \mod {11} }}_{=17^{9} \mod {11}}}_{=2} + {\color{red}3} \cdot {\color{green}11} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ {\color{green}11}^{\varphi({\color{green}17})-1} \pmod {{\color{green}17}} ] }_{=\text{modulo inverse 11 mod 17} } }_{=11^{16-1} \mod {17} }}_{=11^{15} \mod {17}}}_{=14}\\\\ n &=& {\color{red}2} \cdot {\color{green}17} \cdot [ 2] + {\color{red}3} \cdot {\color{green}11} \cdot [14] \\ n &=& 68 + 462 \\ n &=& 530 \\\\ && n \pmod {m}\\ &=& 530 \pmod {187} \\ &=& 156 \\\\ n &=& 156 + k\cdot 187 \qquad k \in Z\\\\ \mathbf{n_{min}} & \mathbf{=}& \mathbf{156} \end{array}\)
b)
n congruency sign 1 (mod 7)
n congruency sign 7 (mod 13)
n congruency sign 13 (mod 20)
\(\begin{array}{rcll} n &\equiv& {\color{red}1} \pmod {{\color{green}7}} \\ n &\equiv& {\color{red}7} \pmod {{\color{green}13}} \\ n &\equiv& {\color{red}13} \pmod {{\color{green}20}} \\ \text{Let } m &=& 7\cdot 13\cdot 20 = 1820 \\ \end{array} \)
Because 7 and 13 and 20 are relatively prim we can go on:
\(\small{ \begin{array}{l} n = {\color{red}1} \cdot {\color{green}13\cdot 20} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}13\cdot 20) }^{\varphi({\color{green}7}) -1 } \pmod {{\color{green}7}} ] }_{=\text{modulo inverse }(13\cdot 20) mod 7 } }_{=(13\cdot 20)^{6-1} \mod {7}} }_{=(13\cdot 20)^{5} \mod {7}} }_{=(260\pmod{7})^{5} \mod {7}} }_{=(1)^{5} \mod {7}} }_{=1} + {\color{red}7} \cdot {\color{green}7\cdot 20} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}7\cdot 20) }^{\varphi({\color{green}13}) -1} \pmod {{\color{green}13}} ] }_{=\text{modulo inverse } (7\cdot 20) mod 13 } }_{=(7\cdot 20)^{12-1} \mod {13}} }_{=(7\cdot 20)^{11} \mod {13}} }_{=(140\pmod{13})^{11} \mod {13}} }_{=(10)^{11} \mod {13}} }_{=4} + {\color{red}13} \cdot {\color{green}7\cdot 13} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}7\cdot 13) }^{\varphi({\color{green}20}) -1 } \pmod {{\color{green}20}} ] }_{=\text{modulo inverse } (7\cdot 13) mod 20 } }_{=(7\cdot 13)^{8-1} \mod {20}} }_{=(7\cdot 13)^{7} \mod {20}} }_{=(91\pmod{20})^{7} \mod {20}} }_{=(11)^{7} \mod {20}} }_{=11}\\\\ n = {\color{red}1} \cdot {\color{green}13\cdot 20} \cdot [1] + {\color{red}7} \cdot {\color{green}7\cdot 20} \cdot [4] + {\color{red}13} \cdot {\color{green}7\cdot 13} \cdot [11] \\ n = 260+ 3920 + 13013 \\ n = 17193 \\\\ n \pmod {m}\\ = 17193 \pmod {1820} \\ = 813 \\\\ n = 813 + k\cdot 1820 \qquad k \in Z\\\\ \mathbf{n_{min}} \mathbf{=} \mathbf{813} \end{array} }\)
\(\begin{array}{l} \text{In number theory, }\\ \text{Euler's theorem (also known as the Fermat–Euler theorem or Euler's totient theorem)}\\ \text{states that if } \mathbf{n} \text{ and } \mathbf{a} \text{ are coprime positive integers, then }\\ \hline a^{\varphi (n)} \equiv 1 \pmod{n} \end{array}\)