+0  
 
0
103
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.

Guest Nov 23, 2017
Sort: 

12+0 Answers

 #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.

Guest Nov 23, 2017
 #2
avatar+91256 
0

You lost me after the word 'simple'.

Melody  Nov 23, 2017
 #3
avatar+833 
+1

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
edited by GingerAle  Nov 23, 2017
 #4
avatar+91256 
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+91256 
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+833 
+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+833 
+1

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.

Guest Nov 23, 2017
 #6
avatar
+1

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

Guest Nov 23, 2017
 #8
avatar+833 
+2

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+48 
+1

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

JacobBernoulli  Nov 24, 2017
 #10
avatar+833 
+3

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

GingerAle  Nov 25, 2017

7 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