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.
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.
+129933 These are all trivial answers......!!!!
n mod 1,103 = 1,041 n = 1041
n mod 1,303 = 859 n = 859
n mod 2,003 = 1,095 n = 1095
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.
+129933 Ah....thanks, Guest....I misunderstood the problem....no wonder it seemed so easy.....LOL!!!!!
+2511 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. } \\ \)
