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

682

はじめに

中国式剰余定理については、名前はよく聞くが正直よくわかっていないという印象であった。そのため，自分の理解のために中国式剰余定理についてまとめてみることを考えた。
当初は１つの記事で高校数学における中国式剰余定理と，一般の中国式剰余定理およびその関係について紹介しようと考えていたが，書き始めるといろいろとボリュームが増えてきたため記事を分割することとした。目標は全４回である。

高校数学における中国式剰余定理（本記事）

群論および環論の基礎
整数環における中国式剰余定理
一般の環における中国式剰余定理

2020/12/07　追記
とりあえず第4回まで終えた。第2回，第3回の記事は群論と環論の定義や命題等の紹介なのでめんどくさい方は第4回までジャンプしてほしい。

高校数学における中国式剰余定理

7で割ると1余り，5で割ると2余る整数をすべて求めよ。

この問題は以下の連立合同式の解を求めることと同じである。
$\begin{array}{r} {\begin{cases} x \equiv 1 (\mod 7) \\ x \equiv 2 (\mod 5) \end{cases} \end{array}$
第 $1$ 式を満たす $x$ は $x = 7 y + 1$ の形でかけるものだけである。
これを第 $2$ 式に代入すると $7 y + 1 \equiv 2$ ( $\mod 5$ )つまり， $7 y \equiv 1$ ( $\mod 5$ )である。これを満たす整数 $y$ は， $y = 5 k + 3$ ( $k$ は任意の整数)である。
従って，求めるものは $x = 35 k + 22$ ( $k$ は任意の整数)となる。

中国式剰余定理（高校数学）

$m, n$ を互いに素な整数, $a, b$ を任意の整数とする。このとき，次を満たす整数 $x$ が $0 \leq x < m n$ にただ１つ存在する。
$\begin{array}{r} {\begin{cases} x \equiv a (\mod m) \\ x \equiv b (\mod n) \end{cases} \end{array}$

$a$ , $c$ , $m$ を整数で $m >$ 1， $g = g c d (a, m)$ ， $g | c$ とする。このとき， $a x \equiv c (\mod m)$ はちょうど $g$ 個の互いに合同でない解をもつ。

補題2

$a x \equiv c (\mod m)$ の解を見つけるには， $a x - c = m y$ となる整数 $y$ を見つければよい。つまり，
$a x \equiv c (\mod m)$ が解をもつ $\Leftrightarrow a x - m y = c$ が解をもつ
ということである。いま， $g = gcd (a, m)$ であるから， $a u + m v = g$ は常に解をもつ。さらに，ユークリッドの互除法から解 $u = u_{0}$ ， $v = v_{0}$ が見つかる。 $g | c$ だから，両辺に整数 $c / g$ をかけて， $a \frac{c u_{0}}{g} + m \frac{c v_{0}}{g} = c$ を得る。これは $x_{0} \equiv \frac{c u_{0}}{g} (\mod m)$ は合同式 $a x \equiv c (\mod m)$ の解であることを意味している。
次に $x_{0}$ から $g$ 個の合同でない解を作る。
$x_{1}$ を $x_{0}$ とは異なる解とする。このとき， $a x_{1} \equiv a x_{0} (\mod m)$ となるので $m$ は $a x_{1} - a x_{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, \dots, g - 1$ の $g$ 個の異なる解を得る。

定理１

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