Chinese Remainder Theorem - Classic Problems | Repovive

CLS41. Chinese Remainder Theorem

1s256 MB

Given $n$ equations of the form: $x \equiv a_i \pmod{m_i}$

where all $m_i$ are pairwise coprime (their GCD is 1), find the smallest non-negative integer $x$ that satisfies all equations.

\begin{array}{l} n \\ a_1 \quad m_1 \\ a_2 \quad m_2 \\ \vdots \\ a_n \quad m_n \end{array}

x

Input

Explanation

The value 23 satisfies all three equations: 23 mod 3 is 2, 23 mod 5 is 3, and 23 mod 7 is 2. No smaller non-negative value satisfies all three.

Output

Input

2
1 2
2 3

Explanation

The value 5 is 1 modulo 2 and 2 modulo 3. The smaller non-negative values 0 through 4 fail at least one equation.

Output

Input

Explanation

The value 0 satisfies all three equations because every required remainder is 0, so the smallest non-negative answer is 0.

Output

Given $n$ equations of the form: $x \equiv a_i \pmod{m_i}$

where all $m_i$ are pairwise coprime (their GCD is 1), find the smallest non-negative integer $x$ that satisfies all equations.

\begin{array}{l} n \\ a_1 \quad m_1 \\ a_2 \quad m_2 \\ \vdots \\ a_n \quad m_n \end{array}