+0

Can someone teach or explain to me Chinese Remainder Theorem?

+2
113
14
+2552

Chinese Remainder Theorem is used to solve problems like these:

What is the smallest whole number that has a remainder of 1 when divided by 4, a remainder of 1 when divided by 3, and a remainder of 2 when divided by 5

So it becomes:

x = 1 mod(4)

x = 1 mod(3)

x = 2 mod(5)

How would I solve for x using CRT?

It is very confusing, so can someone just explain to me a straight-forward method that I can memorize? This will help me understand how to do it, then later, I can understand why it works.

I tried learning it on AOPS, but their lesson costs money as I have to buy the book. And they don't explain it well in their question solutions on Alcumus.

I also tried watching a video, I copied their exact method to solve a problem, but got a wrong answer, and it was WAYYY off.

Nov 5, 2019
edited by CalculatorUser  Nov 5, 2019
edited by CalculatorUser  Nov 5, 2019

14+0 Answers

#1
+1

This computer code incorporates the "Chinese Remainde Theorem + Modular multiplicative Inverse"
i=0;j=0;m=0;t=0;a=(4, 3, 5);r= (1, 1, 2);c=lcm(a); d=c / a[i];n=d % a[i] ;loop1:m++; if(n*m % a[i] ==1, goto loop, goto loop1);loop:s=(c/a[i]*r[j]*m);i++;j++;t=t+s;m=0;if(i< count a, goto4,m=m);printc,"m + ",t % c;return

ANSWER =60 m +  37, where m=0, 1, 2, 3......etc.

Look under this link for detailed explanation of CRT:
https://web2.0calc.com/questions/congruences

Nov 5, 2019
#2
+2552
+1

OMG THANK YOU SO MUCH! I just realized that the numbers are required to be relatively prime!

Thats why I got the problem wrong when I followed the video, because the Question had no relatively prime numbers! The question was making you guess and check.

I can solve system of modulos now! Thanks!

Nov 5, 2019
#3
+2552
+1

Also, what program do you use to run the code? I would like to use your codes to help me solve these questions in the future quickly!

CalculatorUser  Nov 5, 2019
#4
+681
+1

they didn't seem to use the semicolon at the end of their lines of code...so i'm guessing python (don't take my word, but try to run it through to see if it works)

it could also be something funky as C++ or C# or something which i have NOOOO idea how that works lol

Nirvana  Nov 5, 2019
#5
+1

It is written in C++.

Nov 5, 2019
#6
+681
+1

you beat me to it :')

i was about to say it's not python i think its C++

but dang!! C++ is a really hard language to learn, congrats :)

Nirvana  Nov 5, 2019
#7
+2552
+1

Thanks, probs during the summer (which is far far away lol) I am going to take some computing classes so I can be cool like you

Probably I will start with Java, because it  is the most common and easy one.

THank you Guest and Nirvana!

Nov 5, 2019
edited by CalculatorUser  Nov 5, 2019
#8
+681
+1

Believe it or not,,, i was just thinking of that too...

do you know what language you're gonna learn CU? :D

Nirvana  Nov 5, 2019
#9
+2552
+1

Yup just edited and replied!

CalculatorUser  Nov 5, 2019
#10
+681
+1

awesome!! :D

Nirvana  Nov 5, 2019
#11
+1830
+3

Solution:

This method uses Euler's totient and the modulo inverse functions.

$$\begin{array}{rcll} n &\equiv& {\color{red}1} \pmod {{\color{green}4}} \\ n &\equiv& {\color{red}1} \pmod {{\color{green}3}} \\ n &\equiv& {\color{red}2} \pmod {{\color{green}5}} \\ \text{Set } m &=& 4\cdot 3\cdot 5 = 60 \\ \end{array}$$

$$\small{ \begin{array}{l} n = {\color{red}1} \cdot {\color{green}3\cdot 5} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}3 \cdot 5) }^{\varphi({\color{green}4}) -1 } \pmod {{\color{green}4}} ] }_{=\text{modulo inverse }(3\cdot 5) \mod 4 } }_{=(3\cdot 5)^{2-1} \mod {4}} }_{=(3\cdot 5)^{1} \mod {4}} }_{=(15\pmod{4})^{1} \mod {4}} }_{=(15)^{1} \mod {4}} }_{= 3} + {\color{red}1} \cdot {\color{green}4\cdot 5} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}4\cdot 5) }^{\varphi({\color{green}3}) -1} \pmod {{\color{green}3}} ] }_{=\text{modulo inverse } (4\cdot 5) \mod {3}} }_{=(4\cdot 5)^{2-1} \mod {3}} }_{=(4\cdot 5)^{1} \mod {3}} }_{=(20\pmod{3})^{1} \mod {3}} }_{=(2)^{1} \mod {3}} }_{=2} + {\color{red}2} \cdot {\color{green}4\cdot 3} \cdot \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ \underbrace{ [ { (\color{green}4\cdot 3) }^{\varphi({\color{green} 5}) -1 } \pmod {{\color{green}5}} ] }_{=\text{modulo inverse } (4\cdot 3) \mod 5 } }_{=(4\cdot 3)^{4-1} \mod { 5}} }_{=(4\cdot 3)^{3} \mod {5}} }_{=(12\pmod{5})^{3} \mod {5}} }_{=(2)^{3} \mod {5}} }_{=3}\\ \\ n = {\color{red}1} \cdot {\color{green}3\cdot 5} \cdot [3] + {\color{red}1} \cdot {\color{green}4\cdot 5} \cdot [2] + {\color{red}2} \cdot {\color{green}4\cdot 3} \cdot [3] \\ n = 45+ 40 + 72 \\ n = 157 \\\\ n \pmod {m} = 157 \pmod {60} \\ n = 37+ k\cdot 60 \; \; k \in Z\\ \mathbf{n_{min}} \; \mathbf{=} \; \mathbf{37} \end{array} }$$

