中国剰余定理

定義

  • $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条件の場合の解法を連鎖的に適用していくことで、多条件の場合の解も得られる。

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項目から順にマージしていける。

このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/number_theory/chinese_remainder_theorem.txt · 最終更新: 2019/12/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0