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

Reference

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

CRT Calculator