Proof: By Induction

(related to Theorem: Chinese Remainder Theorem)

By hypothesis, $m_1,m_2,\ldots,m_r$ are positive integers and $a_1,\ldots,a_r$ are any integers. We will first prove the theorem for $r=2$ and then the general case by induction. We can assume all $a_i$ are distinct, otherwise, we could replace two congruences of the system by just one and reduce the number of simultaneous congruences. For the case $r=1,$ the Chinese remainder theorem is trivial.

Base Case $r=2$

We will first show that both congruences are solvable simultaneously if and only if the greatest common divisor $d:=\gcd(m_1,m_2)$ is a divisor of $a_1-a_2.$

"$\Rightarrow$"

"$\Leftarrow$"

Now, we will show that all simultaneous solutions belong to a single congruence class modulo the least common multiple $\operatorname{lcm}(m_1,m_2).$

Induction step $r > 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