中国剰余定理を具体例とともに分かりやすく証明

中国剰余定理

中国剰余定理は

目次

連立一次合同式のおさらい

前回の記事では、連立一次合同式を用いてライバルのテストの点を暴きました。

その概略は、次です。

まず、ライバルのテストの点を3,5,7で割った余りを聞き出します。

例えば、余りがそれぞれ1,2,6だったとすると、

\[ \left\{ \begin{array}{ll} x\equiv 1 && (\mod 3) \cdots ①\\ x\equiv 2 && (\mod 5)\cdots ② \\ x\equiv 6 && (\mod 7) \cdots ③ \end{array} \right. \]

という連立一次合同式が立式されます。

これの具体的な解き方は、2パターンありました。

今回は、簡略バージョンを思い出しておきましょう。

簡略バージョンでは、先ほどの連立一次合同式を、

70×1+21×2+15×6=202

$202 \equiv 97 (\mod 105)$

よって$x=97$

という驚くべきスピードで解いてしまいます。

この発想をおさらいします。

$x$は3で割って1余り5で割って2余り7で割って6余る数です

要するに、$x$には青い条件、緑の条件、黄色の条件んが付いています。

ここで、70は3で割って1余り、かつ5,7で割った余りは0です。

なので、70は青い条件だけを表し、緑と黄色の条件の邪魔をしません。

同様に、21は5で割って1余り、3,7で割った余りは0です。

緑の条件は、5で割った余りが2なので、21は1個ではなく2個必要です。

同様に、黄色の条件は15×6で表されます。

以上のことから、

70×121×215×6=202

となり、202は100点を超えているので、

105(3×5×7)を法として202と合同な100点以下の数を探し、

$202 \equiv 97 (\mod 105)$

からテストの点は97点という結論を得ます。

問題は、70,21,15という都合のいい数をどうやって見つけるのか、という点です。

70は3で割ると1あまり、5,7で割ると0余る数です。

$5×7x\equiv 1(\mod3)$

を解いて$x$を求めると、

$5×7x$がこの条件を満たすことが分かると思います。

したがって、

$5×7x-1=3k$ $(kは整数)$

となり、一次不定方程式

$5×7x-3k=1$

を解けばよいことになります。

$5×7$と$3$は互いに素なので、

この一次不定方程式は解くことができ、

例えば$x=2, k=23$とすると

$5×7x=5×7×2=70$

となり、70が求まります。

のこりの21と15も同様です。

結果だけまとめると、

\[ \left\{ \begin{array}{ll} x\equiv 1 && (\mod 3) \cdots ①\\ x\equiv 2 && (\mod 5)\cdots ② \\ x\equiv 6 && (\mod 7) \cdots ③ \end{array} \right. \]

を満たす整数$x$が存在し、$0≦x≦105-1$の範囲では97ただ一つであった。

となります。

これを文字で表して一般化すると次のようになります。

$n_1, n_2, n_3$が、どの2つをとっても互いに素な自然数であるとする。

このとき、任意の整数$a_1, a_2, a_3$に対して、

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \end{array} \right. \]

を満たす整数$x$が$0≦x≦n_1n_2n_3-1$の範囲にただ一つ存在する

この主張を中国剰余定理(文字3つバージョン)というのでした。

さて。

それでは本題。

これを証明していきましょう。

中国剰余定理(式3つバージョン)の証明

中国剰余定理(式3つバージョン)

$n_1, n_2, n_3$が、どの2つをとっても互いに素な自然数であるとする。

このとき、任意の整数$a_1, a_2, a_3$に対して、

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \end{array} \right. \]

を満たす整数$x$が$0≦x≦n_1n_2n_3-1$の範囲にただ一つ存在する

~脳内会議~

まずは、ライバルのテストの点を暴いた際の

70,21,15に相当する数を見つけなければなりません。

70に相当する数は、

$n_1$で割った余りが$a_1$で、かつ$n_2, n_3$でわった余りが0なので、

$n_2×n_3u\equiv a_1(\mod n_1)$

を満たす$u$です。

これの解の存在が保証できれば、

あとは

70×1+21×2+15×6

に相当する式を立式して終了です。

(証明)

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \end{array} \right. \]

を満たす整数$x$が存在することと、

$0≦x≦n_1n_2n_3-1$にそのような$x$はただ一つであることを示せばよい。

まず解の存在を示す。

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \end{array} \right. \]

について、

$n_1$で割った余りが$a_1$で、$n_2, n_3$で割った余りが0である数$u_1$を考える。

$n_2×n_3u\equiv 1 (\mod n_1)$

を考える。

$n_2n_3u-1=n_1p$ ($p$は整数)

である。

整理すると、

$n_2n_3u-n_1p=1$

となる。

条件より、

$n_2, n_3, n_1$はどの2つをとっても互いに素であるので、

$n_2n_3$と$n_1$は互いに素である。

よって、一次不定方程式

$n_2n_3u-n_1p=1$

は解を持ち、それを$u=u_1m p=p_1$と置く。

すると、

$n_2n_3u_1$は$n_1$で割った余りが$1$で、$n_2, n_3$で割った余りが0となる。

同様にして、

$n_2$で割った余りが$1$で、$n_3, n_1$で割った余りが0となる数を

$n_3n_1u_2$とし、

$n_3$で割った余りが$1$で、$n_1, n_2$で割った余りが0となる数を

$n_1n_2u_3$とする。

ここで、

$x_0=(n_2n_3u_1)a_1+(n_3n_1u_2)a_2+(n_1n_2u_3)a_3$

と定めると、$u_1, u_2, u_3$の定義から、

