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.

Guest Nov 23, 2017

#1**0 **

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.

Guest Nov 23, 2017

#3**+2 **

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:}\\ \)

GingerAle Nov 23, 2017

#4**0 **

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 ://

Melody
Nov 23, 2017

#7**0 **

Ginger: Your LaTex is really cool.

Mine is never as good as I want it to be :((

Melody
Nov 23, 2017

#11**+2 **

Thank you. I’ve studied and learned the techniques of two LaTex masters: Heureka and Lancelot Link.

GingerAle
Nov 25, 2017

#12**+3 **

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

GingerAle
Nov 25, 2017

#5**+1 **

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.

Guest Nov 23, 2017

#6**+1 **

GingerAle: It looks like you laid a big, fat "Turkey Egg" !! Happy Thanksgiving !.

Guest Nov 23, 2017

#8**+3 **

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.

GingerAle
Nov 24, 2017

#9**+1 **

Ginger couldn’t a soar with the eagle because she’s hanging with a turkey.

JacobBernoulli
Nov 24, 2017

#10**+4 **

**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} \)

GingerAle Nov 25, 2017