この時、条件を満たす $X$ は必ず存在し、かつ $X$ を $D_1D_2$ で割った時の余りは一意に決まる。
証明はQiita記事参照。
むかしむかし、あるところにおじいさんがおったそうな。
おじいさんは山へ柴刈りに行くにあたり、薪の在庫を調べたそうな。
3個ずつに分けたところ、2個余ったそうな。
5個ずつに分けたところ、3個余ったそうな。
7個ずつに分けたところ、2個余ったそうな。
はて、薪はいったいいくつあるじゃろうか。
中国の『孫子算経』に伝わる。（設定は後付け）
70,21,15がどこから出てきたか。これはそれぞれ、以下のようになっている。
たとえば5を中心に見ると、140,63,30のうち、63は問題の条件に合うよう5で割ると3余る数を選んでいて、他の140と30は5の倍数である。 よってそれを足し合わせた数は当然、5で割ると3余る。 3,7に対しても同じことが言える。
こうした数をあらかじめ見つけておけば、他の数で割った場合の答えも求められる。
以下のように問題を拡張する。
ひとまず条件を絞って、全ての $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$ は互いに素）
すると以下が言える。
$X = M_2D_1p + M_1D_2q$ とすると、以下のようになり、条件を満たす $X$ を構成できる。
この場合、矛盾のため $X$ が構成できないケースが出てくる。単純な例で言うと、
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$ と置くことで、
となり、条件を満たす。
初期値として $D_0=1,M_0=0$ としておくと、最初の2項を特別扱いせずとも、1項目から順にマージしていける。