中国剰余定理…その先にあるもの！！ - ラスクのMathematics for Everyone！

こんにちは、ラスクです。

春は常に眠くて大変です…
でも数学をしていて、何かひらめいたときはハッと目が覚めますよね。
そんなときは眠かったのも忘れて必死に計算してしまいます。
まぁ単なる勘違いなことも多いのですが…

さて、今回は前回お話しした中国剰余定理をもう少し一般的に考えてみようという試みです。
一応、専門的な記事とみなしますが前回の記事(と合同式の知識)があれば無理なく読めると思うので、まだの方はぜひこちらを先にお読みください！
mathforeveryone.hatenablog.com

また、前回と今回の記事で私が伝えたいことを最後に書いたので、そこだけでも読んでくれたらうれしいです！！

復習とちょっとだけ一般化
- 前回の復習
- n個に一般化
剰余環を使った表現
- 剰余環の導入
- 定理の書き換え
まだまだこんなもんじゃない
最後に

復習とちょっとだけ一般化

前回の復習

では初めに前回やったことを思い出しておきましょう。
前回は次のような問題について考えていました。

$p_1$ で割って $r_1$ 余り、 $p_2$ で割って $r_2$ 余るような整数がどのようなときに存在するか

そして、最終的な結論として

定理
$p_1$ と $p_2$ が互いに素であれば、任意の余りの組み合わせ $r_1,r_2$ に対して上のような整数が( $1$ から $p_1$ と $p_2$ の最小公倍数 $L$ の中にただ一つ)存在する

という事が得られ、これを中国剰余定理と呼んだのでした。

前回書いた表をもう一度載せておきます。

f:id:rusk_mathematics:20190415001759p:plain

思い出していただけましたでしょうか？

n個に一般化

では少し一般化していきます。ここからは、さすがに記述が面倒なのでここからは合同式をバンバン使っていきます！まだ合同式に慣れてない方でも難しいことはないので、ゆっくり調べながらお読みください。

ということで、次の問題を考えます。

整数 $0\le r_1\lt p_1,0\le r_2\lt p_2\ldots ,0\le r_n\lt p_n$ に対して、
\begin{align}
\begin{cases}
x&\equiv r_1 \pmod{p_1}\\
x&\equiv r_2 \pmod{p_2}\\
&\vdots\\
x&\equiv r_n \pmod{p_n}\\
\end{cases}\tag{1}
\end{align}
を満たすような整数 $x$ はどのようなときに存在するか。

いやー合同式を使うとすっきりしますね(笑)
内容としては先ほど $2$ 個で考えていたものを単に $n$ 個に増やしただけですね？
この場合でも"ほぼ"同じ結論が得られます。

定理
（整数 $p_1,p_2,\ldots,p_n$ の最小公倍数を $L$ としておく。)
$p_1,p_2,\ldots,p_n$ がどの二つもそれぞれ互いに素であれば、任意の $0\le r_1\lt p_1,0\le r_2\lt p_2,\ldots,0\le r_n \lt p_n$ に対して（1）を満たすような整数 $x$ が( $1$ から $L$ の中にただ一つ)存在する。

この定理も少し一般化されていますが中国剰余定理と呼びます。
これが成り立つ理由は前回説明したこととほぼ同じなので簡単に済ませますが、一つだけ注意しなければならないのは赤字て書いた部分です。この部分を

$p_1,p_2,\ldots,p_n$ が互いに素ならば…

という文章に変えてしまうと、定理が成り立たなくなってしまいます。なぜでしょうか。

そもそも中国剰余定理の成り立つ理由の本質は

$p_1,p_2,\ldots,p_n$ の最小公倍数 $L=$ 余りの組み合わせの数 $p_1\times p_2\times\ldots\times p_n$

という関係式が成り立つことでした。
ここで例えば、 $p_1=3,p_2=5,p_3=6$ として考えてみると確かにこの3つは全体としては公約数を持たず、互いに素ですが、その最小公倍数 $L=30$ となってしまいます。すると、
$L\lt 3\times5\times 6=90$
となってしまい余りの組み合わせ数に対して $1$ から $L$ までの数が足りなくなってしまうのです。

これに対し
$p_1,p_2,\ldots,p_n$ のどの二つも互いに素であれば
$L=p_1\times p_2\times\ldots\times p_n$
となるので無事に余りの組み合わせ数と $L$ が一致します。

