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 $\gcd (m_1,m_2)=1$, then the simultaneous linear congruences $n\equiv a_1(\mathrm{mod}{m}_1)$ $n\equiv a_2(\mathrm{mod}{m}_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\equiv n_0(\mathrm{mod}{m}_1{m}_2)$

Generalized Chinese Remainder Theorem (GCRT)

For all positive integers $k$ and $m_1,m_2,\dots ,m_k$, and integers $a_1,a_2,\dots ,a_k$, if $\gcd (m_i,m_j)=1$ for all $i\ne j$, then the simultaneous congruences

$n\equiv a_1(\mathrm{mod}{m}_1)$ $n\equiv a_2(\mathrm{mod}{m}_2)$ $⋮$ $n\equiv a_k(\mathrm{mod}{m}_k)$ have a unique solution modulo $m_1,m_2,\dots ,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\equiv n_0(\mathrm{mod}{m}_1{m}_2\dots m_k)$