+0

Modular Math.....

0
113
4

Find the smallest positive number that will satisfy the following modular equations:
n mod 1,103 = 1,041, n mod 1,303 = 859, n mod 2,003 = 1,095.
Thanks for any help.

Guest Mar 12, 2017

#2
+5

Very nice going CPhill!!!. But, with little help from a simple computer code, we can do a bit better!.

A*1,103 + 1,041 =B*1,303 + 859 = C*2,003 + 1,095, solve for A, B, C.

A = 40, B = 34, C = 22. Therefore, the smallest positive number will be: 40 x 1,103 + 1,041 =45,161.
The general formula will then be:

LCM{1,103, 1,303, 2003} = 2,878,729,627

2,878,729,627D + 45,161 = n. For D =0, 1, 2.....etc. we have:

45,161, 2,878,774,788, 5,757,504,415.....etc.

Guest Mar 12, 2017
Sort:

#1
+76929
0

n mod 1,103 = 1,041     n = 1041

n mod 1,303 = 859        n = 859

n mod 2,003 = 1,095     n = 1095

CPhill  Mar 12, 2017
#2
+5

Very nice going CPhill!!!. But, with little help from a simple computer code, we can do a bit better!.

A*1,103 + 1,041 =B*1,303 + 859 = C*2,003 + 1,095, solve for A, B, C.

A = 40, B = 34, C = 22. Therefore, the smallest positive number will be: 40 x 1,103 + 1,041 =45,161.
The general formula will then be:

LCM{1,103, 1,303, 2003} = 2,878,729,627

2,878,729,627D + 45,161 = n. For D =0, 1, 2.....etc. we have:

45,161, 2,878,774,788, 5,757,504,415.....etc.

Guest Mar 12, 2017
#3
+76929
0

Ah....thanks, Guest....I misunderstood the problem....no wonder it seemed so easy.....LOL!!!!!

CPhill  Mar 12, 2017
#4
+725
+5

Solution for (n) (smallest positive integer that satisfies the system of congruencies).

n mod 1103 = 1041

n mod 1303 = 859

n mod 2003 = 1095

$$\begin{array}{rcll} n &\equiv& {\color{red}1041} \pmod {{\color{green}1103}} \\ n &\equiv& {\color{red}859} \pmod {{\color{green}1303}} \\n &\equiv& {\color{red}1095} \pmod {{\color{green}2003}} \\ \text{Let } m &=&1103 \cdot 1303\cdot 2003 = 2878729627 \\ \end{array}$$

$$\text {1103, 1303, and 2003 are coprime numbers (they are actually prime).}\\$$

$$\small{ \begin{array}{l} n = {\color{red}1041} \cdot {\color{green}1303\cdot 2003} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}1303\cdot 2003)}^{\varphi({\color{green}1103}) -1 } \pmod {{\color{green}1103}} ] }_{=\text{modulo inverse }(1303\cdot 2003) mod 1103 }}_{=(1303\cdot 2003)^{1103-1} \mod {1103}} }_{=(1303\cdot 2003)^{1102} \mod {1103}} }_{=(2609909\pmod{1103})^{1102} \mod {1103}} }_{=(211)^{1102} \mod {1103}} }_{=988} + {\color{red}859} \cdot {\color{green}1103\cdot 2003} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}1103\cdot 2003) }^{\varphi({\color{green}1303}) -1} \pmod {{\color{green}1303}} ] }_{=\text{modulo inverse } (1103\cdot 2003) mod 1303 } }_{=(1103\cdot 2003)^{1302-1} \mod {1303}} }_{=(1103\cdot 2003)^{1301} \mod {1303}} }_{=(2209309\pmod{1303})^{1301} \mod {1303}} }_{=(724)^{1301} \mod {1303}} }_{=9} +{\color{red}{1095}} \cdot {\color{green}1103\cdot 1303} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}1103\cdot 1303) }^{\varphi({\color{green}2003}) -1 } \pmod {{\color{green}2003}} ] }_{=\text{modulo inverse } (1103\cdot 1303) mod 2003 } }_{=(1103\cdot 1303)^{2002-1} \mod {2003}} }_{=(1103\cdot 1303)^{2001} \mod {2003}} }_{=(1437209\pmod{2003})^{2001} \mod {2003}} }_{=(1058)^{2001} \mod {2003}} }_{=195}\\\\ n = {\color{red}{1041}} \cdot {\color{green}{1303}\cdot 2003} \cdot [988] + {\color{red}859} \cdot {\color{green}1103\cdot 2003} \cdot [9] + {\color{red}1095} \cdot {\color{green}1103\cdot 1303} \cdot [195] \\ n = 2684312285772 + 17080167879 + 306880051725 \\ n = 3008272505376 \\\\ n \pmod {m}\\ = 3008272505376 \pmod {2878729627} \\ = 45161 \\\\ n = 45161 + k\cdot 2878729627 \qquad k \in Z\\\\ \mathbf{n_{min}} \mathbf{=} \mathbf{45161} \end{array}}$$

--------------------------------------------

$$\small \text {Related formulas and principles compliments of Leonhard Euler }\scriptsize \text {(totient function),} \\ \small \text {Euclid of Alexandria }\scriptsize \text {(Extended Euclidean algorithm), and Brilliant Chinese mathematicians “Chinese Remainder Theorem” } \\ \small \text {LaTex layout and coding adapted from Heureak’s mathematical solution and Latex presentation:}\\ \tiny \text {http://web2.0calc.com/questions/find-the-smallest-positive-integer-that-satisfies-the-system-of-congruences }\\ \small \text {Produced by Lancelot Link & Co.}\\ \small \text {Directed by GingerAle}\\ \small \text {Sponsored by Nause Corp pharmaceuticals: Makers of } \\ \scriptsize \text { Quantum Vaccines for spooky dumbness at a distance and related contagious dumbness diseases (rCDDs).}\\ \scriptsize \text{ and}\\ \scriptsize \text{ Master Blarney Filters. Now filters most toxins emitted by blarney bankers and related dumb-dumbs. } \\$$

GingerAle  Mar 13, 2017

11 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