2014/08/28

中国剰余定理の証明と例題(二元の場合)

分野: 整数問題  レベル: 数学オリンピック

中国剰余定理(二元の場合):
$n_1$ と $n_2$ が互いに素なとき,
$x\equiv a_1 \:\mathrm{mod}\: n_1,$
$x\equiv a_2 \:\mathrm{mod}\: n_2$
を満たす $x$ が $0$ 以上 $n_1n_2$ 未満の範囲に唯1つ存在する。


連立合同式,中国剰余定理の本質的な部分を理解するためにこのページでは二元の場合で $n_1, n_2$ が互いに素な場合のみを考えます。より一般の場合は→中国剰余定理と法が互いに素でない場合への拡張

連立合同式の簡単な例題

合同式の形で書くと一見いかめしいですがここで考えるのは以下のような単純な問題です:

例題

$3$ で割って $2$ 余り,$5$ で割って $4$ 余る $15(=3\times 5)$ 未満の非負整数 $n$ を求めよ。

これくらいの大きさなら全部調べれます,解は $n=14$ のみです。解が存在して,しかもただ1つです。

上記の例題と解答を一般化したのが中国剰余定理(Chinese Remainder Theorem)です。このページでは二元の場合の中国剰余定理を証明するとともに実際に連立合同式の解の求め方を解説します。

中国剰余定理の証明(解の唯一性)

まずは簡単なので唯一性,つまり「解が $2$ つ以上存在することはない」ことを背理法で証明します。

(中国剰余定理の証明:前半)
題意の連立合同式の解が2つあると仮定する。それを $x,y$ とおくと,
$x\equiv a_1\equiv y \:\mathrm{mod}\: n_1\\
x\equiv a_2\equiv y\:\mathrm{mod}\: n_2$
より $x-y$ は $n_1$ の倍数であり $n_2$ の倍数でもある。 $n_1$ と $n_2$ が互いに素なので $x-y$ は $n_1n_2$ の倍数。
ところが $x,y$ はともに $n_1n_2$ 未満の非負整数なので $x=y$ となり矛盾。よって解が存在するとしたら $1$ つ。

中国剰余定理の証明(解の存在性)

次に連立合同式に解が存在することを証明します。

(中国剰余定理の証明:後半)
$n_1, n_2$ は互いに素なので,
$n_1X+n_2Y=1$ を満たす整数 $X,Y$ が存在する(→注)。
よって,$n_2Y\equiv 1\:\mathrm{mod}\: n_1\\n_1X\equiv 1\:\mathrm{mod}\: n_2$
よって,$x’=a_1n_2Y+a_2n_1X$ とおくと
$x’\equiv a_1\:\mathrm{mod}\:n_1\\
x’\equiv a_2\:\mathrm{mod}\:n_2$
となり $x’$は題意の連立合同式を満たす。
$n_1n_2$ 未満の非負整数の解 $x$ を得るためには $x$ を「 $x’$を $n_1n_2$ で割った余り」とすればよい。

注:有名な定理(ベズーの定理)です。一次不定方程式ax+by=cの整数解で詳しく説明しています。ユークリッドの互除法を用いることで $X, Y$ を求めることができるので,解 $x$ を実際に計算することができます!

さっきの例題を実際に解いてみる

例題(再掲):以下の連立合同式を解け。
$x\equiv 2\:\mathrm{mod}\:3,\\x\equiv 4\:\mathrm{mod}\:5$

$3X+5Y=1$ を満たす $X, Y$ を直感またはユークリッドの互除法で求めると例えば $X=2, Y=-1$
よって $x’=2\cdot 5\cdot (-1)+4\cdot 3\cdot 2=14$
となりご所望の解が得られます!

「中国剰余定理」という名前がかっこいいですね
分野: 整数問題  レベル: 数学オリンピック