中国の剰余定理 - 知識メモ

中国の剰余定理（Chinese remainder theorem）の証明

与えられた k 個の整数 m_1, m_2, ... , m_k のどの２つも互いに素であるとき、∀b_1, b_2, ... , b_k∈Z に対し




を満たす整数 x が m_1 m_2 ... m_k を法として一意的に存在する。

（証明）




は互いに素なので、拡張ユークリッド互除法より




なる整数 a_i , a_i ' が存在する。よって




である。これらの両辺に b_i をかければ




を得る。これらの左辺の和

を m_i で割った余りは、m_i が含まれていない項

を m_i で割った余りとなる。すなわち m_i を法とした b_i と合同な値となる。
よってこの左辺の和の値を x とすれば、これは定理の条件を満たす。

次に、この x が一意的であることを示す。
ある y が定理の条件を満たすとすれば、



が成立する。
m_1, m_2, ... , m_k のどの２つも互いに素であるから、結局

となるので、m_1 m_2 ... m_k を法として一意的である。