中国剰余定理とその詳しい証明

中国剰余定理 (chinese remainder theorem) とは，複数の割り算の余りに関する定理です。中国式剰余定理とも言います。中国剰余定理について，その主張と詳しい証明を解説していきます。

m_1, m_2 ,\dots , m_n>0 をどの2つも互いに素な整数とする。このとき， a_1, a_2 ,\dots, a_n\in\mathbb に対し，

をみたす x\in\mathbb が \mod m_1m_2\dots m_n において一意に存在する。

証明

M=m_1m_2\dots m_n とおく。 i = 1,2,\dots, n に対し， M/m_i, m_i は互いに素であるから， \dfracs_i+m_is'_i=1 となる s_i,s'_i\in\mathbb が存在する。

\displaystyle\boldsymbol x= \sum_^n a_i \frac s_i> とする。 j\ne i なら M/m_j\equiv 0\pmod なので，

x\equiv a_i \frac s_i = a_i(1-m_is'_i)\equiv a_i \pmod

x, y を共に条件をみたすとする。このとき， i=1,2,\dots, n に対して，

\beginx-y&\equiv a_i-a_i \equiv 0 \pmod \end

なので， x-y は \operatorname(m_1, m_2,\dots, m_n)=m_1m_2\dots m_n の倍数である。これは， x\equiv y \pmod を意味する。

証明終

環論における中国剰余定理

なお，ここからは 環やイデアルの定義などの専門的な知識が必要 です。簡単のため，（単位元を持つ）可換環としましょう。

中国剰余定理3 (Chinese remainder theorem)

R を可換環， I_1, I_2, \dots, I_n\subsetneq R をどの2つも互いに素(後述)なイデアルとする。このとき，

1. i=1,2,\dots, n に対し， I_i と I_1 \cdots I_I_\cdots I_n は互いに素である。
2. \color I_1 \cap I_2 \cap \dots \cap I_n = I_1I_2\cdots I_n.
3. \color R/(I_1\cap I_2\cap \dots \cap I_n) \simeq R/I_1 \times R/I_2 \times \dots \times R/I_n.

ここでイデアル I,J が 互いに素 とは， I+J=R を意味します。

この定理は，初等整数論における中国剰余定理2の一般化になっています。 実際，可換環 \mathbb において，整数 m_i, m_j が互いに素であることは，イデアル m_i\mathbb, m_j\mathbb が互いに素であることに対応していて， \bmod\, m_i で考えることは， \mathbb/m_i\mathbb で考えることに対応しているからです。

中国剰余定理の系

m_1, \dots, m_n >0 はどの2つも互いに素な整数とする。このとき，

\color\mathbb/m_1\cdots m_n\mathbb \simeq \mathbb/m_1\mathbb\times \dots\times \mathbb/m_n\mathbb.

証明

i=1 としても一般性を失わない。 j =2,\dots, n に対し， I_1, I_j は互いに素なので， x_j+y_j = 1 となる x_j\in I_1, \, y_j\in I_j が存在する。すると，

(x_2+y_2)\cdots (x_n+y_n) = 1\cdots 1=1

である。左辺を展開すると， y_2\cdots y_n \in I_2\cdots I_n であり，残りの項は x_i を少なくとも1つ含むので I_1 の元である。したがって， 1\in I_1 + I_2 \cdots I_n なので， I_1+ I_2 \cdots I_n =R である。

まず n=2 のときを考える。イデアルの定義より， I_1I_2\subset I_1\cap I_2 は明らか。

I_1+I_2=R より， x_1\in I_1,\, x_2\in I_2 で x_1+x_2=1 となるものが存在する。 a\in I_1\cap I_2 とする。このとき， ax_1+ax_2=a である。 ax_1, ax_2\in I_1I_2 なので， a\in I_1I_2 である。

ゆえに I_1\cap I_2 \subset I_1I_2 なので， I_1\cap I_2 = I_1I_2 である。

一般の n については，1.と帰納法を用いて，

I_1I_2 \cdots I_n = I_1 \cap (I_2 \cdots I_n) = \bigcap_^n I_i.

f\colon R \ni a \mapsto (a+I_1, a+I_2) \in R/I_1\times R/I_2

について， \operatornamef = I_1 \cap I_2 である。2.で定めた x_1,x_2 を用いる。任意の a,b\in R に対し，

\begin bx_1+ax_2 &= a + (b-a)x_1 \in a+I_1 \\ &= b+(a-b)x_2 \in b+I_2 \end

であるから， f は全射である。したがって準同型定理より，

R/(I_1\cap I_2) \simeq R/I_1\times R/I_2

を得る。一般の n については1,2.と帰納法により，

\begin&R/(I_1\cap I_2\cap\cdots I_n)\\&= R/(I_1\cap( I_2\cdots I_n) ) \\&\simeq R/I_1\times R/(I_2\cdots I_n ) \\ &= R/I_1\times R/(I_2\cap \dots\cap I_n ) \\ &\simeq R/I_1 \times R/I_2 \times \dots \times R/I_n \end

証明終

参考

1. 堀田良之「代数入門－群と加群－」 (裳華房 数学シリーズ，新装版，2021)
2. 雪江明彦「整数論１ 初等整数論からp進数へ」(日本評論社，2013)
3. 雪江明彦「代数学１ 群論入門」(日本評論社，第2版，2023)
4. 雪江明彦「代数学２ 環と体とガロア理論」(日本評論社，第2版，2023)

関連記事

剰余環 (factor ring)，あるいは商環(quotient ring)とは，両側イデアルによる同値類で割った商集合に入る環構造を指します。剰余環を調べることは，環論において最も基本的なことの一つです。剰余環について，定義がwell-definedであることと，具体例を挙げましょう。

コラッツ予想（コラッツの問題; Collatz conjecture; 角谷予想）は，整数論に関する予想で，中高生でも理解できそうなくらい簡単にもかかわらず，多くの数学者の頭を悩ませる未解決問題の1つとして有名です。これについて，その主張を解説しましょう。

合同式における平方剰余(quadratic residue)・平方非剰余(quadratic nonresidue)の概念と，それを扱うのに便利なルジャンドル記号(Legendre symbol)の定義・性質について，順を追って解説していきましょう。