\(
\begin{align*}
\begin{cases}
x \equiv 2 \hspace{2mm} (mod \hspace{1mm} 3) \hspace{8mm} 2,5,8,11,14,17,20,\textbf{23},\cdots \\
x \equiv 3 \hspace{2mm} (mod \hspace{1mm} 5) \hspace{8mm} 3,8,13,18,\textbf{23},28,\cdots \\
x \equiv 2 \hspace{2mm} (mod \hspace{1mm} 7) \hspace{8mm} 2,9,16,\textbf{23},30,\cdots
\end{cases}
\end{align*}
\)
\( n_1=3, n_2=5, n_3=7 \)
\( N = n_1 \times n_2 \times n_3 = 3 \times 5 \times 7 = 105 \)
\( a_1=2, a_2=3, a_3=2. \)
Now \( N_1 = \frac{N}{n_1} = 35 \) and so \(d_1 \equiv 35^{-1} \hspace{2mm} (mod \hspace{1mm} 3) = 2 \),
\( N_2 = \frac{N}{n_2} = 21 \) and so \(d_2 \equiv 21^{-1} \hspace{2mm} (mod \hspace{1mm} 5) = 1 \), and
\( N_3 = \frac{N}{n_3} = 15 \) and so \(d_3 \equiv 15^{-1} \hspace{2mm} (mod \hspace{1mm} 7) = 1 \). Hence
\( x \equiv (2 \times 35 \times 2) + (3 \times 21 \times 1) + (2 \times 15 \times 1) = 233 ≡ 23 \hspace{2mm} (mod \hspace{1mm} 105) \)
The Chinese Remainder Theorem
If the \(n_i\) are pairwise coprime, and if \(a_1, …, a_k\) are any integers
\(
\begin{align}
x \equiv a_1 \hspace{2mm} (mod \hspace{1mm} n_1) \\
x \equiv a_2 \hspace{2mm} (mod \hspace{1mm} n_2) \\
x \equiv a_3 \hspace{2mm} (mod \hspace{1mm} n_3) \\
\vdots \\
x \equiv a_k \hspace{2mm} (mod \hspace{1mm} n_k)
\end{align}
\)
has a simultaneous solution which is unique modulo \(n_1n_2⋯n_k\).
Gauss’s algorithm
Let \(N = \prod_{i=1}^k n_i \) then
\(x ≡ \sum_{i=1}^k a_iN_id_i \hspace{2mm} (mod \hspace{1mm} N)\)
where \(N_i = N/n_i\) and \(d_i ≡ N_i^{-1} \hspace{2mm} (mod \hspace{1mm} n_i).\)
The latter modular inverse \(d_i\) is easily calculated by the extended Euclidean algorithm.