Case Western Reserve University

Chinese Remainder Theorem

Notes

Suppose $n_1,\dots,n_k$ are positive integers that are pairwise coprime. Then, for any given sequence of integers $a_1,\dots,a_k$ there exists an integer x that solves the following system of simultaneous congruences:
$\begin{cases} x\equiv a_1 & \mod n_1 \\ \dots \\ x \equiv a_k & \mod n_k\end{cases}$
A solution x exists if and only if $a_i\equiv a_j \mod \gcd(n_i,n_j) \, \forall i,j$ .