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.

CalculatorUser Nov 5, 2019

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

Guest Nov 5, 2019

#2**+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!

CalculatorUser Nov 5, 2019

#3**+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

#7**+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!

CalculatorUser Nov 5, 2019

#11**+4 **

Solution:

This method uses ** Euler's totient** and the

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

.GingerAle Nov 5, 2019

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

heureka Nov 5, 2019