Chinese Remainder Theorem

Notes

Suppose $n_{1},...,n_{k}$ are positive integers that are pairwise coprime. Then, for any given sequence of integers $a_{1},...,a_{k}$ there exists an integer x that solves the following system of simultaneous congruences:
$\left \{ x\equiv a_{1}\mod n_{1}, x\equiv a_{2}\mod n_{2},...,x\equiv a_{k}mod n_{k} \right \}$
A solution x exists if and only if $a_i\equiv a_j \mod \gcd(n_i,n_j) \, \forall i,j$