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