+0

# More modular math..

0
154
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.

Guest Feb 19, 2017

#2
+8824
+5

correction

241 : 211 = 1 R 30

Omi67  Feb 19, 2017
Sort:

#1
+8824
+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.

Omi67  Feb 19, 2017
#2
+8824
+5

correction

241 : 211 = 1 R 30

Omi67  Feb 19, 2017
#3
+2

Omi67: Thanks for that, but the question is about ONE NUMBER, n, that satifies those 3 conditions.

Guest Feb 19, 2017
#4
0

43A + 22 =101B + 64 =211C + 30, solve for A,B,C.
A=1,065,  B=453,    C=217, so that:
43 x 1,065 + 22 =45,817 The smallest positive number.
LCM {43, 101, 211} =916,373. So, the general form is:
916,373D + 45,817. And for D=0, 1, 2......etc. We have:
45,817 The smallest positive number.
962,190
1,878,563.......etc.

Guest Feb 19, 2017
#5
+18777
+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

heureka  Feb 20, 2017
edited by heureka  Feb 20, 2017
edited by heureka  Feb 20, 2017
edited by heureka  Feb 20, 2017

### 21 Online Users

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