定理の内容

$a_{1}, a_{2}, \dots , a_{n}$ および $m_{1}, m_{2}, \dots , m_{n}$ があるとき、

$\begin{eqnarray} x &\equiv& a_{1} (\mathrm{mod}\ m_{1}) \\ x &\equiv& a_{2} (\mathrm{mod}\ m_{2}) \\ &\vdots& \\ x &\equiv& a_{n} (\mathrm{mod}\ m_{n}) \\ \end{eqnarray}$

を全て満たす整数 $x$ が存在する必要十分条件は

$\begin{eqnarray} a_{1} \equiv a_{2} \equiv \dots \equiv a_{n} (\mathrm{mod}\ \mathrm{LCM}(m_{1}, m_{2}, \cdots , m_{n})) \end{eqnarray}$

であり、このとき $0 \le x \lt \mathrm{LCM}(m_{1}, m_{2}, \dots , m_{n})$ の範囲にただ一つの解 $x$ が存在する。

互いに素の2つのペアのケース

定理の内容を言い換えると、 $m_{1}, m_{2}$ が互いに素のとき、

$\begin{eqnarray} x &\equiv& a_{1} (\mathrm{mod}\ m_{1}) \\ x &\equiv& a_{2} (\mathrm{mod}\ m_{2}) \\ \end{eqnarray}$

を満たす解 $x$ が $0 \le x \lt m_{1} \times m_{2}$ の範囲にただ一つ存在する。

証明

解の存在性

拡張ユークリッドの互除法を用いることで、

$\begin{eqnarray} km_{1} + hm_{2} = 1 \end{eqnarray}$

となる整数 $k, h$ が存在する。これを変形すると

$\begin{eqnarray} km_{1} = 1 - hm_{2} \equiv 1\ (\mathrm{mod}\ m_{2}) \end{eqnarray}$

となるので

$\begin{eqnarray} a_{2}km_{1} \equiv a_{2}\ (\mathrm{mod}\ m_{2}) \end{eqnarray}$

となる。同様に

$\begin{eqnarray} a_{1}hm_{2} \equiv a_{1}\ (\mathrm{mod}\ m_{1}) \end{eqnarray}$

なので、

$\begin{eqnarray} x = a_{2}km_{1} + a_{1}hm_{2} \end{eqnarray}$

とすれば

$\begin{eqnarray} x &\equiv& a_{1} (\mathrm{mod}\ m_{1}) \\ x &\equiv& a_{2} (\mathrm{mod}\ m_{2}) \\ \end{eqnarray}$

を満たすことがわかる。

解の一意性

$0\le x_{1} \lt x_{2} \lt m_{1}m_{2}$ という2つの解 $x_{1}, x_{2}$ が存在したとする。このとき、

$\begin{eqnarray} x_{1} &\equiv& x_{2}\ (\mathrm{mod}\ m_{1}) \\ x_{1} &\equiv& x_{2}\ (\mathrm{mod}\ m_{2}) \\ \end{eqnarray}$

であるから

$\begin{eqnarray} x_{2} - x_{1} &=& rm_{1} \\ x_{2} - x_{1} &=& sm_{2} \\ \therefore rm_{1} &=& sm_{2} \end{eqnarray}$

となり、 $m_{1}$ と $m_{2}$ は互いに素であるから $r$ は $m_{2}$ の倍数である必要がある。一方解の範囲の条件より $x_{2} - x_{1} = rm_{1} \lt m_{1}m_{2}$ なので、必然的に $r=0$ となり、 $x_{1} = x_{2}$ である。

互いに素ではない2つのペアのケース

$\mathrm{GCD}(m_{1},\ m_{2})=g \gt 1$ のとき、

$\begin{eqnarray} x &\equiv& a_{1} (\mathrm{mod}\ m_{1}) \\ x &\equiv& a_{2} (\mathrm{mod}\ m_{2}) \\ \end{eqnarray}$

の解が存在する必要十分条件は、

$\begin{eqnarray} a_{1} &\equiv& a_{2} (\mathrm{mod} g) \end{eqnarray}$

であり、解は $0 \le x \lt LCM(m_{1},\ m_{2})$ の範囲に存在する。

解の存在性

拡張ユークリッドの互除法により、

$\begin{eqnarray} km_{1} + hm_{2} = g \end{eqnarray}$

となる整数 $k, h$ が存在する。また、 $a_{1} \equiv a_{2}\ (\mathrm{mod}\ g)$ なので、 $a_{2}-a_{1}=ng$ と表されるから、

$\begin{eqnarray} nkm_{1} + nhm_{2} = a_{2} - a_{1} \end{eqnarray}$

ここで $x=nkm_{1}+a_{1}$ と定義すると

$\begin{eqnarray} x=nkm_{1}+a_{1} = -nhm_{2} + a_{2} \end{eqnarray}$

となることから、

$\begin{eqnarray} x &\equiv& a_{1}\ (\mathrm{mod}\ m_{1}) \\ x &\equiv& a_{2}\ (\mathrm{mod}\ m_{2}) \\ \end{eqnarray}$

となることが示せる。また、もし $x$ が $\mathrm{LCM}(m_{1},\ m_{2})$ 以上であれば、 $x%LCM(m_{1},\ m_{2})$ を行っても $\mathrm{mod}\ m_{1}$ と $\mathrm{mod}\ m_{2}$ の値は変わらないので、解が $0 \le x \lt LCM(m_{1},\ m_{2})$ の範囲に存在することもわかる。