空論上の砂、楼閣上の机。

The Castle of Indolence

中国剰余定理

3世紀から5世紀にかけて成立したと言われている中国の算術書『孫子算経』に

ある物を $3$ つずつ数えると $2$ つ余り, $5$ つずつ数えると $3$ 余り, $7$ つずつ数えると $2$ 余るとき, 物の個数はいくらか.

という問題があり, 解答は

$3$ で割ると $2$ 余る数として $140$ とおく. $5$ で割ると $3$ 余る数として $63$ とおく. $7$ で割ると $2$ 余る数として $30$ とおく. これらを足し合わせて $233$ を得る. これから $210$ を引いて答えを得る. 一般に, $3$ つずつにして物を数えて余りに $70$ をかける. $5$ で割った余りに $21$ をかける. $7$ で割った余りに $15$ をかける. $106$ 以上ならば $105$ を引くことで答えを得る.

とあります. これは環の同型 $$\mathbf{Z}/3\mathbf{Z}\times\mathbf{Z}/5\mathbf{Z}\times\mathbf{Z}/7\mathbf{Z}\cong\mathbf{Z}/105{\mathbf{Z}}$$ において $(\overline{2},\overline{3},\overline{2})\mapsto\overline{23}$ となることが背景にあるといえます. この同型を与える定理が中国剰余定理 (Chinese remainder theorem) です.

$A$ を単位的可換環とします.

補題1. $A$ のイデアル $I_1,\dots,I_n$ がどの2つも互いに素($i\neq j$ ならば $I_i+I_j=A$)ならば $$I_1\cdots I_n=\bigcap _ {i=1} ^ n I_i$$
証明. $n=1$ のときは明らか. $n=2$ のとき成り立てば $I_1I_2I_3=I_1\cap I_2I_3=I_1\cap I_2\cap I_3$ のように帰納的に適用でき主張が従うので, $n=2$ のときだけ示せば十分である. $I_1+I_2=A$ であるから $x+y=1$ なる $x\in I_1$, $y\in I_2$ が存在する. このとき $IJ$ と $I\cap J$ の定義より明らかに $I_1I_2\subset I_1\cap I_2$ であり, また任意の $I_1\cap I_2$ の元 $a$ に対し $a=a\cdot1=a(x+y)=ax+ay\in I_1I_2$ であるから, $I_1I_2=I_1\cap I_2$ である.
定理2. (中国剰余定理)

$A$ のイデアル $I_1,\dots,I_n$ がどの2つも互いに素(すなわち $i\neq j$ ならば $I_i+I_j=A$)であると仮定する. このとき自然な環準同型

$$A\to A/I_1\cdots I_n; x\mapsto(x+I_1,\dots,x+I_n)$$
は全射であり, 環同型$$R/I_1\dots I_n\to R/I_1\times\cdots\times R/I_n$$を誘導する.

証明. $n=1$ のとき明らか. $n=2$ のとき成り立てば $R/I_1I_2I_3\cong R/I_1I_2\times R/I_3$ のように帰納的に適用でき主張が従うので, $n=2$ のときだけ示せば十分である. $n=2$ のとき, 自然な写像$$f _ 1 \colon R\to R/I _ 1;\,x\mapsto x+I _ 1\\f _ 2\colon R\to R/I _ 2;\,x\mapsto x+I _ 2$$に対し定まる
$$f\colon R\to R/I_1\times R/I_2;\,r\mapsto\left(f_1(r),f_2(r)\right)$$
は環準同型である. まず核を決定する. $r\in\mathrm{Ker}{f}\Longleftrightarrow f_1(r)=f_2(r)=0$ より
$$\mathrm{Ker}{f}=\mathrm{Ker}{f_1}\cap\mathrm{Ker}{f_2}=I_1\cap I_2=I_1I_2$$
である. 次に全射性を示して像を決定する. $a_1+a_2=1$ なる $a_1\in I_1$, $a_2\in I_2$ に対し, $a_2=1-a_1\equiv1\pmod{I_1}$ より $f_1(a_1a_2)=f_1(a_1)$ であり, 同様にして $f_2(a_1a_2)=f_2(a_2)$ であるから, $$f(a_1a_2)=\left(f_1(a_1),f_2(a_2)\right)$$より全射性が示された. したがって $\mathrm{Im}{f}=R/I_1\times R/I_2$ である. $f$ に対して準同型定理を適用することにより主張を従う.
系3. どの2つも互いに素な $f_1,\dots,f_n\in K[X]$($i\neq j$ ならば $(f_i,f_j)=K[X]$)に対して
$$K[X]/(f_1\cdots f_n)\cong K[X]/(f_1)\times\cdots\times K[X]/(f_n)$$
系4. どの2つも互いに素な整数 $n_i$ ($i=1,\dots, k$) に対して, $k$ 本の連立方程式 $x\equiv a_i \pmod{n_i}$ を満たす $x$ は $0\leqq x\lt n _ 1\cdots n_k$ の範囲に一意に存在する.