中国人剰余定理

中国人剰余定理 (Chinese remainder theorem)

連立１次合同式

x ≡ b₁ (mod d₁ )
x ≡ b₂ (mod d₂ )
…
x ≡ b_t (mod d_t )

の場合、 d₁, d₂, … d_t が互いに素であれば、

n = d₁ d₂ … d_t

を法として、ただ一つの解がある。
まず、n / d_i = n_i とおけば、 d_i と n_i は互いに素であるから、

n_i x_i ≡ 1 (mod d_i )

の解 x_i を求めることができる。そこで、

x ≡ b₁ n₁ x₁ + b₂ n₂ x₂ + … + b_t n_t x_t (mod n)

とすれば、この x は明らかにもとの合同式をすべて満足する。

このような連立合同式の性質と解法を中国人剰余定理 (Chinese remainder theorem) と呼ぶ。