ということで、複数個の場合はそれぞれが互いに素であることが重要という事です。

以上で、中国剰余定理は $n$ 個の組み合わせに拡張できることの説明を終わります。

剰余環を使った表現

ではここからは、これまでの話を少し高級な道具を使って表現してみましょう！
これ以降に話すことはかなり厳密性に欠けるので、いろいろな方からおしかりを受けそうですが(笑)概要を抑えるという意味では問題ないはずなのでお許しください*1

剰余環の導入

まず、整数全体のことを $\mathbb{Z}$ と書きます。これは覚えておいてください。また、この整数全体 $\mathbb{Z}$ を正の整数 $p$ で割った余りでグループ分けしたものを $\mathbb{Z}/p\mathbb{Z}$ と書きます。
今、 $\mathbb{Z}/p\mathbb{Z}$ の中身は次のように書けます。
$\displaystyle\mathbb{Z}/p\mathbb{Z}=\{\bar{0},\bar{1},\ldots,\overline{p-1}\}$
ここで $\bar{a}$ というのは $p$ で割って $a$ 余るような整数全体を表しています。なので、 $p=5$ として具体的に表すと

\begin{align}
\bar{0}&=\{\ldots,-5,0,5,10\ldots\}\\
\bar{1}&=\{\ldots,-4,1,6,11,\ldots\}\\
\vdots\\
\bar{4}&=\{\ldots,-1,4,9,14,\ldots\}\\
\end{align}

となっています。
このとき、 $1$ と $6$ は同じグループに入りますから $\bar{1}$ のことを $\bar{6}$ と書いてもよいです。この上についている横線の意味は、「この数字の入っているグループだよ～」という事なのです。なので極端なことを言えば $\bar{4}$ のことを $\overline{2019}$ と書いてもOKです。*2

さらにこの $\mathbb{Z}/p\mathbb{Z}$ に対して演算（足し算と掛け算）を定義します。

あまり大学以降の数学に慣れていない方はギョッとするかもしれませんが、数学では、ある集合上に新たな演算を定義することがよくあります。
そうです！演算というのはもともとあるものではなく、定義をするものなのです！！！
そう思うと、数学というのがとても多様なものであると感じられるのではないでしょうか？

はい。それはさておき(笑)話を続けます。
演算を定義するといっても難しいことはありません。 $\mathbb{Z}/p\mathbb{Z}$ の要素は $\bar{a}$ や $\bar{b}$ とあらわされていましたから、この二つの足し算や掛け算を
\begin{align}
\bar{a}+\bar{b}&:=\overline{a+b}\\
\bar{a}\times\bar{b}&:=\overline{a\times b}
\end{align}
とすればいいのです。…何を言っているかお分かりになるでしょうか？

$p=5$ として、具体的に見ましょう。
$\mathbb{Z}/5\mathbb{Z}$ の要素として今、 $\bar{2}$ と $\bar{3}$ を考えます。この二つの足し算は
$\displaystyle\bar{2}+\bar{3}=\bar{5}$
となります。これに間違いはありませんが、 $\bar{5}=\bar{0}$ でしたから
$\displaystyle\bar{2}+\bar{3}=\bar{0}$
と書くこともできます。同じように掛け算は
$\displaystyle\bar{2}\times\bar{3}=\bar{6}=\bar{1}$
となります。
つまり、この世界での演算は、普通に足し算や掛け算をした後に $p=5$ で割った余りを考えればよいという事になります。

はい。これでめでたく演算が定義されたと思いきや、まだ問題があります。
なぜなら今、 $\bar{2}$ という要素は $\bar{7}$ と書くこともできました。なので
\begin{align}
\bar{2}+\bar{3}と\bar{7}+\bar{3}
\end{align}
という二つの計算結果は同じにならないといけないわけです。（ $\bar{2}$ と $\bar{7}$ というのは見た目こそ違えどまったく同じものをあらわしている！）
幸い今はどちらも $\bar{0}$ になってくれていますが、上のようなことをすべての場合で考え、きちんと整合性が取れていないと演算が定義されたとは言えません。
証明はしませんが、今の場合は足し算も掛け算も最終的にはきちんと定義できているのでご安心ください。このようなことが確かめられ、きちんと定義されていることを専門的にはwell-definedであるといいます。これは数学科に入学した大学生を最初に(？)苦しめる概念なのですが要は非の打ちどころがなく定義されているという事です。

