The following theorem is known as the Chinese remainder theorem because it was discovered by Qin Jiushao (1202 - 1261).

Theorem: Chinese Remainder Theorem

Let $m_1,m_2,\ldots,m_r$ be positive integers and let $a_1,\ldots,a_r$ be any integers. The simultaneous congruences $$\begin{array}{rcl} x(m_1)&\equiv&a_1(m_1)\\ x(m_2)&\equiv&a_2(m_2)\\ &\vdots&\\ x(m_r)&\equiv& a_r(m_r)\\ \end{array}\label{eq:E18594}\tag{*}$$ have a solution if and only if for all pairs of numbers $a_i,a_j$ with $i\neq j$ the greatest common divisor $d:=\gcd(a_i,a_j)$ is a divisor of $a_i-a_j$ (equivalently $a_i\equiv a_j\mod \gcd(a_i,a_j)$ whenever $i\neq j$).

In this case, the solution consists of all integers belonging to a single congruence class modulo $m=\operatorname{lcm}(m_1,m_2,\cdots, m_r),$ where $m$ is the least common multiple of the $r$ numbers $m_1,\ldots,m_r.$

In particular, $(\ref{eq:E18594})$ is always solvable if $m_i\perp m_j$ are co-prime, whenever $i\neq j.$

Proofs: 1

Persons: 1
Proofs: 2


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Landau, Edmund: "Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927
  2. Jones G., Jones M.: "Elementary Number Theory (Undergraduate Series)", Springer, 1998