中国剰余定理

中国剰余定理(Chinese Remainder Theorem)

定理

$ m_1 と $ m_2 を互いに素な正の整数とする。

互いに素は共通の約数が1

つまり素数

$ x≡b_1 \pmod{m_1}

$ x≡b_2 \pmod{m_2}

を満たす整数$ x が 0 以上 $ m_1m_2 未満にただ 1 つ存在する。特にそれを$ r とすると

$ x≡b_1 \pmod{m_1}, x≡b_2 \pmod{m_2}

$ \hspace{3mm} \Lrarr x≡r \pmod{m_1m_2}

が成立する。

元記事の証明は見てもまだ全然ピンとこない。

$ \equiv の演算子については下記ページを見る

参考

確認用

Q. 中国剰余定理