ということで、長々と書きましたが $\mathbb{Z}/p\mathbb{Z}$ に無事、演算が定義されました！！
この演算が定義された $\mathbb{Z}/p\mathbb{Z}$ のことを $\mathbb{Z}$ の剰余環という風に呼びます。

定理の書き換え

では、剰余環を使って中国剰余定理を記述してみましょう。結論としては次のようになります。

定理
$p_1,p_2,\ldots,p_n$ をどの二つも互いに素な正の整数とし、 $L=p_1p_2\ldots p_n$ とする。
このとき
$\displaystyle\mathbb{Z}/L\mathbb{Z}\simeq\mathbb{Z}/p_1\times\mathbb{Z}/p_2\mathbb{Z}\times\ldots\times\mathbb{Z}/p_n\mathbb{Z}$
が成り立つ。

この意味を読み解いていきましょう。
まあ、とはいっても前半はいいですね。

$\mathbb{Z}/p_1\times\mathbb{Z}/p_2\mathbb{Z}\times\ldots\times\mathbb{Z}/p_n\mathbb{Z}$
というのは直積といって、それぞれの要素の組を表しています。
今それぞれは各 $p_i(i=1,\ldots,n)$ で割った余りを考えていますから、まさに今まで考えていた余りの組み合わせを表しています！

例
$p_1=3.p_2=5,p_3=8$ だとすれば、
$(\bar{1},\bar{3},\bar{5})$ や $(\bar{0},\bar{2},\bar{2})$ などがそれにあたります。
今まではこれを $r_1,r_2,r_3$ などとしていました。
この $p_1,p_2,p_3$ についてはこの先も多用していきます。

また、この後半の数式に出てくる $\simeq$ という記号は二つのものが同型であるという事を表していて、意味はざっくりいうと左辺と右辺が演算を保ったまま一対一に対応している、ということです。

対応のさせ方は以下の通りです。
$\mathbb{Z}/L\mathbb{Z}=\{\bar{0},\ldots.\overline{L-1}\}$
とあらわされていました。
この $\bar{a}$ という要素の行き先を $a$ を各 $p_i(i=1,\ldots,n)$ で割った余りとして定義します*3。この対応を $f(\bar{a})=(r_1,r_2,\ldots,r_n)$ と書きましょう。

例
先の $p_1,p_2,p_3$ では $L=120$ ですが、例えば
$f(\overline{37})=(\bar{1},\bar{2},\bar{5})$ となり、
$f(\overline{56})=(\bar{2},\bar{1},\bar{0})$ となります。

つまり平たく言えば、 $0$ から $L-1$ の数を各 $p_i$ で割った余りを並べて書いてだけです。

そして最後に演算を保つという意味ですが、これは
$f(\bar{a}+\bar{b})=f(\bar{a})+f(\bar{b})$
と
$f(\bar{a}\times\bar{b})=f(\bar{a})\times f(\bar{b})$
が成り立つという事。つまり、先に演算してから $f$ で送っても、 $f$ で送ってから演算しても同じ結果になるという事です*4。

例
これも先程までの $p_1,p_2,p_3$ において
\begin{align}
f(\overline{37}+\overline{56})=f(\overline{93})=(\bar{0},\bar{3},\bar{5})=(\bar{1},\bar{2},\bar{5})+(\bar{2},\bar{1},\bar{0})=f(\overline{37})+f(\overline{56})\\
f(\overline{37}\times\overline{56})=f(\overline{32})=(\bar{2},\bar{2},\bar{0})=(\bar{1},\bar{2},\bar{5})\times(\bar{2},\bar{1},\bar{0})=f(\overline{37})+f(\overline{56})\\
\end{align}
と確かに成り立っています。このあたりの計算は剰余環や $f$ という対応の理解を試すいい練習になるので是非自分で数字を決めて試してみてください。

ということで、各部分の説明が終わりました。
まとめると
$\mathbb{Z}/L\mathbb{Z}$ と $\mathbb{Z}/p_1\times\mathbb{Z}/p_2\mathbb{Z}\times\ldots\times\mathbb{Z}/p_n\mathbb{Z}$ はそれぞれの余りを考える $f$ という対応によって、演算を保ちながら一対一に対応する。
という事になります。

さて、このことがきちんといままで考えていた中国剰余定理と一致していることは理解できていますか？
キーポイントは一対一に対応するという事です。
まず、対応が一対一という事から、ことなる $\mathbb{Z}/L\mathbb{Z}$ の要素が $f$ によって同じ要素に送られることはありません。このことは $0$ から $L-1$ までの数が同じ余りの組み合わせを実現することはない、という事に対応しています。