GA

.
Nov 5, 2019
edited by GingerAle  Nov 5, 2019
#12
+1830
0

Additional comments:

Pending ....

Nov 5, 2019
#13
+23893
+1

What is the smallest whole number that has

a remainder of 1 when divided by 4,

a remainder of 1 when divided by 3,

and a remainder of 2 when divided by 5

So it becomes:

x = 1 mod(4)

x = 1 mod(3)

x = 2 mod(5)

$$\begin{array}{rcll} x &\equiv& {\color{red}1} \pmod {{\color{green}4}} \\ x &\equiv& {\color{red}1} \pmod {{\color{green}3}} \\ x &\equiv& {\color{red}2} \pmod {{\color{green}5}} \\ \text{Let } m &=& 4\cdot 3\cdot 5 = 60 \\ \end{array}$$

Because 4 and 3 and 5 are relatively prim  we can go on:

$$\begin{array}{|rclcl|} \hline x &=& {\color{red}1} \cdot {\color{green}3\cdot 5} \cdot \left[\dfrac{1}{\color{green}3\cdot 5}\pmod{4} \right] + {\color{red}1} \cdot {\color{green}4\cdot 5} \cdot \left[\dfrac{1}{\color{green}4\cdot 5}\pmod{3} \right] \\ &+& {\color{red}2} \cdot {\color{green}4\cdot 3} \cdot \left[\dfrac{1}{\color{green}4\cdot 3}\pmod{5} \right] + {\color{green}4\cdot 3\cdot 5}\cdot k \quad | \quad k \in \mathbb{Z} \\ \hline && \left[\dfrac{1}{\color{green}3\cdot 5}\pmod{4} \right] \\ && \equiv \left[ { (\color{green}3\cdot 5) }^{\varphi({\color{green}4}) -1 } \pmod {{\color{green}4}} \right] \quad | \quad \varphi({\color{green}4}) = 2 \\ && \equiv \left[ { 15 }^{2 -1} \pmod {{\color{green}4}} \right] \\ && \equiv \left[ { 15 } \pmod {{\color{green}4}} \right] \\ && \equiv \left[ { 3 } \pmod {{\color{green}4}} \right] \\ \hline && \left[\dfrac{1}{\color{green}4\cdot 5}\pmod{3} \right] \\ && \equiv \left[ { (\color{green}4\cdot 5) }^{\varphi({\color{green}3}) -1 } \pmod {{\color{green}3}} \right] \quad | \quad \varphi({\color{green}3}) = 2 \\ && \equiv \left[ { 20 }^{2 -1} \pmod {{\color{green}3}} \right] \\ && \equiv \left[ { 20 } \pmod {{\color{green}3}} \right] \\ && \equiv \left[ { 2 } \pmod {{\color{green}3}} \right] \\ \hline && \left[\dfrac{1}{\color{green}4\cdot 3}\pmod{5} \right] \\ && \equiv \left[ { (\color{green}4\cdot 3) }^{\varphi({\color{green}5}) -1 } \pmod {{\color{green}5}} \right] \quad | \quad \varphi({\color{green}5}) = 4 \\ && \equiv \left[ { 12 }^{4 -1} \pmod {{\color{green}5}} \right] \\ && \equiv \left[ { 12^3 } \pmod {{\color{green}5}} \right] \quad 12 \pmod{5} \equiv 2 \pmod{5} \\ && \equiv \left[ { 2^3 } \pmod {{\color{green}5}} \right] \\ && \equiv \left[ { 8 } \pmod {{\color{green}5}} \right] \\ && \equiv \left[ { 3 } \pmod {{\color{green}5}} \right] \\ \hline x &=& {\color{red}1} \cdot {\color{green}3\cdot 5} \cdot [3] + {\color{red}1} \cdot {\color{green}4\cdot 5} \cdot [2] + {\color{red}2} \cdot {\color{green}4\cdot 3} \cdot [3] + 60\cdot k \quad | \quad k \in \mathbb{Z} \\ x &=& 45+ 40 + 72 + 60\cdot k \\ x &=& 157+ 60\cdot k \quad | \quad 157 \pmod {60} = 37 \\ x &=& 37+ 60\cdot k \qquad k \in Z \\ \mathbf{x_{min}} &=& \mathbf{ 37} \\ \hline \end{array}$$

Nov 5, 2019
#14
+2552
+1

wow... this site has shown its true power!

Thank you guys!

Nov 6, 2019