中国式剰余定理を理解する（第1回　高校数学）

$ax \equiv c \pmod m $の解を見つけるには，$ax-c = my$となる整数$y$を見つければよい。つまり，
$ax \equiv c \pmod m$ が解をもつ $\Leftrightarrow ax-my=c$が解をもつ
ということである。いま，$g = \gcd (a,m)$であるから，$au + mv = g$は常に解をもつ。さらに，ユークリッドの互除法から解$u = u_0$，$v = v_0$が見つかる。$g | c$だから，両辺に整数$ c/g$ をかけて，$a\frac{cu_0}{g} +m\frac{cv_0}{g} = c$を得る。これは$ x_0 \equiv \frac{cu_0}{g} \pmod m $は合同式$ax \equiv c \pmod m$の解であることを意味している。
次に$x_0$から$g$個の合同でない解を作る。
$x_1$を$x_0$とは異なる解とする。このとき，$ax_1 \equiv ax_0 \pmod m$となるので$m$は$ax_1 - ax_0$を割り切る。つまり，$\frac{m}{g}$は$\frac{a(x_1-x_0)}{g}$を割り切る。また，$\gcd(a,m)=g$なので$m/g$と$a/g$は互いに素。したがって，$m/g$は$x_1-x_0$を割り切る。つまり，ある整数$k$が存在して,$x_1 = x_0 + k\cdot \frac{m}{g}$と表せる。
しかし，どの2つの解も$m$の倍数の違いに関しては同一の解とみなすので，$k=0,1,\cdots,g-1$の$g$個の異なる解を得る。

問題1と同様の手法により証明できる。
第1式を満たす$x$は$y$を任意の整数として，$x = my + a$の形にかけるもののみ。これを第2式に代入すると$my \equiv b-a \pmod n$となる。このとき$m,n$は互いに素であるから，これを満たす整数$y_1$が$0 \leq y_1 < n$にただ１つ存在する（補題2）。このとき$x_1 = my_1 + a$は元の合同式の解となる。$x_1$の一意性は$y_1$の一意性から従う。
最後に，この$x_1$が$0 \leq x_1 < mn$を満たすことを示す。$0 \leq y_1 \leq n-1$だから，$0 \leq mx_1 \leq mn-m + a$である。ここで，$a$は$m$で割ったときのあまりなので$a < m$であるから$mm-m+a < mn$となり，$0 \leq x_1 < mn$が成り立つ。