heureka

avatar
Benutzernameheureka
Punkte26387
Membership
Stats
Fragen 17
Antworten 5678

 #5
avatar+26387 
+5

What is the smallest positive n under 50,000 that satisfies the following:

n mod 43 = 22 

n mod 101 = 64 

n mod 211 = 30 . Thanks for help.

 

\(\begin{array}{rcll} n &\equiv& {\color{red}22} \pmod {{\color{green}43}} \\ n &\equiv& {\color{red}64} \pmod {{\color{green}101}} \\ n &\equiv& {\color{red}30} \pmod {{\color{green}211}} \\ \text{Let } m &=& 43\cdot 101\cdot 211 = 916373 \\ \end{array}\)

 

43 is a prime number, and 101 is a prime number, and 211 is a prime number.

Because 43 and 101 and 211 are relatively prim ( gcd(43,101,211) = 1! ) we can go on:

 

\(\small{ \begin{array}{lcl} n = \\ {\color{red}22} \cdot {\color{green}101\cdot 211} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}101\cdot 211) }^{\varphi({\color{green}43}) -1 } \mod {{\color{green}43}} ] }_{=\text{modulo inverse }(101\cdot 211) \pmod {43} } }_{=(101\cdot 211)^{42-1} \pmod {43}} }_{=(101\cdot 211)^{41} \pmod {43}} }_{=(21311\pmod{43})^{41} \pmod {43}} }_{=(26)^{41} \pmod {43}} }_{=5}\\ + {\color{red}64} \cdot {\color{green}43\cdot 211} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}43\cdot 211) }^{\varphi({\color{green}101}) -1} \mod {{\color{green}101}} ] }_{=\text{modulo inverse } (43\cdot 211) \pmod {101} } }_{=(43\cdot 211)^{100-1} \pmod {101}} }_{=(43\cdot 211)^{99} \pmod {101}} }_{=(9073\pmod{101})^{99} \pmod {101}} }_{=(84)^{99} \pmod {101}} }_{=95}\\ + {\color{red}30} \cdot {\color{green}43\cdot 101} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}43\cdot 101) }^{\varphi({\color{green}211}) -1 } \mod {{\color{green}211}} ] }_{=\text{modulo inverse } (43\cdot 101) \pmod {211} } }_{=(43\cdot 101)^{210-1} \mod {211}} }_{=(43\cdot 101)^{209} \mod {211}} }_{=(4343\pmod{211})^{209} \mod {211}} }_{=(123)^{209} \mod {211}} }_{=199} \\ + {\color{green}43}\cdot {\color{green}101}\cdot {\color{green}211} \cdot k \quad | \quad k\in Z \\ n = {\color{red}22} \cdot {\color{green}101\cdot 211} \cdot [5] + {\color{red}64} \cdot {\color{green}43\cdot 211} \cdot [95] + {\color{red}30} \cdot {\color{green}43\cdot 101} \cdot [199] + {\color{green}43}\cdot {\color{green}101}\cdot {\color{green}211} \cdot k \\ n = 2344210+ 55163840 + 25927710 + {\color{green}43}\cdot {\color{green}101}\cdot {\color{green}211} \cdot k \\ n = 83435760 + {\color{green}916373}\cdot k \quad | \quad k\in Z \\\\ n_{min} = 83435760 \pmod {916373 } \\ n_{min} = 45817 \\\\ \mathbf{n} \mathbf{=} \mathbf{45817 + 916373 \cdot k \quad | \quad k\in Z} \end{array} }\)

 

The smallest positive n under 50,000 is 45817

 

laugh

20.02.2017
 #1