Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

中国の剰余定理

中国の剰余定理

 m, n \in Z で m, n は互いに素とする。
つまり、 gcd(m, n) = 1
 x = b \mod m
 x = c \mod n
 b, c \in Z
を満たす x \in Z 0 \le x \le nmの範囲にただ一つ存在する。

中国剰余定理の証明と例題(二元の場合) | 高校数学の美しい物語

これは、2つの値の場合ですが、もっと拡張します。
 p_1, p_2, ... p_nを異なる素数とし、
 x = m_1 \mod p_1
 x = m_2 \mod p_2
...
 x = m_n \mod p_n
を満たすxは 0 \le x \le p_1 p_2 \cdot \cdot p_nの範囲にただ一つ存在する。