+0  
 
0
954
12
avatar

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.

 Nov 23, 2017
 #1
avatar
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.

 Nov 23, 2017
 #2
avatar+108608 
0

You lost me after the word 'simple'.

Melody  Nov 23, 2017
 #3
avatar+1849 
+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:}\\ \)

.
 Nov 23, 2017
edited by GingerAle  Nov 23, 2017
 #4
avatar+108608 
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
avatar+108608 
0

Ginger:  Your LaTex is really cool.   laugh

 

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

Melody  Nov 23, 2017
 #11
avatar+1849 
+2

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

GingerAle  Nov 25, 2017
 #12
avatar+1849 
+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. 

 

GAsmiley

GingerAle  Nov 25, 2017
 #5
avatar
+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.

 Nov 23, 2017
 #6
avatar
+1

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

 Nov 23, 2017
 #8
avatar+1849 
+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.smiley

GingerAle  Nov 24, 2017
 #9
avatar+98 
+1

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

JacobBernoulli  Nov 24, 2017
 #10
avatar+1849 
+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.surprise  The first time was when I thought I made a mistake, but I didn’t, so I was wrong in thinking I did. smiley

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

 

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

.
 Nov 25, 2017

12 Online Users

avatar