Questions   
Sort: 
 #11
avatar+2489 
+4

Solution: 

This method uses Euler's totient and the modulo inverse functions.

 

\(\begin{array}{rcll} n &\equiv& {\color{red}1} \pmod {{\color{green}4}} \\ n &\equiv& {\color{red}1} \pmod {{\color{green}3}} \\ n &\equiv& {\color{red}2} \pmod {{\color{green}5}} \\ \text{Set } m &=& 4\cdot 3\cdot 5 = 60 \\ \end{array} \)

 

\(\small{ \begin{array}{l} n = {\color{red}1} \cdot {\color{green}3\cdot 5} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}3 \cdot 5) }^{\varphi({\color{green}4}) -1 } \pmod {{\color{green}4}} ] }_{=\text{modulo inverse }(3\cdot 5) \mod 4 } }_{=(3\cdot 5)^{2-1} \mod {4}} }_{=(3\cdot 5)^{1} \mod {4}} }_{=(15\pmod{4})^{1} \mod {4}} }_{=(15)^{1} \mod {4}} }_{= 3} + {\color{red}1} \cdot {\color{green}4\cdot 5} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}4\cdot 5) }^{\varphi({\color{green}3}) -1} \pmod {{\color{green}3}} ] }_{=\text{modulo inverse } (4\cdot 5) \mod {3}} }_{=(4\cdot 5)^{2-1} \mod {3}} }_{=(4\cdot 5)^{1} \mod {3}} }_{=(20\pmod{3})^{1} \mod {3}} }_{=(2)^{1} \mod {3}} }_{=2} + {\color{red}2} \cdot {\color{green}4\cdot 3} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}4\cdot 3) }^{\varphi({\color{green} 5}) -1 } \pmod {{\color{green}5}} ] }_{=\text{modulo inverse } (4\cdot 3) \mod 5 } }_{=(4\cdot 3)^{4-1} \mod { 5}} }_{=(4\cdot 3)^{3} \mod {5}} }_{=(12\pmod{5})^{3} \mod {5}} }_{=(2)^{3} \mod {5}} }_{=3}\\ \\ n = {\color{red}1} \cdot {\color{green}3\cdot 5} \cdot [3] + {\color{red}1} \cdot {\color{green}4\cdot 5} \cdot [2] + {\color{red}2} \cdot {\color{green}4\cdot 3} \cdot [3] \\ n = 45+ 40 + 72 \\ n = 157 \\\\ n \pmod {m} = 157 \pmod {60} \\ n = 37+ k\cdot 60 \; \; k \in Z\\ \mathbf{n_{min}} \; \mathbf{=} \; \mathbf{37} \end{array} }\)

 

 

 

 

GA

.
Nov 5, 2019
 #10
avatar+700 
+1
Nov 5, 2019

0 Online Users