整数約数と倍数 Euclidの互除法により最大公約数を求める方法、除法の定理、剰余

学習環境

親切な代数学演習新装2版―整数・群・環・体 (加藤明史(著)、現代数学社)の第Ⅰ部(整数)、第1章(約数と倍数)の問14の解答を求めてみる。

b > a

a と bを任意の異なる整数とする。

0 < a < b

のときある整数q、 r が存在して、

\begin{array}{l} b = a q + r \\ 0 \leq r < | a | \end{array}

また、

(b, a) = (a, b) = (a, r)

同様のことを繰り返せば、

\begin{array}{l} a = r q_{1} + r_{1} (0 \leq r_{1} < r) \\ r = r_{1} q_{2} + r_{2} (0 \leq r_{2} < r_{1}) \\ r_{1} = r_{2} q_{3} + r_{3} \\ ⋮ \\ r_{n} = r_{n + 1} q_{n + 2} + 0 \end{array}

\begin{array}{l} (b, a) = (a, r) \\ = (r, r_{1}) \\ = (r_{1}, r_{2}) \\ ⋮ \\ = (r_{n}, r_{n + 1}) \\ = (r_{n + 1}, 0) \\ = r_{n + 1} \end{array}

（証明終）