CRT

$$\begin{array}{rl}x& \equiv a_1\mathrm{mod}{n}_1\\ x& \equiv a_2\mathrm{mod}{n}_2\\ \cdots \\ x& \equiv a_k\mathrm{mod}{n}_k\end{array}$$

$$N=\prod _{i=1}^k{n}_i$$

Where the

$n_i$ are pairwise coprime. then there is one and only one integer

$x,0\le x<N$ satisfy them.

$$\begin{array}{rl}x& \equiv a_1\mathrm{mod}{n}_1\\ x& \equiv a_2\mathrm{mod}{n}_2\end{array}$$

$n_1{m}_1+n_2{m}_2=1$ calculate

$m_1,m_2$ by Extended Euclidean algorithm

$$\begin{array}{rl}x& =a_1{n}_2{m}_2+a_2{n}_1{m}_1\\ & =a_1(1-n_1{m}_1)+a_2{n}_1{m}_1=a_1{n}_2{m}_2+a_2(1-n_2{m}_2)\\ & =a_1+(a_2-a_1)m_1{n}_1=a_2+(a_1-a_2)n_2{m}_2\end{array}$$

example

$$\begin{array}{rl}x& \equiv 2\mathrm{mod}3\\ x& \equiv 3\mathrm{mod}5\\ x& \equiv 2\mathrm{mod}7\end{array}$$

calculate:

$3m_1+5m_2=1$

$$\begin{array}{ccc}{r}_0=a=5& s_0=1& t_0=0\\ r_1=b=3& s_1=0& t_1=1\\ r_2=r_0-q_1{r}_1=5-1\cdot 3=2& s_2=s_0-q_1{s}_1=1-1\cdot 0=1& t_2=t_0-q_1{t}_1=0-1\cdot 1=-1\\ r_3=r_1-q_2{r}_2=3-1\cdot 2=1& s_3=s_1-q_2{s}_2=0-1\cdot 1=-1& t_3=t_1-q_2{t}_2=1-1\cdot (-1)=2\\ r_4=r_2-q_3{r}_3=2-2\cdot 1=0& s_4=s_2-q_3{s}_3=1-2\cdot (-1)=3& t_4=t_2-q_3{t}_3=-1-2\cdot 2=-5\end{array}$$

$gcd(5,3)=1$

$m_1=s_3=2$

$m_2=t_3=-1$

$3\cdot 2+5\cdot (-1)=1$

$x_{1,2}=a_1{n}_2{m}_2+a_2{n}_1{m}_1=2\cdot 5\cdot (-1)+3\cdot 3\cdot 2=8$

$$\begin{array}{rl}x& \equiv 8\mathrm{mod}15\\ x& \equiv 2\mathrm{mod}7\end{array}$$

calculate:

$15m_1+7m_2=1$

$$\begin{array}{ccc}{r}_0=a=15& s_0=1& t_0=0\\ r_1=b=7& s_1=0& t_1=1\\ r_2=r_0-q_1{r}_1=15-2\cdot 7=1& s_2=s_0-q_1{s}_1=1-2\cdot 0=1& t_2=t_0-q_1{t}_1=0-2\cdot 1=-2\\ r_3=r_1-q_2{r}_2=7-7\cdot 1=0& s_3=s_1-q_2{s}_2=0-7\cdot 1=-7& t_3=t_1-q_2{t}_2=1-7\cdot (-2)=15\end{array}$$

$gcd(15,7)=1$

$m_1=s_3=1$

$m_2=t_3=-2$

$x=8\cdot 7\cdot (-2)+2\cdot 15\cdot 1=-112+30=-82$

$x\equiv -82\equiv =-82+15\cdot 7=23\mathrm{mod}105$