# Chinese remainder theorem for divisibility problem

Find the smallest $n$ so that:

$n$ divided by $3$ gives remainder $2$, $n$ divided by $11$ gives remainder $8$, $n$ divided by $27$ gives remainder $5$, $n$ divided by $47$ gives remainder $40$.

I’m not sure if it is $2813$, but that is the number I used to generate this problem. Anyways, I’m trying to figure out how to use the Chinese remainder to solve this problem step by step. I’ve seen “tricks” where they use the LCM and other things, but I need to know the way with the Chinese remainder theorem for my exam.

#### Solutions Collecting From Web of "Chinese remainder theorem for divisibility problem"

The following is not the fastest method, but it’s pretty simple so I like to use it.

40 (=13 mod 27 .. No) -> 87 (=6 mod 27, no) -> 134 (26) ->181 (19) ->228 (12) ->275 (5:yes!)

OK, so now keep adding 27*47 =1269 until you get 8 modulo 11:

275 (=0 mod 11, no)->1544 (4, no)-> 2813 (yes!)

OK, so now keep adding 11*27*47 until you get 2 module 3:

2813 (= 2 modulo 3: yes!)

OK, so that’s indeed the answer:2813

You have $M = 11\times 27\times 47 = 13959$ and $M_1 = M/11 = 1269$, $M_2 = M/27 = 517$, $M_3 = M/47 = 297$. Taking $y_1$, $y_2$, $y_3$ such that $M_1y_1 = 1$ (mod 11), $M_2y_2 = 1$ (mod 27), $M_3y_3 = 1$ (mod 47). Then we have $$n = 8M_1y_1 + 5M_2y_2 + 40M_3y_3.$$

EDIT: make some simple calculation, you have $y_1 = 3$, $y_2 = 7$, $y_3 = 22$, then $n = 309911 = 2813$ (mod M).

The following solution is how I learned how to do these problems at first, and can be quite long, but uses a fairly straight forward algorithm so it tends to be accurate.

This problem is equivalent to solving the system of congruences:
$$(*)\begin{cases}n\equiv 2\mod 3\qquad (1)\\n\equiv 8\mod 11\qquad (2)\\n\equiv 5\mod 27\qquad (3)\\n\equiv 40\mod 47\qquad (4)\end{cases}$$
You can use the fact that
$$(**)\begin{cases}x\equiv a\mod m\\x\equiv b\mod n\end{cases}$$
has a solution $\color{red}{x_0=anv+bmu}$ where $u,v\in\Bbb Z$ satisfy $mu+nv=1$. Notice that this solution requires that $\gcd(m,n)=1$ since $\gcd(m,n)=1\iff \exists u,v\in\Bbb Z:mu+nv=1$. Also, any solution to $(**)$ will be congruent to $x_0$ modulo $m\cdot n$. In your question, we see that $3$ and $27$ are not relatively prime, so we can first reduce the system involving $(1)$ and $(3)$, which is the system
$$(***)\begin{cases}n\equiv 2\mod 3\\n\equiv 5\mod 27\end{cases}$$
Note that $(***)$ will have a solution because $\gcd(3,27)=3$ and $2\equiv 5\mod 3$. This comes from the fact that, if $d=\gcd(m,n)$, then the system $(**)$ has a solution if and only if $a\equiv b\mod d$. Indeed, this boils down the original system $(*)$ to the following:
$$(****)\begin{cases}n\equiv 5\mod 27\qquad (5)\\n\equiv 8\mod 11\\n\equiv 40\mod 47\end{cases}$$
since $n=5$ satisfies $n\equiv 2\mod 3$. Then we see that $27,11,47$ are all relatively prime (pairwise), and so you can use the aforementioned particular solution (i.e. $x_0$ as highlighted in red), where you first solve the system of congruences $(5)$ and $(2)$, and then take that solution and solve the system of congruences with $(4)$. Any solution to $(****)$ will be unique modulo $27\cdot 11\cdot 47=13959$.

Just to show you how to solve systems like $(**)$, a solution to the system involving $(5)$ and $(2)$ is $x_0=(5)(11)(5)+(8)(27)(-2)=-157$ since $27(-2)+11(5)=1$. Then this system has a unique solution modulo $27\cdot 11=297$, and is $-157\equiv 140\mod 297$. So now you have to solve the final system:
$$(*****)\begin{cases}n\equiv 140\mod 297\\n\equiv 40\mod 47\end{cases}$$

A Summary:
\begin{align}&(1)\qquad\text{Break the system (*) into smaller systems like (**).}\\&(2)\qquad\text{Find integers u and v such that mu+nv=1, where m and n are described in (**)}\\&(3)\qquad\text{Use the particular solution x_0=anv+bmu which solves (**)}\\&(4)\qquad\text{Pair these solutions to the smaller congruence systems together to form new} \\&\qquad\qquad\text{systems until you have reduced the system to one congruence.}\end{align}

3 is not needed, it is taken care of by 27. Begins with

$$27 \cdot (-2) + 11 \cdot 5 = 1$$
$$297 \cdot 22 + 47 \cdot (-139) = 1$$

$$8 \cdot 27 \cdot (-2) + 5 \cdot 11 \cdot 5 = -432 + 275 = -157$$
is $8 \pmod {11}$ and $5 \pmod {27}.$

$$40 \cdot 297 \cdot 22 + (-157) \cdot 47 \cdot (-139) = 1287041$$
is $40 \pmod {47}$ and $-157 \pmod {297}$

Now, as you knew,
$$1287041 \equiv 2813 \pmod {13959},$$
$$27 \cdot 11 \cdot 47 = 13959$$
$$1287041 = 92 \cdot 13959 + 2813$$
$$-157 + 297 = 140 \equiv -157 \pmod {297}$$
$$40 \cdot 297 \cdot 22 + 140 \cdot 47 \cdot (-139) = 261360-914620 = -653260$$