中国剰余定理

• 中国の剰余定理
• 中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ - Qiita

• $X$ は $D_1$ で割ると $M_1$ 余る
• $X$ は $D_2$ で割ると $M_2$ 余る
• $D_1$ と $D_2$ は互いに素

この時、条件を満たす $X$ は必ず存在し、かつ $X$ を $D_1D_2$ で割った時の余りは一意に決まる。

証明はQiita記事参照。

むかしむかし、あるところにおじいさんがおったそうな。
おじいさんは山へ柴刈りに行くにあたり、薪の在庫を調べたそうな。
3個ずつに分けたところ、2個余ったそうな。
5個ずつに分けたところ、3個余ったそうな。
7個ずつに分けたところ、2個余ったそうな。
はて、薪はいったいいくつあるじゃろうか。

中国の『孫子算経』に伝わる。（設定は後付け）

• 3で割った余りに70をかける。140。
• 5で割った余りに21をかける。63。
• 7で割った余りに15をかける。30。
• これらを全て足し合わせる。233。
• 105で割った余りが答え。23。

70,21,15がどこから出てきたか。これはそれぞれ、以下のようになっている。

• 5と7の公倍数のうち、3で割って1余る数
• 3と7の公倍数のうち、5で割って1余る数
• 3と5の公倍数のうち、7で割って1余る数

たとえば5を中心に見ると、140,63,30のうち、63は問題の条件に合うよう5で割ると3余る数を選んでいて、他の140と30は5の倍数である。 よってそれを足し合わせた数は当然、5で割ると3余る。 3,7に対しても同じことが言える。

こうした数をあらかじめ見つけておけば、他の数で割った場合の答えも求められる。

以下のように問題を拡張する。

• ある数 $X$ は $D_i$ で割ると $M_i$ 余る（$X \equiv M_i \mod{D_i}$）という条件が $N$ 個ある
• 任意の $i,j$ に対して $D_i,D_j$ は互いに素とは限らない
• 全ての条件を満たす最小の正整数 $X$ を求めよ
• 存在しない場合はその旨を報告せよ

ひとまず条件を絞って、全ての $D_i$ が互いに素とする。

中国剰余定理より「$X \equiv M_1 \mod{D_1}$」と「$X \equiv M_2 \mod{D_2}$」から「$X \equiv M_{1,2} \mod{D_1D_2}$」という解が得られる。（具体的な導出方法は下記「2条件の場合の解法」参照。とりあえず得られるということは保証される）

さらにこれを「$X \equiv M_3 \mod{D_3}$」とあわせることで「$X \equiv M_{1,2,3} \mod{D_1D_2D_3}$」という解が得られる。

2条件の場合の解法を連鎖的に適用していくことで、多条件の場合の解も得られる。

拡張ユークリッドの互除法より、$D_1p+D_2q=1$ を満たす整数解 $(p,q)$ は必ず存在し、計算で求められる。（$D_1,D_2$ は互いに素）

すると以下が言える。

• $D_1p+D_2q \equiv D_2q \equiv 1 \mod{D_1}$
• $D_1p+D_2q \equiv D_1p \equiv 1 \mod{D_2}$

$X = M_2D_1p + M_1D_2q$ とすると、以下のようになり、条件を満たす $X$ を構成できる。

• $X \equiv M_1D_2q \equiv M_1 \mod{D_1}$
• $X \equiv M_2D_1p \equiv M_2 \mod{D_2}$

この場合、矛盾のため $X$ が構成できないケースが出てくる。単純な例で言うと、

• $X \equiv 1 \mod{4}$
• $X \equiv 2 \mod{6}$

4で割った余りが1なら奇数のはずなのに、6で割った余りが2だと偶数となり、矛盾する。

解が存在する必要十分条件は、$D_1,D_2$ の最大公約数を $d$ として、「$M_1 \equiv M_2 \mod{d}$」が成立することである。

上の例では、4と6の最大公約数が2だが $1 \not\equiv 2 \mod{2}$ のため、矛盾する。

以降、その条件は満たすとして、具体的な $X$ の構成方法を示す。

拡張ユークリッドの互除法にて $D_1p+D_2q=d$ となる $(p,q)$ を見つける。また、$s=\frac{M_2-M_1}{d}$ なる $s$ を定義する。

すると、$s(D_1p+D_2q) = sD_1p + sD_2q = M_2 - M_1$ となる。

移項すると、$M_1 + sD_1p = M_2 - sD_2q$ となる。これを $X$ と置くことで、

• $X \equiv M_1 + sD_1p \equiv M_1 \mod{D_1}$
• $X \equiv M_2 - sD_2q \equiv M_2 \mod{D_2}$

となり、条件を満たす。

初期値として $D_0=1,M_0=0$ としておくと、最初の2項を特別扱いせずとも、1項目から順にマージしていける。