中国剰余定理の証明と2元、3元、4元、5元の例題について
1. 中国剰余定理とは？
例えば、次の合同式を同時に満たす1以上105未満の整数 \( x \) を求めることができます。
- \( x \equiv 2 \pmod 3 \)
- \( x \equiv 3 \pmod 5 \)
- \( x \equiv 2 \pmod 7 \)
- 中国剰余定理・・・「ちゅうごくじょうよていり」と読みます。
- 別名・・・中国人の剰余定理、孫子の定理とも呼ばれます。
2. 二元の場合
\[ \begin{cases} x \equiv a \pmod m \\ x \equiv b \pmod n \end{cases} \]
$x$は$0\leq x < mn$の範囲に存在する。
2.1. 証明の方針
次の二つを示します。
- 存在性の証明： 解 \( x \) が存在することを示す。
- 一意性の証明： 解 \( x \) が法 \( mn \) で一意に定まることを示す。
2.2. 解の存在性の証明
互いに素な整数 \( m \) と \( n \) について、次が成り立つ。
\[ s m + t n = 1 \]
等式を満たす整数解$(m,n)$が存在します。
法 \( m \) と法$n$の合同式をそれぞれ考えると、
\[ t n \equiv 1 \pmod m \]
\[ sm \equiv 1 \pmod n \]
ここで、$x=at n+ bsm$とすると、
\[ x \equiv atn \equiv a \pmod m \]
\[ x \equiv bsm \equiv b \pmod n \]
となり与えられた連立合同式になる。
2.3. 一意であることの証明
mnを法としたときに解は一意に存在しないと仮定する。したがって、連立合同式を満たす$x,y$が存在する。このとき、
$$x-y\equiv a-a \equiv 0 \pmod m$$
$$x-y\equiv b-b \equiv 0\pmod n$$
したがって、$x-y$はmnの倍数であることがわかる。$x,y$は0以上mn未満の自然数であるので、x=yになり矛盾する。したがって、mnを法としたときに解は一意に定まる。
3. 一般の場合
\[ \begin{cases} x \equiv a_1 \pmod {n_1} \\ x \equiv a_2 \pmod {n_2} \\ \vdots \\ x \equiv a_k \pmod {n_k} \\ \end{cases} \]
$x$は$0\leq x < n_1n_2\cdots n_k$の範囲に存在する。
3.1. 証明の方針
- 存在性の証明： 一般の場合は２元の場合を利用して、数学的帰納法で証明します。
- 一意性の証明： 2元の場合と同様の方法で示す。
3.2. 存在性の証明
k=1のとき、
$$x\equiv a_1 \pmod {n_1} $$
となるので、解 \( x \) が法 \( n_1 \) で一意に定まる。
$k=m$のとき、連立合同式
\[ \begin{cases} x \equiv a_1 \pmod {n_1} \\ x \equiv a_2 \pmod {n_2} \\ \vdots \\ x \equiv a_m \pmod {n_m} \\ \end{cases} \]
が成り立つxについて、法を$n_1n_2\cdots n_m$としたときの合同式は
$$x\equiv y\pmod{n_1n_2\cdots n_m}$$
$0\leq y < n_1n_2\cdots n_m$で$y$が存在する。
$k=m+1$のとき、
$$x \equiv a_{m+1} \pmod {n_{m+1}}$$
とする。ここで、$n_{m+1}$は$n_1,n_2,\cdots n_m$と互いに素である。仮定より、二つの連立合同式が成り立つ。
$$\begin{cases}x\equiv y\pmod{n_1n_2\cdots n_m} \\ x \equiv a_{m+1} \pmod {n_{m+1}} \end{cases}$$
そして、先ほど示したように二元の連立合同式において解は一意に定まるので、あるzに対して、
$$x\equiv z\pmod{n_1n_2\cdots n_mn_{m+1}}$$
zは０以上$n_1n_2\cdots n_mn_{m+1}$の範囲に収まる。したがって、k=m+1の場合にも成り立つ。
数学的帰納法により、一般の場合の連立合同式の解は一意に定まる。
3.3. 一意性の証明
mnを法としたときに解は一意に存在しないと仮定する。したがって、連立合同式を満たす$x,y$が存在する。このとき、与えられた \( m_1, m_2, \dots, m_k \) が互いに素であるとき、次の連立合同式を考えます。
\[ \begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases} \]
上記のように、任意の \( i\) に対して、\( x – y \) が各 \( m_i \) で割り切れるので
\[ \begin{cases} x-y \equiv a_1-a_1 \equiv0\pmod{m_1} \\ x-y \equiv a_2-a_2 \equiv0\pmod{m_2} \\ \vdots \\ x-y \equiv a_k-a_k \equiv0\pmod{m_k} \end{cases} \]
が導かれます。したがって、$x-y$は$m_1 \times m_2 \times \dots \times m_k $の倍数である。
このとき、\( x \) は範囲 \( 0 \leq x < m_1 \times m_2 \times \dots \times m_k \) の中に存在するため、再び \( x = y \) となり矛盾するため、解が一意に定まることが示されます。
3.4. 解の構成
\[ x = \sum_{i=1}^{k} a_i N_i N_i^{-1} \pmod{N} \]
全体の法の積Nを次のように定義します。
\[ N = n_1 \times n_2 \times \dots \times n_k \]
それぞれの \( n_i \) に対して、次のように \( N_i \) を定義します。
\[ N_i = \frac{N}{n_i} \]
つまり、\( N_i \) は \( N \) から \( n_i \) を除いた他の全ての法の積です。
それぞれの \( N_i \) に対して、次の合同式を満たす逆元 \( N_i^{-1} \) を求めます。
\[ N_i N_i^{-1} \equiv 1 \pmod{n_i} \]
求めた \( N_i \) とその逆元 \( N_i^{-1} \) を使って、次のように解 \( x \) を構成します。
\[ x = \sum_{i=1}^{k} a_i N_i N_i^{-1} \pmod{N} \]
この式の中で、各 \( N_i N_i^{-1} \) は \( n_i \) の法に対して \( 1 \) になり、他の法 \( n_j \) (\( j \neq i \)) に対しては \( 0 \) になります。したがって、この式で構成された \( x \) はすべての連立合同式を満たします。
4. 例題
4.1. 連立合同式の解き方
連立合同式を解く手順は次のようになります。
4.2. 例題1：2元の例題
\[\begin{cases} x \equiv 2 \pmod{3}\\ x \equiv 3 \pmod{5} \end{cases}\]
法の積を求めると、
$$ N = 3 \times 5 = 15 $$
$N_i$を求めると、
$$ N_1 = \frac{N}{3} = 5 $$
$$ N_2 = \frac{N}{5} = 3 $$
次に、\( N_1^{-1} \) と \( N_2^{-1} \) を計算します。合同式の性質を利用して逆元を求める。（拡張ユークリッドの互除法でも求めることができる。）
\( N_1^{-1} \mod 3 \) を求めます。
$$\begin{align*} 5 N_1^{-1} &\equiv 1 \pmod{3} \\ 2N_1^{-1} &\equiv 1 \pmod{3} \\ 2N_1^{-1} &\equiv 4 \pmod{3} \\ N_1^{-1} &\equiv 2 \pmod{3} \\ \end{align*}$$
\( N_2^{-1} \mod 5 \) を求めます。
$$\begin{align*} 3N_2^{-1} &\equiv 1 \pmod{5} \\ 3N_2^{-1} &\equiv 6 \pmod{5} \\ N_2^{-1} &\equiv 2 \pmod{5} \\ \end{align*}$$
これをもとにして、解を求めます。
\[ x = 2 \times 5 \times 2 + 3 \times 3 \times 2 \equiv 20 + 18 \equiv 5+3 \equiv 8\pmod{15} \]
解は \( 8 \) です。
4.3. 例題2：3元の例題
\[ \begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \\ \end{cases} \]
法の積を求めると、
$$N = 3 \times 5 \times 7 = 105 $$
$N_i$を求めると、
$$ N_1 = \frac{105}{3} = 35 , N_2 = \frac{105}{5} = 21 , N_3 = \frac{105}{7} = 15$$
合同式の性質を利用して逆元を求める。（拡張ユークリッドの互除法でも求めることができる。）
$$\begin{align*} 35N_1^{-1} &\equiv 1 \pmod{3} \\ 2N_1^{-1} &\equiv 1 \pmod{3} \\ 2N_1^{-1} &\equiv 4 \pmod{3} \\ N_1^{-1} &\equiv 2 \pmod{3} \\ \end{align*}$$
同様に、他の逆元も求めます。
$$\begin{align*} 21N_2^{-1} &\equiv 1 \pmod{5} \\ N_2^{-1} &\equiv 1 \pmod{5} \\ \end{align*}$$
$$\begin{align*} 15N_3^{-1} &\equiv 1 \pmod{7} \\ N_3^{-1} &\equiv 1 \pmod{7} \\ \end{align*}$$
解 \( x \) を計算すると、
\[\begin{align*} &x = (2 \times 35 \times 2) + (3 \times 21 \times 1) + (2 \times 15 \times 1) \\ &\equiv 140 + 63 + 30 \pmod{105} \\ &\equiv 35+ 63 + 30 \pmod{105} \\ &\equiv 128 \pmod{105} \\ &\equiv 23\pmod{105} \\ \end{align*}\]
したがって、解 は\( 23 \) となります。
4.4. 例題3：4元の例題
\[\begin{cases} x \equiv 1 \pmod{2}\\ x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 4 \pmod{7} \end{cases}\]
法の積を求めると、
$$N = 2 \times 3 \times 5 \times 7 = 210 $$
$N_i$を求めると、
$$N_1 = \frac{N}{2} = 105, N_2 = \frac{N}{3} = 70 , N_3 = \frac{N}{5} = 42,N_4 = \frac{N}{7} = 30 $$
次に、各 \( N_i^{-1} \) を計算します。
\( N_1^{-1} \mod 2 \) を求めます。
$$\begin{align*} 105 \times N_1^{-1} &\equiv 1 \pmod{2} \\ N_1^{-1} &\equiv 1 \pmod{2} \\ \end{align*}$$
\( N_2^{-1} \mod 3 \) を求めます。
$$\begin{align*} 70 \times N_2^{-1} &\equiv 1 \pmod{3} \\ N_2^{-1} &\equiv 1 \pmod{3} \\ \end{align*}$$
\( N_3^{-1} \mod 5 \) を求めます。
$$\begin{align*} 42 N_3^{-1} &\equiv 1 \pmod{5} \\ 2 N_3^{-1} &\equiv 1 \pmod{5} \\ 2 N_3^{-1} &\equiv 6 \pmod{5} \\ N_3^{-1} &\equiv 3 \pmod{5} \end{align*}$$
\( N_4^{-1} \mod 7 \) を求めます。
$$\begin{align*} 30N_4^{-1} &\equiv 1 \pmod{7} \\ 2 N_4^{-1} &\equiv 1 \pmod{7} \\ 2 N_4^{-1} &\equiv 8 \pmod{7} \\ N_4^{-1} &\equiv 4 \pmod{7} \end{align*}$$
これをもとにして、解を求めます。
\[ \begin{align*} x &= 1 \times 105 \times 1 + 2 \times 70 \times 1 + 3 \times 42 \times 3 + 4 \times 30 \times 4 \\ &\equiv 105 + 140 + 378 + 480 \pmod{210} \\ &\equiv 245 +168+60 \pmod{210} \\ &\equiv 35+228 \pmod{210} \\ &\equiv 35+18 \pmod{210} \\ &\equiv 53 \pmod{210} \\ \end{align*}\]
したがって、解は \( 53 \) です。
4.5. 例題4：5元の例題
\[\begin{cases} x \equiv 0 \pmod{2}\\ x \equiv 2 \pmod{3} \\ x \equiv 2 \pmod{5} \\ x \equiv 6 \pmod{7} \\ x \equiv 10 \pmod{11} \end{cases}\]
まず、法の積を求めます。
\[ N = 2 \times 3 \times 5 \times 7 \times 11 = 2310 \]
次に、各 \( N_i \) を求めます。
\[ N_1 = \frac{2310}{2} = 1155, \quad N_2 = \frac{2310}{3} = 770, \quad N_3 = \frac{2310}{5} = 462 \] \[ N_4 = \frac{2310}{7} = 330, \quad N_5 = \frac{2310}{11} = 210 \]
次に、合同式の性質を利用して逆元を求めます。
\( N_1^{-1} \pmod 2 \)を計算します。
$$\begin{align*} 1155 N_1^{-1} &\equiv 1 \pmod{2} \\ N_1^{-1} &\equiv 1 \pmod{2} \\ \end{align*}$$
\( N_2^{-1} \pmod 3 \)を計算します。
$$\begin{align*} 770 \times N_2^{-1} &\equiv 1 \pmod{3} \\ 2N_2^{-1} &\equiv 1 \pmod{3} \\ 2N_2^{-1} &\equiv 4 \pmod{3} \\ N_2^{-1} &\equiv 2 \pmod{3} \\ \end{align*}$$
\( N_3^{-1} \mod 5 \)を計算します。
$$\begin{align*} 462 N_3^{-1} &\equiv 1 \pmod{5} \\ 2 N_3^{-1} &\equiv 1 \pmod{5} \\ 2 N_3^{-1} &\equiv 6 \pmod{5} \\ N_3^{-1} &\equiv 3 \pmod{5} \end{align*}$$
\( N_4^{-1} \mod 7 \)を計算します。
$$\begin{align*} 330N_4^{-1} &\equiv 1 \pmod{7} \\ N_4^{-1} &\equiv 1 \pmod{7} \end{align*}$$
\( N_5^{-1} \mod 11 \)を計算します。
$$\begin{align*} 210N_5^{-1} &\equiv 1 \pmod{11} \\ N_5^{-1} &\equiv 1 \pmod{11} \end{align*}$$
解を計算します。
\[\begin{align*} x &= (0 \times 1155 \times 1) + (2 \times 770 \times 2) + (2 \times 462 \times 3) + (6 \times 330 \times 1) + (1 \times 210 \times 10) \\ &\equiv 0+3080+2772+(1980+2100) \pmod{2310} \\ &\equiv 0+770+462+4080 \pmod{2310} \\ &\equiv 0+770+462+1770\pmod{2310} \\ &\equiv 3002\pmod{2310} \\ &\equiv 692\pmod{2310} \\ \end{align*} \]
したがって、解は \( 692\) となります。
