# CRT

$$\begin{align*} x & \equiv a_1 \mod n_1 \\ x & \equiv a_2 \mod n_2 \\ \cdots \\ x & \equiv a_k \mod n_k \end{align*}$$

$$N = \prod_{i=1}^k n_i$$

Where the $n_i$ are pairwise coprime. then there is one and only one integer $x, 0\leq x < N$ satisfy them.

$$\begin{align*} x & \equiv a_1 \mod n_1 \\ x & \equiv a_2 \mod n_2 \end{align*}$$

$n_1 m_1 + n_2 m_2 = 1$ calculate $m_1, m_2$ by [Extended Euclidean algorithm](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)

$$\begin{align*} x &= a_1 n_2 m_2 + a_2 n_1 m_1 \\ &= a_1(1-n_1m_1) + a_2 n_1 m_1 = a_1 n_2 m_2 + a_2 (1-n_2m_2) \\ &= a_1 + (a_2-a_1)m_1n_1 = a_2 + (a_1-a_2)n_2m_2\end{align*}$$

example

$$\begin{align*}x & \equiv 2 \mod 3 \\ x & \equiv 3 \mod 5 \\ x &\equiv 2 \mod 7 \end{align*}$$

calculate:

$3m_1 + 5m_2 = 1$

$$\begin{matrix} 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_1r_1 = 5 - 1\cdot 3 = 2 & s_2 = s_0 -q_1s_1 = 1 - 1 \cdot 0 = 1 & t_2 = t_0 - q_1t_1 = 0 - 1\cdot1 = -1 \\ r_3 = r_1 -q_2r_2 = 3 - 1 \cdot 2= 1 & s_3 = s_1 - q_2 s_2 = 0 - 1\cdot 1 = -1 & t_3 = t_1 - q_2t_2 = 1 - 1 \cdot (-1) = 2 \\ r_4 = r_2 - q_3r_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{matrix}$$

$\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_1n_2m_2 + a_2n_1m_1 = 2\cdot 5 \cdot (-1) + 3 \cdot 3 \cdot 2 = 8$

$$\begin{align*} x &\equiv 8 \mod 15 \\ x &\equiv 2 \mod 7 \end{align*}$$

calculate:
$15 m_1 + 7 m_2 = 1$

$$\begin{matrix} 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_1r_1 = 15 - 2 \cdot 7 = 1 & s_2 = s_0 -q_1s_1 = 1 - 2 \cdot 0 = 1 & t_2 = t_0 - q_1t_1 = 0 - 2\cdot1 = -2 \\ r_3 = r_1 -q_2r_2 = 7 - 7 \cdot 1= 0 & s_3 = s_1 - q_2 s_2 = 0 - 7\cdot 1 = -7 & t_3 = t_1 - q_2t_2 = 1 - 7 \cdot (-2) = 15 \end{matrix}$$

$\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 \mod 105$