解答例 1

合同式の個数 $n$ に関する数学的帰納法によって証明する.

$n=2$ のとき, $m_{1}$, $m_{2}$ は互いに素であるから, 合同式 $$ m_{1}t\equiv a_{2}-a_{1}\pmod{m_{2}} $$ は解 $t\in\mathbb{Z}$ をもつ. $x = a_{1} + m_{1}t$ とおけば, $x$ は連立合同式 \begin{equation} \begin{split} x&\equiv a_{1}\pmod{m_{1}}, \\ x&\equiv a_{2}\pmod{m_{2}} \end{split} \tag{1} \end{equation} の解である. また, $x_{1}$, $x_{2}\in\mathbb{Z}$ を連立合同式 (1) の解とすると, \begin{align*} &x_{1}\equiv a_{1} \pmod{m_{1}},\quad x_{1}\equiv a_{2} \pmod{m_{2}}, \\ &x_{2}\equiv a_{1} \pmod{m_{1}},\quad x_{2}\equiv a_{2} \pmod{m_{2}}. \end{align*} よって, $$ x_{1}\equiv x_{2} \pmod{m_{1}},\quad x_{1}\equiv x_{2} \pmod{m_{2}}. $$ 言い換えると, $$ m_{1}\mid (x_{1}-x_{2}),\quad m_{2}\mid (x_{1}-x_{2}). $$ $m_{1}$, $m_{2}$ は互いに素であるから, $$ m_{1}m_{2}\mid (x_{1}-x_{2}). $$ すなわち, $x_{1}\equiv x_{2}\pmod{m_{1}m_{2}}$. したがって, 連立合同式 (1) は $m_{1}m_{2}$ を法としてただ1つの整数解をもつ.

$n=k$ のとき, 問題の主張が正しいと仮定すると, 連立合同式 \begin{align*} x & \equiv a_{1} \pmod{m_{1}}, \\ x & \equiv a_{2} \pmod{m_{2}}, \\ & \cdots\cdots, \\ x & \equiv a_{k} \pmod{m_{k}} \end{align*} は整数解 $b_{0}$ をもち, すべての整数解 $x$ は $$ x\equiv b_{0}\pmod{m_{1}m_{2}\cdots m_{k}} $$ を満たす. さらに, 合同式 $x\equiv a_{k+1}\pmod{m_{k+1}}$ を追加したとき, $k+1$ 個の合同式 \begin{align*} x & \equiv a_{1} \pmod{m_{1}}, \\ x & \equiv a_{2} \pmod{m_{2}}, \\ & \cdots\cdots, \\ x & \equiv a_{k} \pmod{m_{k}}, \\ x & \equiv a_{k+1} \pmod{m_{k+1}} \end{align*} の整数解 $x$ は, 連立合同式 \begin{align*} x&\equiv b_{0} \pmod{m_{1}m_{2}\cdots m_{k}}, \\ x&\equiv a_{k+1}\pmod{m_{k+1}} \end{align*} の整数解である. また, $m_{1}$, $m_{2}$, $\ldots$, $m_{k}$, $m_{k+1}$ が対ごとに素であることより, $$ \gcd(m_{1}, m_{k+1}) = \gcd(m_{2}, m_{k+1}) = \cdots = \gcd(m_{k}, m_{k+1}) = 1 $$ であるから, $$ \gcd(m_{1}m_{2}\cdots m_{k}, m_{k+1}) = 1. $$ ゆえに, $n=2$ の場合より, この連立方程式は整数解 $b'_{0}$ をもち, すべての整数解 $x'$ は $$ x'\equiv b'_{0}\pmod{m_{1}m_{2}\cdots m_{k}m_{k+1}} $$ を満たす. したがって, $k+1$ のときも問題の主張は正しい.

最終更新日：2011年11月02日