中国剰余定理は
連立一次合同式のおさらい
前回の記事では、連立一次合同式を用いてライバルのテストの点を暴きました。
その概略は、次です。
まず、ライバルのテストの点を３，５，７で割った余りを聞き出します。
例えば、余りがそれぞれ１，２，６だったとすると、
\[ \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. \]
という連立一次合同式が立式されます。
これの具体的な解き方は、２パターンありました。
今回は、簡略バージョンを思い出しておきましょう。
簡略バージョンでは、先ほどの連立一次合同式を、
７０×１＋２１×２＋１５×６＝２０２
$202 \equiv 97 (\mod 105)$
よって$x=97$
という驚くべきスピードで解いてしまいます。
この発想をおさらいします。
$x$は３で割って１余り、５で割って２余り、７で割って６余る数です。
要するに、$x$には青い条件、緑の条件、黄色の条件んが付いています。
ここで、７０は３で割って１余り、かつ５，７で割った余りは０です。
なので、７０は青い条件だけを表し、緑と黄色の条件の邪魔をしません。
同様に、２１は５で割って１余り、３，７で割った余りは０です。
緑の条件は、５で割った余りが２なので、２１は１個ではなく２個必要です。
同様に、黄色の条件は１５×６で表されます。
以上のことから、
７０×１＋２１×２＋１５×６＝２０２
となり、２０２は１００点を超えているので、
１０５（３×５×７）を法として２０２と合同な１００点以下の数を探し、
$202 \equiv 97 (\mod 105)$
からテストの点は９７点という結論を得ます。
問題は、７０，２１，１５という都合のいい数をどうやって見つけるのか、という点です。
７０は３で割ると１あまり、５，７で割ると０余る数です。
$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$
となり、７０が求まります。
のこりの２１と１５も同様です。
結果だけまとめると、
\[ \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$の範囲では９７ただ一つであった。
となります。
これを文字で表して一般化すると次のようになります。
$n_1, n_2, n_3$が、どの２つをとっても互いに素な自然数であるとする。
このとき、任意の整数$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 n_3) \end{array} \right. \]
を満たす整数$x$が$0≦x≦n_1n_2n_3-1$の範囲にただ一つ存在する
この主張を中国剰余定理（文字３つバージョン）というのでした。
さて。
それでは本題。
これを証明していきましょう。
中国剰余定理（式３つバージョン）の証明
中国剰余定理（式３つバージョン）
$n_1, n_2, n_3$が、どの２つをとっても互いに素な自然数であるとする。
このとき、任意の整数$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 n_3) \end{array} \right. \]
を満たす整数$x$が$0≦x≦n_1n_2n_3-1$の範囲にただ一つ存在する
～脳内会議～
まずは、ライバルのテストの点を暴いた際の
７０，２１，１５に相当する数を見つけなければなりません。
７０に相当する数は、
$n_1$で割った余りが$a_1$で、かつ$n_2, n_3$でわった余りが０なので、
$n_2×n_3u\equiv a_1(\mod n_1)$
を満たす$u$です。
これの解の存在が保証できれば、
あとは
７０×１＋２１×２＋１５×６
に相当する式を立式して終了です。
（証明）
\[ \left\{ \begin{array}{ll} x\equiv a_1 && (\mod n_1) \\ x\equiv a_2 && (\mod n_1) \\ x\equiv a_3 && (\mod n_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 n_3) \end{array} \right. \]
について、
$n_1$で割った余りが$a_1$で、$n_2, n_3$で割った余りが０である数$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$はどの２つをとっても互いに素であるので、
$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$で割った余りが０となる。
同様にして、
$n_2$で割った余りが$1$で、$n_3, n_1$で割った余りが０となる数を
$n_3n_1u_2$とし、
$n_3$で割った余りが$1$で、$n_1, n_2$で割った余りが０となる数を
$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 n_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 n_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 n_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$
に２つあると仮定し、それを$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 n_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$が、どの２つをとっても互いに素な自然数であるとする。
このとき、任意の整数$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 n_k) \end{array} \right. \]
を満たす整数$x$が$0≦x≦n_1n_2n_3\cdots n_k-1$の範囲にただ一つ存在する
文字と式が増えただけで、証明の本質は式３つバージョンと同じなので、
忙しい方は読み飛ばして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$はどの２つをとっても互いに素であるので、
$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 n_3) \\ \vdots&&\\ x\equiv a_k && (\mod n_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 n_3) \\ \vdots&&\\ x\equiv a_k && (\mod n_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 n_3) \\ \vdots&&\\ x\equiv a_k && (\mod n_k) \end{array} \right. \]
と
$0≦x≦n_1n_2n_3\cdots n_k-1$
を満たす$x$の存在が示される。
次に、このような$x$がただ一つであることを示す。
$0≦x≦N-1$の範囲にこのような$x$が２つ存在すると仮定し、
$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 n_3) \\ \vdots&&\\ x\equiv a_k && (\mod n_k) \end{array} \right. \]
と
$0≦x≦n_1n_2n_3\cdots ×n_k-1$
を満たす$x$がただ一つ存在することが示された
（証明終了）
まとめ
いかがでしたか。
・中国剰余定理（式３つバージョン）の証明
・中国剰余定理（式n個バージョン）の証明
を押さえていただれればと思います。
中国剰余定理はあまりに関する定理です。
複数の文字で割った余りを考察する際にとても便利で、
オイラー関数という大変興味深い数学概念の定理の証明で活躍します。
ではまた次回の記事でお会いしましょう！
コメント