一次合同式の解 - こにょにょの冒険

一次合同式とは以下である。　
$ax \equiv b\,\,mod\,n$
$GCD(a,n)=d$ のとき $a=a'd$ 、 $n=n'd$ と書ける。
$ax-b=nt$ （ $t$ は整数)にこれを代入すると、 $a'dx-b=n'dt$ 即ち、 $b=a'dx-n'dt$ より、 $b$ は $d$ を約数として持たなければならない。よって、 $b=b'd$ と書くと、 $a'dx \equiv b'd\,\, mod\,n'd$ なる。 $d$ で割ると以下のようになる。
$a'x \equiv b'\,\, mod\,n'$
この一次合同式の唯一つの解を $x_{0}$ とすると、 $a'x_{0} \equiv b'\,\, mod\,n'$ より $a'x_{0}-b'=n't$
両辺に $d$ 掛けて、 $a'dx_{0}-b'd=n'dt$ 即ち $ax_{0}-b=nt$ となり
$ax_{0} \equiv b\,\, mod\,n$
よって、 $x_{0}$ も元の一次合同式の解である。
ここで、 $x=x_{0}+n't$ とすると $ax=ax_{0}+an't=ax_{0}+a'nt \equiv b\,\, mod\,n$
よって、 $x=x_{0}+n't$ も元の一次合同式の解である。 $x_{0}+n'd \equiv x_{0}\,\, mod\,n$ より、以下の $d$ 個の整数が解である。
$x_{0},\,x_{0}+n',\,x_{0}+2n',\,\cdots,\,x_{0}+(d-1)n'$