中国人剰余定理の抽象#1
中国人剰余定理の抽象
The Chinese remainder theorem
代数学はよく抽象代数学とよばれる。
つぎのような連立方程式がある。
$${x\equiv 8\left( \bmod \,11 \right)}$$$${x\equiv 3\left( \bmod 17 \right)}$$
最初の式から
$${x=8+11y}$$
となる整数$${y}$$をとって2番目の式にいれると
$${11y\equiv 3-8\equiv 12\left( \bmod 17 \right)}$$
をえる。 $${17}$$ と$${11}$$はたがいに素であるから
割り算ができて$${y=14}$$ をえる。
そして、$${x=8+11y=173}$$をえる。
この$${173}$$は (mod 187)において一意の解になっている。
これはThe Chinese remainder theorem
中国人剰余定理ver.1の応用で、
古代中国の孫子算経という書物（Ad300年ごろ）
に記されたvol3, 問題２０
「３でわると２あまり５でわると３あまり、
７でわると２あまる。そのような数はいかに？」
に由来がある。
定理（中国人剰余定理ver.1）
$${{{m}_{1}},{{m}_{2}}\in \mathbb{Z}\backslash \left\{ 0 \right\}}$$ で$${\gcd \left( {{m}_{1}},{{m}_{2}} \right)=1}$$ とする。このとき$${{{c}_{1}},{{c}_{2}}\in \mathbb{Z}}$$にたいして
(a)$${x\equiv {{c}_{1}}\left( \bmod {{m}_{1}} \right)}$$ ,$${x\equiv {{c}_{2}}\left( \bmod {{m}_{2}} \right)}$$
をみたす解$${x\in \mathbb{Z}}$$が存在する。
(b) $${x,x'}$$を(a)の２つの解とすれば
$${x\equiv x'\bmod \left( {{m}_{1}}{{m}_{2}} \right)}$$
がなりたつ
(a)の証明：
$${x\equiv {{c}_{1}}\left( \bmod {{m}_{1}} \right)}$$より$${x={{c}_{1}}+{{m}_{1}}y}$$ となる$${y\in \mathbb{Z}}$$ がある。
$${x\equiv {{c}_{2}}\left( \bmod {{m}_{2}} \right)}$$であるから
$${{{m}_{1}}y\equiv {{c}_{2}}-{{c}_{1}}\left( \bmod {{m}_{2}} \right)}$$をえるが、
$${\gcd \left( {{m}_{1}},{{m}_{2}} \right)=1}$$より $${{{m}_{1}}}$$でわることができる。
（Remember：$${ax\equiv b\left( \bmod m \right)}$$ は $${\gcd \left( a,m \right)=1}$$のとき$${{{a}^{-1}}}$$が存在し解$${x}$$をもつ）
(b) の証明：
$${x-x'\equiv {{c}_{1}}-{{c}_{1}}\equiv 0\left( \bmod {{m}_{1}} \right)}$$ ,
$${x-x'\equiv {{c}_{2}}-{{c}_{2}}\equiv 0\left( \bmod {{m}_{2}} \right)}$$
より
$${{{m}_{1}}\left| x-x' \right.}$$ ,$${{{m}_{2}}\left| x-x' \right.}$$
$${\gcd \left( {{m}_{1}},{{m}_{2}} \right)=1}$$より
$${{{m}_{1}}{{m}_{2}}\left| x-x' \right.}$$
すなわち、
$${x\equiv x'\bmod \left( {{m}_{1}}{{m}_{2}} \right)}$$
$${\gcd \left( {{m}_{1}},{{m}_{2}} \right)=1}$$のとき
$${\phi :\mathbb{Z}/{{m}_{1}}{{m}_{2}}\mathbb{Z}\to \mathbb{Z}/{{m}_{1}}\mathbb{Z}\times \mathbb{Z}/{{m}_{2}}\mathbb{Z}}$$
という写像を
$${\phi \left( a\bmod {{m}_{1}}{{m}_{2}} \right)=\left( a\bmod {{m}_{1}},a\bmod {{m}_{2}} \right)}$$
であたえる。このとき、$${\phi }$$は環同型
ring isomorphism となる。
これが、中国人剰余定理ver.1の意味するところである。
一般化：
補題：$${R}$$ を可換環とする。
$${a,b\in R}$$にたいして$${aR+bR=R}$$
をみたすを仮定する。このとき、
$${\phi :R/abR\to R/aR\times R/bR}$$
という写像を
$${\phi \left( r\bmod ab \right)=\left( r\bmod a,r\bmod b \right)}$$
であたえるとこのとき、$${\phi }$$は環同型
ring isomorphism となる。
ここで、$${R}$$は整数でないので、
$${r\bmod a}$$ を定義しておく必要がある。
定義：可換環$${R}$$ のイデアル$${I}$$とは、
$${I\subset R}$$ で$${I\ne \phi }$$そして
$${a\in I}$$かつ$${b\in I}$$のとき、$${a+b\in I}$$
$${a\in I}$$かつ$${r\in R}$$のとき、$${ra\in I}$$
をみたすものである。
$${I=cR}$$という特別なかたちのイデアルは
単項イデアルであるといわれる。
定義：
Rを可換環とする。
$${c\in R}$$をとるとき
$${c}$$により生成される単項イデアルを$${cR}$$ とかく。
すなわち、$${cR=\left\{ cr:r\in R \right\}}$$ 。
$${R}$$ のイデアル$${I}$$があるとき
$${a}$$が属する剰余類coset は
$${a+I=\left\{ a+c:c\in I \right\}}$$
とかける。
$${a,b\in R}$$にたいして$${a-b\in I}$$のとき、
$${b\equiv a\left( \bmod I \right)}$$
と書こう。
剰余類cosetの和、積
$${\left( a+I \right)+\left( b+I \right)=\left( a+b \right)+I}$$
$${\left( a+I \right)\cdot \left( b+I \right)=\left( a\cdot b \right)+I}$$
を定義して(well definedになる)、
この方法で剰余類を要素とする環（＝商環）ができる。
$${r+I=r\bmod I}$$、
$${a+cR=a\bmod cR}$$、
$${a\equiv b\left( \bmod cR \right)}$$
$${a\equiv b\left( \bmod c \right)}$$
など省略形をつかう。
$${\psi :R\to R/aR\times R/bR}$$
という写像を
$${\psi \left( r \right)=\left( r\bmod a,r\bmod b \right)}$$
であたえる
（写像$${\phi }$$ と似ているが定義域がことなっている！）
命題
$${\ker \psi =\left\{ r\in R:\psi \left( r \right)=\left( 0,0 \right) \right\}}$$
と書くと
$${abR=\ker \left( \psi \right)}$$
証明）
$${r\in abR}$$とすると$${r=abs}$$$${s\in R}$$と書ける。$${\psi \left( abs \right)=\left( abs\bmod a,abs\bmod b \right)=\left( 0,0 \right)}$$ 。
ゆえに、$${abR\subset \ker \left( \psi \right)}$$
ぎゃくに、$${r\in ker\left( \psi \right)}$$とすると、
$${r\equiv 0\left( \bmod a \right)}$$かつ$${r\equiv 0(\bmod b)}$$
である。
$${r\equiv 0\left( \bmod a \right)\Leftrightarrow r\in aR}$$、
$${r\equiv 0\left( \bmod b \right)\Leftrightarrow r\in bR}$$
であるから、
$${r=as=bt}$$ となる$${s,t\in R}$$がある。したがって
$${r\in abR}$$。
$${abR=\ker \left( \psi \right)}$$が証明できた。
補題（再録）：$${R}$$ を可換環とする。
$${a,b\in R}$$にたいして
$${aR+bR=R}$$ をみたすを仮定する。このとき、
$${\phi :R/abR\to R/aR\times R/bR}$$
という写像を
$${\phi \left( r\bmod ab \right)=\left( r\bmod a,r\bmod b \right)}$$
であたえると、$${\phi }$$ は環同型
ring isomorphism となる。
証明）$${\psi :R\to R/aR\times R/bR}$$という写像を
$${\psi \left( r \right)=\left( r\bmod a,r\bmod b \right)}$$
であたえる。
$${1\in R}$$ ,
$${aR+bR=R}$$
より
$${au+bv=1}$$
となる$${u,v\in R}$$をえらぶ。
同型とは全単射な準同型のことである。
$${\phi }$$は準同型$${\psi :R\to R'}$$の
性質をそのまま引き継ぐので準同型である。同型をいうには
$${\phi }$$が全単射になっていることをしめせばよい。
（単射なこと）：
$${\phi \left( a+\ker \psi \right)=\phi \left( a'+\ker \psi \right)}$$ $${\Rightarrow }$$$${\psi \left( a \right)=\psi \left( a' \right)}$$
$${\Rightarrow }$$$${\psi \left( a-a' \right)=0}$$ $${\Rightarrow }$$$${a-a'\in \ker \psi }$$
$${\Rightarrow }$$$${a+\ker \psi =a'+\ker \psi }$$
となりOK
（全射なこと）
$${bv=1-au}$$ であったので
$${\psi \left( 1-au \right)=\psi \left( bv \right)}$$、
$${\psi \left( r \right)=\left( r\bmod a,r\bmod b \right)}$$
より
$${\psi \left( 1-au \right)=\psi \left( bv \right)=\left( 1-au\bmod a,bv\bmod b \right)=\left( 1,0 \right)}$$
同様に
$${\psi \left( au \right)=\psi \left( 1-bv \right)=\left( au\bmod a,1-bv\bmod b \right)=\left( 0,1 \right)}$$
そこで、$${\left( c,d \right)\in R'}$$を任意にえらぶと
$${\left( c,d \right)=c\left( 1,0 \right)+d\left( 0,1 \right)=c\psi \left( bv \right)+d\psi \left( au \right)}$$$${=\psi \left( cbv+dau \right)}$$
となるので$${cbv+dau\in R}$$ をみつけることができる。
$${\psi }$$ の全射性から$${\phi }$$ が全射を与えることがわかる。
（$${\phi \left( a+\ker \psi \right)=\psi \left( a \right)}$$をおもいだせ）。