What is the smallest number under 16,000 that when divided by 127 leaves a remainder of 14, and when divided by 131 leaves a ramainder of 66. Thanks for any help.
+26388 What is the smallest number under 16,000 that
when divided by 127 leaves a remainder of 14,
and when divided by 131 leaves a ramainder of 66.
\(\begin{array}{|rcll|} \hline n \equiv {\color{red}14} \pmod {{\color{green}127}} \\ n \equiv {\color{red}66} \pmod {{\color{green}131}} \\ m=127\cdot 131=16637 \\ \hline \end{array} \)
Because 127 and 131 are relatively prim ( gcd(127,131) = 1! ) we can go on:
\(\begin{array}{rcll} n &=& {\color{red}14} \cdot {\color{green}131} \cdot [ \frac{1}{\color{green}131}\pmod {{\color{green}127}} ] + {\color{red}66} \cdot {\color{green}127} \cdot [ \frac{1}{\color{green}127}\pmod {{\color{green}131}} ] + {\color{green}127}\cdot {\color{green}131} \cdot k \quad & | \quad k\in Z\\ \end{array} \)
\(\begin{array}{rcll} && [ \frac{1}{\color{green}131}\pmod {{\color{green}127}} ] \quad &| \quad \text { modular inverse } 131\cdot \frac{1}{131} \equiv 1 \pmod {127} \\ &=& {\color{green}131}^{\varphi({\color{green}127})-1} \pmod {{\color{green}127}} \quad & | \quad \text{ Euler's totient function } \varphi(n) \quad \varphi(p) = p-1 \\ &=& 131^{126-1} \mod {127} \\ &=& 131^{125} \mod {127} \\ &=& 32 \\\\ && [ \frac{1}{\color{green}127}\pmod {{\color{green}131}} ] \quad &| \quad \text { modular inverse } 127\cdot \frac{1}{127} \equiv 1 \pmod {131} \\ &=& {\color{green}127}^{\varphi({\color{green}131})-1} \pmod {{\color{green}131}} \quad & | \quad \text{ Euler's totient function } \varphi(n)\quad \varphi(p) = p-1 \\ &=& 127^{130-1} \mod {131} \\ &=& 127^{129} \mod {131} \\ &=& 98 \\ \end{array}\)
\(\begin{array}{|rcll|} \hline n &=& {\color{red}14} \cdot {\color{green}131} \cdot 32 + {\color{red}66} \cdot {\color{green}127} \cdot 98 + {\color{green}127}\cdot {\color{green}131} \cdot k \\ n &=& 58688 + 821436 + 16637 \cdot k \\ n &=& 880124 + 16637 \cdot k \quad & | \quad k\in Z \\ \hline \end{array} \)
\(\begin{array}{|rcll|} \hline n_{min} &=& 880124 \pmod {16637 } \\ n_{min} &=& 15000 \\\\ n &=& 15000 + 16637 \cdot k \quad & | \quad k\in Z \\ \hline \end{array} \)
\(\begin{array}{|lrcll|} \hline k=0: & \mathbf{n} &\mathbf{=}& \mathbf{15000} \\ \hline \end{array} \)
The smallest number is 15000
[127R +14] =[131T + 66], solve for R, T
R = 118 and S = 114, Therefore:
127 x 118 + 14 =15,000 The smallest number.
LCM of: 127, 131 =127 x 131 (both are primes)
=16,637. Then, the general formula is:
16,637C + 15,000. And for C=0, 1, 2......etc. we have:
15,000 - The smallest number that satisfies the above conditions.
31,637
48,274.....etc.
+37084 Hey Guest..... I think you were probavly the one who solved a similar problem a day or two ago.....can you explain HOW you solve ONE equation with two variable for the two variables?
THIS one: [127R +14] =[131T + 66], solve for R, T
THANX !!!
+37084 Perhaps a graphical solution like shown below???
Well....will post graph when uploader is working.....
Hello EP: Thanks for the enquiry. I have actually written a program(in Java) that uses iterations to find the the two variables in question. It is only a few lines of code and quite efficient. It can cycle through numbers 1, 2,3......up to perhaps 1 billion in a matter of seconds. It is essentially "trial and error", but it works very well!. There are formal methods of finding the number in question, but modular math can get messy and rather complicated for High School students, and even for the 1st and 2nd year college students. So, I thought why not simplify it by writing a few lines of code, at which I'm rather competent.
It might be a bit of "cheating", but there you have it and it works!.
+37084 Ahhh.... I was imagining it was something like that .....Thanx for the reply !
+12531 What is the smallest number under 16,000 that when divided by 127 leaves a remainder of 14, and when divided by 131 leaves a ramainder of 66. Thanks for any help.
https://picload.org/image/roporror/098.jpg
Thanks Omi67: The programm I have written ONLY looks at "positive integers", but can easily be modified to to find both positive and negative answers.
+37084 I expect they were asking for a positive integer.....if we include NEGATIVES the negative number which meets the criteria is out infinity-ways !
There are also some "quirks" when the answer is negative. For example: -29,911 mod 127 =61!.
But: -29,911 / 127 =-235 x 127 = (-29,911) - (-29,845)=-66 !!!.
+26388 What is the smallest number under 16,000 that
when divided by 127 leaves a remainder of 14,
and when divided by 131 leaves a ramainder of 66.
\(\begin{array}{|rcll|} \hline n \equiv {\color{red}14} \pmod {{\color{green}127}} \\ n \equiv {\color{red}66} \pmod {{\color{green}131}} \\ m=127\cdot 131=16637 \\ \hline \end{array} \)
Because 127 and 131 are relatively prim ( gcd(127,131) = 1! ) we can go on:
\(\begin{array}{rcll} n &=& {\color{red}14} \cdot {\color{green}131} \cdot [ \frac{1}{\color{green}131}\pmod {{\color{green}127}} ] + {\color{red}66} \cdot {\color{green}127} \cdot [ \frac{1}{\color{green}127}\pmod {{\color{green}131}} ] + {\color{green}127}\cdot {\color{green}131} \cdot k \quad & | \quad k\in Z\\ \end{array} \)
\(\begin{array}{rcll} && [ \frac{1}{\color{green}131}\pmod {{\color{green}127}} ] \quad &| \quad \text { modular inverse } 131\cdot \frac{1}{131} \equiv 1 \pmod {127} \\ &=& {\color{green}131}^{\varphi({\color{green}127})-1} \pmod {{\color{green}127}} \quad & | \quad \text{ Euler's totient function } \varphi(n) \quad \varphi(p) = p-1 \\ &=& 131^{126-1} \mod {127} \\ &=& 131^{125} \mod {127} \\ &=& 32 \\\\ && [ \frac{1}{\color{green}127}\pmod {{\color{green}131}} ] \quad &| \quad \text { modular inverse } 127\cdot \frac{1}{127} \equiv 1 \pmod {131} \\ &=& {\color{green}127}^{\varphi({\color{green}131})-1} \pmod {{\color{green}131}} \quad & | \quad \text{ Euler's totient function } \varphi(n)\quad \varphi(p) = p-1 \\ &=& 127^{130-1} \mod {131} \\ &=& 127^{129} \mod {131} \\ &=& 98 \\ \end{array}\)
\(\begin{array}{|rcll|} \hline n &=& {\color{red}14} \cdot {\color{green}131} \cdot 32 + {\color{red}66} \cdot {\color{green}127} \cdot 98 + {\color{green}127}\cdot {\color{green}131} \cdot k \\ n &=& 58688 + 821436 + 16637 \cdot k \\ n &=& 880124 + 16637 \cdot k \quad & | \quad k\in Z \\ \hline \end{array} \)
\(\begin{array}{|rcll|} \hline n_{min} &=& 880124 \pmod {16637 } \\ n_{min} &=& 15000 \\\\ n &=& 15000 + 16637 \cdot k \quad & | \quad k\in Z \\ \hline \end{array} \)
\(\begin{array}{|lrcll|} \hline k=0: & \mathbf{n} &\mathbf{=}& \mathbf{15000} \\ \hline \end{array} \)
The smallest number is 15000
