$a_{1}$, $a_{2}$ を整数, $m_{1}$, $m_{2}$ を正の整数とし, $d=\gcd(m_{1},\,m_{2})$ とおく. このとき, 連立合同式 \begin{equation} \begin{split} x&\equiv a_{1}\pmod{m_{1}}, \\ x&\equiv a_{2}\pmod{m_{2}} \end{split} \tag{$*$} \end{equation} が整数解を持つための必要十分条件は, $$ a_{1}\equiv a_{2} \pmod{d} $$ が成り立つことである. さらに, 連立合同式 ($*$) が整数解を持つとき, その解は $m_{1}$, $m_{2}$ の最小公倍数を法として一意的である. このことを証明せよ.
解答例 1
連立合同式 ($*$) が解 $x\in\mathbb{Z}$ をもつとする. すなわち, \begin{align*} x&\equiv a_{1}\pmod{m_{1}}, \\ x&\equiv a_{2}\pmod{m_{2}}. \end{align*} $m_{1}$, $m_{2}$ はともに $d$ で割り切れるから, \begin{align*} x&\equiv a_{1}\pmod{d}, \\ x&\equiv a_{2}\pmod{d}. \end{align*} ゆえに, $a_{1}\equiv a_{2}\pmod{d}$. 逆に, $a_{1}\equiv a_{2}\pmod{d}$ が成り立つと仮定すると, 合同式 $$ m_{1}t\equiv a_{2}-a_{1}\pmod{m_{2}} $$ は解 $t\in\mathbb{Z}$ をもつ. $x = a_{1} + m_{1}t$ とおけば, $x$ は連立合同式 ($*$) の解である.
$x_{1}$, $x_{2}\in\mathbb{Z}$ を連立合同式 ($*$) の解とすると, \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}$ の最小公倍数を $l$ とおくと, 最小公倍数の性質から, $$ l\mid (x_{1}-x_{2}). $$ すなわち, $$ x_{1}\equiv x_{2}\pmod{l}. $$
最終更新日：2011年11月02日