2014/08/28

中国剰余定理と法が互いに素でない場合への拡張

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

中国剰余定理(一般の場合):
$n_i\: (i=1,2,\cdots, k)$ たちが互いに素なとき,$k$ 本の連立合同式
$x\equiv a_i \:\mathrm{mod}\:n_i$
を満たす $x$ が $0\leq x <n_1n_2\cdots n_k$ の範囲にただ1つ存在する。

中国剰余定理に関する本質的な部分は二元の場合で説明しました。本記事はその発展なので難しいです(が面白いです)。以下では二元の場合の結果と考え方をを用いるので先に二元の場合をしっかり理解しておいてください!→中国剰余定理の証明と例題(二元の場合)

ここではより踏み込んで合同式の数が一般に $k$ 本の場合の中国剰余定理を解説します。
また,$n_i$ たちが互いに素でない場合も考えます。

中国剰余定理(一般の場合)の証明

解の唯一性の証明は二元の場合と全く同じなので省略します。解の存在性は合同式の本数 $k$ に関する帰納法と二元の場合の結果により証明できます。

中国剰余定理の証明

$k=1$ のときに成立するのは自明

$k=t$ のときに中国剰余定理が成立すると仮定すると,$t$ 本の合同式
$x\equiv a_i \:\mathrm{mod}\:n_i\:(i=1,\cdots, t)$
を満たす $x$ の集合は,(うまく $x_0$ が取ってこれて)$ 1$ 本の合同式
$x\equiv x_0\:\mathrm{mod}\:n_1n_2\cdots n_t$
を満たす $x$ の集合と同じ。

よって,今考えたい $t+1$ 本の連立合同式
$x\equiv a_i \:\mathrm{mod}\:n_i\:(i=1,\cdots, t+1)$
は $2$ 本の連立合同式
$x\equiv x_0\:\mathrm{mod}\:n_1n_2\cdots n_t$
$x\equiv a_{t+1}\:\mathrm{mod}\: n_{t+1}$
と同値である。ここで,$n_1n_2\cdots n_t$ と $n_{t+1}$ は互いに素なので二元の場合の結果より,この連立合同式には解 $x$ が $0\leq x <n_1n_2\cdots n_t\cdot n_{t+1}$ の範囲に存在する。

よって $k=t+1$ のときも中国剰余定理が成立するので帰納法により証明完了。

互いに素でないときの連立合同式

次に,二元の場合において $n_1$ と $n_2$ が互いに素でない場合に拡張します。

一般の二元合同式:
$x\equiv a_1 \:\mathrm{mod}\: n_1,\\x\equiv a_2\:\mathrm{mod}\: n_2$
を満たす $x$ が $0\leq x <\mathrm{lcm}(n_1,n_2)$ の範囲に唯1つ存在する。
⇔ $a_1\equiv a_2\:\mathrm{mod}\: \mathrm{gcd}(n_1, n_2)$

  • $\mathrm{lcm}(n_1, n_2)$ は $n_1$ と $n_2$ の最小公倍数,$\mathrm{gcd}(n_1, n_2)$ は $n_1$ と $n_2$ の最大公約数を表します。
  • $n_1$ と $n_2$ が互いに素なときは,$\mathrm{gcd}(n_1,n_2)=1$ となり常に右側の条件が満たされるので二元の場合の中国剰余定理と一致します。

証明の概略

・「⇔の右側が満たされるなら左側も満たされる」ことの証明
解の唯一性は互いに素でない場合と同様。以下,解の存在性を示す。右側の条件と一次不定方程式ax+by=cの整数解(ベズーの定理)より,
$n_1X+n_2Y=a_2-a_1$ を満たす整数 $X, Y$ が存在する(注)。
よって,$x’=n_1X+a_1=a_2-n_2Y$ とおくと $x’$は連立合同式を満たす。最後に $x’$を $\mathrm{lcm}(n_1,n_2)$ で割った余りを $x$ とすれば左側の条件を満たす。

・「⇔の左側が満たされるなら右側も満たされる」ことの証明
連立合同式に解 $x$ が存在するとき,
$x\equiv a_1\:\mathrm{mod}\:n_1$ であり,$n_1$ は $\mathrm{gcd}(n_1,n_2)$ の倍数なので
$x\equiv a_1\:\mathrm{mod}\: \mathrm{gcd}(n_1,n_2)$
同様に $x\equiv a_2\:\mathrm{mod}\: \mathrm{gcd}(n_1,n_2)$
となり右側の条件が満たされる。

注:互いに素でない場合と同様,ユークリッドの互除法を用いて $X,Y$ を求めることができます。

一般の連立合同式

最後に $n_i$ たちが互いに素とは限らない,かつ式の本数が $k$ の場合(上記2つの融合)の結果を述べておきます。

最も一般的な定理:
$k$ 本の連立合同式
$x\equiv a_i \:\mathrm{mod}\: n_i\:(i=1,2,\cdots, k)$
を満たす $x$ が $0\leq x <\mathrm{lcm}(n_1,n_2,\cdots, n_k)$ の範囲にただ1つ存在する。
⇔任意の $i$ と $j$ に対して $a_i\equiv a_j\:\mathrm{mod}\: \mathrm{gcd}(n_i, n_j)$

証明は今までとほとんど同様です。

参考にしたサイト:Chinese Remainder Theorem(英語です)

数オリの問題への応用

1989年国際数学オリンピックドイツ大会第5問です。中国剰余定理を使えば一発です。

問題

任意の自然数 $n$ に対して,「いずれもが素数のべき乗の形でないような連続する $n$ 個の自然数」が存在することを証明せよ。

解答

$2n$ 個の素数 $p_1,\:p_2,\:,\cdots,\:p_{2n}$ を持ってくる。
中国剰余定理より,以下の $n$ 本の連立合同式を満たす $x$ が存在する。
$x\equiv -1\:\mathrm{mod}\: p_1p_2$
$x\equiv -2\:\mathrm{mod}\: p_3p_4$
$\cdots$
$x\equiv -n\:\mathrm{mod}\: p_{2n-1}p_{2n}$
よって,$x+1,\:x+2,\:\cdots,x+n$ はいずれも2つ以上の素因数を持つので題意は示された。

かなり複雑になってしまいましたが,「 $x_i\equiv a_i$ 型の連立合同式は(原理的には)ユークリッドの互除法を使って解が求まる」と覚えておくとよいでしょう

Tag: 国際数学オリンピックの過去問

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