Congruence and Modular Arithmetic

### Chinese Remainder Theorem (CRT)

For all integers $a_{1}$ and $a_{2}$, and positive integers $m_{1}$ and $m_{2}$, if $g(m_{1},m_{2})=1$, then the simultaneous linear congruences $n≡a_{1}(modm_{1})$ $n≡a_{2}(modm_{2})$

have a unique solution modulo $m_{1}m_{2}$. Thus, if $n=n_{0}$ is one particular solution, then the solutions are given by the set of all integers $n$ such that

$n≡n_{0}(modm_{1}m_{2})$

### Generalized Chinese Remainder Theorem (GCRT)

For all positive integers $k$ and $m_{1},m_{2},…,m_{k}$, and integers $a_{1},a_{2},…,a_{k}$, if $g(m_{i},m_{j})=1$ for all $i=j$, then the simultaneous congruences

$n≡a_{1}(modm_{1})$ $n≡a_{2}(modm_{2})$ $⋮$ $n≡a_{k}(modm_{k})$ have a unique solution modulo $m_{1},m_{2},…,m_{k}$. Thus, if $n=n_{0}$ is one particular solution, then the solutions are given by the set of all integers $n$ such that $n≡n_{0}(modm_{1}m_{2}…m_{k})$