# How to use the Chinese Remainder theorem to solve a system of congruences

In my class the exact test of the Chinese Remainder Theorem we learned stated \begin{align*} x &\equiv a_1 \pmod{n_1}\\ x &\equiv a_2 \pmod{n_2}\\ ...\\ x &\equiv a_L \pmod{n_L}. \end{align*} has a unique solution modulo the product $n_1n_2...n_L$ if all the $n$'s are pairwise relatively prime.

How does this help us solve the following question. Other sources say to use a product $M$ along with $M_1,M_2,...$ all of which are absent in the text of my CRT

Find the smallest positive integer $x$ so that \begin{align*} x &\equiv 3 \pmod{7}\\ x &\equiv 12 \pmod{11}\\ x &\equiv 5 \pmod{13}. \end{align*}

• I find it best, usually, to go step by step. From the first, we write $x=3+7t$. Now, for the second, we want $3+7t\equiv 1 \pmod {11}$ or $4t\equiv 2 \pmod {11}$. Easy to solve that, which will tell us a class $\pmod {77}$ that passes the first two tests. Now do the third the same way. – lulu Mar 29 '17 at 0:09

## 2 Answers

$2\cdot 7 = 14 \equiv 1\pmod{13}\\ 3 + 2\cdot2\cdot 7 = 31\equiv 5\pmod{13}$

That gets us part way there.

Now we need to find an $n$, such that

$31+n\cdot 7\cdot 13 \equiv 12\equiv 1\pmod{11}\\ 31 \equiv 9\pmod {11}\\ 91 \equiv 3\pmod {11}\\ x=122$

• @Dario just because I studied math doesn't mean I know how to do basic addition very well. – Doug M Mar 29 '17 at 0:28

Let's take it step by step:

A) $x \equiv 3 = a_7 \mod 7$ and $x \equiv 12 \equiv 1 = a_{11} \mod 11$ (um, is that a typo?)

1) Solve $7m_{3} + 11m_{11}$. You can eyeball this or use Euclid's Algorithm

$11 = 7 +4; 4 = 11 -7$

$7 = 4 + 3; 3 = 7 -4$

$4 = 3 + 1; 1= 4 -3$

$= 4 - (7-4) = 2*4-7$

$= 2*(11-7) - 7 = 2*11 - 3*7$

$m_{11} = 2; m_7 = -3$

2) I plug in the formula I have memorized $x \equiv a_7*11*m_{11} + a_{11}*7*m_7 \mod 7*11$. So $x = 3*11*2 - 1*7*3 = 45 \mod 77$ and $45 \equiv 1 \mod 11$ and $45 \equiv 3 \mod 7$.

This works because $a_7*11*m_{11} + a_{11}*7*m_7 \mod 7$

$\equiv a_7*11*m_{11} + a_7*7*m_7 + (a_{11} - a_7)*7*m_7 \mod 7$

$\equiv a_7(11*m_{11} + 7*m_7) \mod 7$

$\equiv a_7 \mod 7$. and

$a_7*11*m_{11} + a_{11}*7*m_7 \mod 11$

$\equiv a_{11}*11*m_{11} + a_{11}*7*m_7 + (a_{7} - a_{11})*11*m_{11} \mod 11$

$\equiv a_{11}(11*m_{11} + 7*m_7) \mod 11$

$\equiv a_{11} \mod 11$

B) $x \equiv 45 \mod 77$

$x \equiv 5\mod 13$

1) Solve $m_{77}77 + m_{13}13 = 1$.

$77 = 5*13 + 12;12 =77 - 5*13$

$13 = 12 + 1$ so

$1 = 13 - 12$

$= 13 - (77 - 5*13)$

$= 6*13 - 77$

2) $x = a_{77}m_{13}*13 + a_{13}m_{77}*77 = 45*6*13 - 5*77 = 3125 \mod 13*77\equiv 122 \mod 1001$ and the solution is $x =122$.