logoMath 350 Tools

Chinese Remainder Theorem

Find the prime factors of any number less than a billion!

Input

  • x ≡
    %
  • x ≡
    %
  • x ≡
    %

Output

Result

23

Steps

\(m = m_{1} \cdot m_{2} \cdot m_{3} = 3 \cdot 5 \cdot 7 = 105\)\(M_{1} = \frac{m}{m_{1}} = \frac{105}{3} = 35\)\(M_{2} = \frac{m}{m_{2}} = \frac{105}{5} = 21\)\(M_{3} = \frac{m}{m_{3}} = \frac{105}{7} = 15\)To solve for \(y_k\) : \(M_k \cdot y_k \equiv 1 \pmod{m_k}\) \(35 \cdot y_{1} \equiv 1 \pmod{3}\) \( \rightarrow y_{1} = 2\)\(21 \cdot y_{2} \equiv 1 \pmod{5}\) \( \rightarrow y_{2} = 1\)\(15 \cdot y_{3} \equiv 1 \pmod{7}\) \( \rightarrow y_{3} = 1\)\(x \equiv a_{1} M_{1} y_{1} + a_{2} M_{2} y_{2} + a_{3} M_{3} y_{3} \pmod{m}\)\(x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \pmod{105}\)\(x \equiv 233 \pmod{105} = 23\)