Find the smallest positive N that will satisfy the following two modular equations. N mod 3331=231, N mod 1361=1247. Thank you for help.
A*3331 + 231=B*1361 + 1247
By simple iteration, A =100 and B =244, so the smallest positive N will be:
100 x 3,331 + 231 =333,331.
Since the LCM of 3,331 and 1,361 =4,533,491. Therefore:
N =4,533,491D + 333,331, where D =0, 1, 2, 3.......etc.
+2236 After clicking on this link I heard a gobbling and clucking noise; I thought Mr. BB gave the forum a turkey for Thanksgiving. However on closer inspection, it’s easy to tell it’s just a chicken with a thyroid condition, stuffed with Blarney Dressing. Yum!
\(\begin{array}{rcll} n &\equiv& {\color{red}3331} \pmod {{\color{green}231}} \\ n &\equiv& {\color{red}1361} \pmod {{\color{green}1247}} \\ \text{Set } m &=& 231\cdot 1247 = 288057\\ \\ \end{array}\)
\(\begin{array}{rcll} n &=& {\color{red}3331} \cdot {\color{green}1247} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ {\color{green}1247}^{\varphi({\color{green}231})-1} \pmod {{\color{green}231}} ] }_{=\text{modulo inverse 1247 mod 231} } }_{=1247^{230-1} \mod {231} }}_{=1247^{229} \mod {231}}}_{=113} + {\color{red}1361} \cdot {\color{green}231} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ {\color{green}231}^{\varphi({\color{green}1247})-1} \pmod {{\color{green}1247}} ] }_{=\text{modulo inverse 231 mod 1247} } }_{=231^{1246-1} \mod {1247} }}_{=231^{1245} \mod {1247}}}_{=637}\\\\ n &=& {\color{red}3331} \cdot {\color{green}1247} \cdot [ 113] + {\color{red}1361} \cdot {\color{green}231} \cdot [637] \\ n &=& 469374541 + 200267067 \\ n &=& 669641608 \\\\ && n\pmod {m}\\ &=& 669641608 \pmod {288057} \\ &=& 197140 \\\\ n &=& 197140 + k\cdot 288057 \qquad k \in Z\\\\ \mathbf{n_{min}} & \mathbf{=}& \mathbf{197140 } \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 Heureka’s mathematical solution and Latex presentation:}\\ \)
+118725 Thanks Ginger,
I used The Euclidean formula and the extended euclidean formula as well but the working went for ever. Maybe I will give it another go. I thought myabe our guest knew what s/he was talking about and might explain it simply. ://
I'm not so sure I follow what you did either I will have to study it ://
+118725 Ginger: Your LaTex is really cool. 
Mine is never as good as I want it to be :((
+2236 Thank you. I’ve studied and learned the techniques of two LaTex masters: Heureka and Lancelot Link. 
+2236 This method utilizes Euler's theorem for computing modular inverses. This is especially useful when the moduli are prime numbers because calculating totients for prime numbers is a trivial process. The rest of the algorithm is an extension of cross multiplication similar to the Chinese remainder theorem, but much less cumbersome.
GA
The first answer of 333331 is the right answer, even though I don't understand how Guest #1 got the answer, since it satisfies the two modular equations:
333331 mod 3331 =231 and 333331 mod 1361=1247
If Gingerale's answer is 197140, it does not work. I also don't understand the method he/she used.
GingerAle: It looks like you laid a big, fat "Turkey Egg" !! Happy Thanksgiving !.
+2236 LMAO I did. ... I did. I did lay a big, fat Turkey Egg. LOL
I’ll hatch it for you. Then you’ll have an intelligent companion by Christmas.
+112 Ginger couldn’t a soar with the eagle because she’s hanging with a turkey.
+2236 Here’s the correct presentation. Previously, I transposed the number and modulus divisor.
An excess consumption of fermented bananas might be a major contributing factor in the cause. I’ve left the previous presentation as a monument to my error (The math is fine). This is an extremely rare event: this is only the second time I’ve made a mistake.
The first time was when I thought I made a mistake, but I didn’t, so I was wrong in thinking I did.
-------------
\(\begin{array}{rcll} n &\equiv& {\color{red}231} \pmod {{\color{green}3331}} \\ n &\equiv& {\color{red}1247} \pmod {{\color{green}1361}} \\ \text{Set } m &=& 3331\cdot 1361 = 4533491\\ \\ \end{array} \)
\(\begin{array}{rcll} n &=& {\color{red}231} \cdot {\color{green}1361} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ {\color{green}1361}^{\varphi({\color{green}3331})-1} \pmod {{\color{green}3331}} ] }_{=\text{modulo inverse 1361 mod 3331} } }_{=1361^{3330-1} \mod {3331} }}_{=1361^{3329} \mod {3331}}}_{=1980} + {\color{red}1247} \cdot {\color{green}3331} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ {\color{green}3331}^{\varphi({\color{green}1361})-1} \pmod {{\color{green}1361}} ] }_{=\text{modulo inverse 3331 mod 1361} } }_{=3331^{1360-1} \mod {1361} }}_{=3331^{1359} \mod {1361}}}_{=552}\\\\ n &=& {\color{red}231} \cdot {\color{green}1361} \cdot [ 1980] + {\color{red}1247} \cdot {\color{green}3331} \cdot [552] \\ n &=& 622494180+ 2292873864\\ n &=& 2915368044\\\\ && n\pmod {m}\\ &=& 2915368044\pmod {4533491} \\ &=& 333331\\\\ n &=& 333331+ k\cdot 4533491\qquad k \in Z\\\\ \mathbf{n_{min}} & \mathbf{=}& \mathbf{333331} \end{array} \)