つぎに、全ての $\mathbb{Z}/p_1\times\mathbb{Z}/p_2\mathbb{Z}\times\ldots\times\mathbb{Z}/p_n\mathbb{Z}$ の要素はある $\mathbb{Z}/L\mathbb{Z}$ の行き先になるという事は、まさに前回から考えていた
\begin{align}
\begin{cases}
x&\equiv r_1 \pmod{p_1}\\
x&\equiv r_2 \pmod{p_2}\\
&\vdots\\
x&\equiv r_n \pmod{p_n}\\
\end{cases}\tag{1}
\end{align}
という整数 $x$ が存在する、という事に対応しているわけです。

さらに今回は存在性だけではなく、演算もセットで考えたので、前回の中国剰余定理よりも少しパワーアップしています。
演算を保つというのは同型である、という事に関してなくてはならない性質なのです。
でないと、個数が等しければなんでも同型になってしまいます…

ということで、文章で長ったらしく書かれた中国剰余定理は
$\displaystyle\mathbb{Z}/L\mathbb{Z}\simeq\mathbb{Z}/p_1\times\mathbb{Z}/p_2\mathbb{Z}\times\ldots\times\mathbb{Z}/p_n\mathbb{Z}$
という一本の数式にまとめることが出来ました！
とてもかっこいい式ですよね！！！！

まだまだこんなもんじゃない

今回は中国剰余定理を $n$ 個バージョンに一般化した後、それを剰余環という概念を用いてまとめていきました。
そのおかげで、とてもすっきりとしたものになったと思います。

でも
剰余環を導入した理由はそれだけではありません。
実はこの中国剰余定理、ほかにもいろいろな所で成り立つのです！

高校生で"余り"というものを考える概念は整数ともう一つあります。そう！多項式です！！
多項式バージョンの中国剰余定理を書くと次のようになります。

定理
$\mathbb{R}[x]$ を実数係数の多項式全体とする(本当は実数である必要はない)。
また $P_1,P_2,\ldots,P_n$ をどの二つも互いに素な多項式とし、 $L=P_1P_2\ldots P_n$ とする。
このとき
$\mathbb{R}[x]/L\mathbb{R}[x]\simeq\mathbb{R}[x]/P_1\mathbb{R}[x]\times\ldots\times\mathbb{R}[x]/P_n\mathbb{R}[x]$
が成り立つ。

これについて説明していると、記事の分量が2倍になってしまうので止めますが(笑)、ともかく多項式でも全く同様の定理が成り立つという事です。

実は整数と多項式というのは非常に性質が似ているものなのです。そんな風には見えませんよね。

そして、少し乱暴ですが、このようなものを（とても）抽象化したものが環という概念になります。
中国剰余定理は一般の環に対して成り立つということがわかっています。

最後に

前回以上に長くなってきているのでそろそろ終わりたいと思います(笑)

前回と今回の記事では中国剰余定理についてお話ししましたが、その中で私が伝えたいことは、
大学の授業で習うような一見複雑そうに見える概念も実はとてもシンプルで自然なものであることが多い
という事です。

思い出してみると、このテーマの導入は麻布中学の入試問題でした。そしてそれは決して難しいものではなく、誰もが理解できるようなシンプルなものです。
そのような問題をどんどん一般化するにつれて、剰余やwell-defined、同型、直積などの概念が現れ、最後には（少し無理矢理でしたが）環というものにまで触れることが出来ました。

そしてそこまでのステップは、どれもそこまでぶっ飛んだ発想ではなかったと思います。
大学の数学科で習うような概念はどれも抽象的なものばかりです。
でも、そのどれもが必要であるがゆえに生み出されたのです！！

ですから、複雑そうに見えてもすぐに諦めず、どんどん手を動かしてみてください。
きっと色々なものが自然に頭に入ってくるはずです！！

なにやら説教くさくなってしまいましたが(笑)、このブログではこれからも、できるだけ取っ掛かりは簡単に、大学レベルの数学に触れていこうと思います！！

コメントはどんなものでも絶賛受け付け中です！
気に入ってくださった方は「読者になる」ボタンやTwitterフォローもポチッとお願いします！

それではまた次回お会いいたしましょう！

f:id:rusk_mathematics:20190424033102p:plain