Chinese Remainder Theorem Calculator

This CRT calculator solve the system of linear congruences \begin{align*} a_1x &\equiv b_1 \pmod{m_1} \\ a_2x &\equiv b_2 \pmod{m_2} \\ &\vdots \\ a_nx &\equiv b_n \pmod{m_n} \end{align*} where $a_i$'s, $m_i$'s are positive integers and $b_i$'s are non-negative integers. The calculator try to find the solution both in the case $m_i$ are pairwise coprime and not pairwise coprime if the solution exist. Note that in the special case of $a_i=1$ for $1\leqslant i\leqslant n$ the problem is reduced to Chinese remainder theorem.

Input Format

The input data must be entered line by line of $a_i$, $b_i$, and $m_i$, separated by at least one space, of linear congruences. For example the linear congruences \begin{align*} 3x &\equiv 2 \pmod{5} \\ 4x &\equiv 7 \pmod{9} \end{align*} should be entered as 

3  2  5
4  7  9
In the case of Chinese remainder theorem all $a_i$ should be one.

Reference

  1. Gareth A. Jones and Josephine M. Jones, Elementary Number Theory (Springer Undergraduate Mathematics Series), 8th printing 2005.
  2. Tom M. Apostol, Introduction to analytic number theory (Undergraduate texts in mathematics), 1976.
  3. A. Bogomolny, Chinese Remainder Theorem from Interactive Mathematics Miscellany and Puzzles. Accessed 23 January 2016

CRT Calculator