$x_0\equiv a_1(\mod n_1)$かつ

$x_0\equiv a_2(\mod n_2)$かつ

$x_0\equiv a_3(\mod n_3)$が成り立つので、

$x=x_0$とすれば、

連立一次合同式

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \end{array} \right. \]

の解の存在が示される。

さらに、$x_0$を$n_1n_2n_3$で割った余りも

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \end{array} \right. \]

を満たすので、これを$x=x_1$とすると、

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \end{array} \right. \]

と$0≦x≦n_1n_2n_3-1$を満たす整数の存在が示された。

次に、このような数が$0≦x≦n_1n_2n_3-1$

にただ一つであることを示す。

このような数が$0≦x≦n_1n_2n_3-1$

に2つあると仮定し、それを$x_2, x_3 $ $x_2<x_3$をする。

連立合同式の条件から、

$x_3\equiv x_2\equiv a_1 (\mod n_1)$

$x_3\equiv x_2 \equiv a_2(\mod n_2)$

$x_3\equiv x_2 \equiv a_3(\mod n_3)$

である。

よって、

$x_3-x_2$は$n_1$の倍数かつ$n_2$の倍数かつ$n_3$の倍数である。

したがって、

$x_3-x_3$は$n_1n_2n_3$の倍数でなければならない。

しかし、

$0≦x_2<x_2≦n_1n_2n_3-1$

であり、

$0<x_3-x_2<n_1n_2n_3$

であるが、この範囲に$n_1n_2n_3$の倍数は存在しないので矛盾

よって、

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \end{array} \right. \]

$0≦x≦n_1n_2n_3-1$

を満たす整数$x$がただ一つ存在することが示された。

(証明終了)

$u_1, u_2, u_3$の存在を示し、

$x_0=(n_2n_3u_1)a_1+(n_3n_1u_2)a_2+(n_1n_2u_3)a_3$

と定めるところが証明の本質です。

ここから先は完全におまけですが、

実は中国剰余定理は式$k$個バージョンまで一般化できますので、

次の見出しでそれを証明しようと思います。

中国剰余定理(式$k$個バージョン)

(定理)

$n_1, n_2, n_3, \cdots, n_k$が、どの2つをとっても互いに素な自然数であるとする。

このとき、任意の整数$a_1, a_2, a_3, \cdots, a_k$に対して、

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \\ \vdots&&\\ x\equiv a_k && (\mod a_k) \end{array} \right. \]

を満たす整数$x$が$0≦x≦n_1n_2n_3\cdots n_k-1$の範囲にただ一つ存在する

文字と式が増えただけで、証明の本質は式3つバージョンと同じなので、

忙しい方は読み飛ばしてOKです。

(証明)

$N=n_1×n_2×\cdots ×n_k$と置く。

また、$N_i=\dfrac{N}{n_i}$ $i=1, 2, \cdots, k$と置く。

このとき、

$N_iu\equiv 1(\mod n_i)$

を考える。

$N_iu-1=n_ip$ $p$は整数

である。

整理すると

$n_1u-n_ip=1$

である。

$n_1, n_2, \cdots, n_k$はどの2つをとっても互いに素であるので、

$N_i$と$n_i$は互いに素である。

したがって、

一次不定方程式$n_1u-n_ip=1$は解を持つことが示される。

この解を$u=u_i, p=p_i$

と置く。

このとき、

$x_0=(N_1u_1)a_1+(N_2u_2)a_2+\cdots +(N_ku_k)a_k$

と置く。

すると、$x=x_0$とすれば

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \\ \vdots&&\\ x\equiv a_k && (\mod a_k) \end{array} \right. \]

に解が存在することが確認される。

さらに、$x_0$を$N$で割った余りも

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \\ \vdots&&\\ x\equiv a_k && (\mod a_k) \end{array} \right. \]

を満たすので、これを$x=x_1$とすると、

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \\ \vdots&&\\ x\equiv a_k && (\mod a_k) \end{array} \right. \]

$0≦x≦n_1n_2n_3\cdots n_k-1$

を満たす$x$の存在が示される。

次に、このような$x$がただ一つであることを示す。

$0≦x≦N-1$の範囲にこのような$x$が2つ存在すると仮定し、

$x_2, x_3$と置く。 $x_3>x_2$

定義より、

$x_3\equiv x_2 \equiv a_i (\mod n_1)$ $i=1, 2, 3, \cdots, k$

であるので、

$x_3-x_2$は$n_1×n_2×\cdots n_k$の倍数である。

しかし、

$0≦x_2<x_3≦n_1×n_2×\cdots ×n_k-1$

であり、

$0<x_3-x_2<n_1×n_2×\cdots ×n_k$

でなければならない。

しかしこの範囲に$n_1×n_2×\cdots ×n_k-1$の倍数は存在しないので、これは矛盾

よって、

\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod a_3) \\ \vdots&&\\ x\equiv a_k && (\mod a_k) \end{array} \right. \]

$0≦x≦n_1n_2n_3\cdots ×n_k-1$

を満たす$x$がただ一つ存在することが示された

(証明終了)

まとめ

いかがでしたか。

・中国剰余定理(式3つバージョン)の証明

・中国剰余定理(式n個バージョン)の証明

を押さえていただれればと思います。

中国剰余定理はあまりに関する定理です。

複数の文字で割った余りを考察する際にとても便利で、

オイラー関数という大変興味深い数学概念の定理の証明で活躍します。

ではまた次回の記事でお会いしましょう!

ブログランキング参加してます

よかったらシェアしてね!
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

CAPTCHA


目次