解答例 1

合同式 ($*$) が整数解 $x_{0}$ をもつと仮定する. そのとき, ある $t\in\mathbb{Z}$ が存在して, $$ ax-b=mt. $$ ゆえに, $$ d\mid (ax-mt)=b. $$ 逆に, $d$ が $b$ を割り切ると仮定する. そのとき, ある $x_{0}$, $y_{0}\in\mathbb{Z}$ が存在して, $$ ax_{0}+my_{0} = b. $$ よって, $$ ax_{0}\equiv b\pmod{m} $$ となり, 合同式 ($*$) は整数解 $x_{0}$ をもつ.

さらに, $a=a'd$, $m=m'd$, $b=b'd$ とおくとき, 合同式 ($*$) の任意の解 $x\in\mathbb{Z}$ に対して, $$ a'x\equiv b'\pmod{m'},\quad a'x_{0}\equiv b'\pmod{m'} $$ であるから, $$ a'x\equiv a'x_{0}\pmod{m'}. $$ $\gcd(a',\,m')=1$ であるから, $$ x\equiv x_{0}\pmod{m'}. $$ したがって, $x$ は $m$ を法として $$ x_{0},\quad x_{0}+m',\quad x_{0}+2\cdot m',\quad \ldots,\quad x_{0}+(d-1)\cdot m' $$ の $d$ 個のうちのいずれかと合同である. 逆に, これらの $d$ 個はすべて合同式 ($*$) の整数解である. したがって, 合同式 ($*$) の整数解は $m$ を法としてちょうど $d$ 個ある.

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