中国剰余定理

中国剰余定理(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 の演算子については下記ページを見る

具体例から見てみる。

3で割って、2余る数は、

2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47 50, 53, ...

5で割って、3余る数は、

3, 8, 13, 18, 23, 28, 33, 38, 43, 48, 53, ...

ここで、共通に出てくるものを見てみる。

8, 23, 38, 53, 68, ...

差について見てみると、15になる。

23 - 8 = 15

38 - 23 = 15

15は3×5の数になる。最初に出てくる8と3,5使って剰余の式を組み立てる

x ≡ 8 (mod 15)

参考

確認用

Q. 中国剰余定理