高校数学：整数：ユーグリッドの互除法とは(最大公約数のからくり)

こんにちは。今回はユーグリッド互除法について書いておきます。何であの方法で最大公約数が求まるのか見ていきましょう。

ユーグリッドの互除法とは

ユーグリッドの互除法

自然数 $A, B$ に対し, $A$ を $B$ で割ったときの商を $q$ , 余りを $r$ とすると,
$A=qB+r$ という等式が成り立つ。
このとき, 「 $A$ と $B$ の最大公約数」は, 「 $B$ と $r$ の最大公約数」に等しいというもの。

証明というか意味的なもの

例えば,　最大公約数が $g$ の2数 $ag$ , $bg$ があるとします。ただし, $a, b$ は互いに素である。
意味的にはこの2数の差の最大公約数も $g$ になるということです。
つまり, $ag-bg=g(a-b)\cdots\maru1$
であり, $ag, bg, g(a-b)$ の最大公約数は $g$ になります。
このとき, $ag$ を $bg$ で割った余りというのは, $\maru1$ の差をとる作業を何回か繰り返して残ったものなので, その繰り返した回数を $q$ とすると,
$ag-qbg=g(a-qb)\cdots\maru2\ (bg>g(a-qb)>0)$ となります。この $g(a-qb)$ が $ag$ を $bg$ で割った余りで, このとき, $ag, bg, g(a-qb)$ の最大公約数も $g$ となります。
$ag=A, bg=B, g(a-qb)=r$ とすると, $\maru2$ は
$A-qB=r$ と書け, これより,
$A=qB+r$ となる。
このことから, $A, B$ の最大公約数は, $B, r$ の最大公約数と等しいと言えます。
この原理を繰り返し用いることで, 最大公約数を求めることを実現しており, ちょうど余りが0になるときの $q$ が最大公約数 $g$ になります。
以下にその流れ的なものを記すと, $x$ を $y$ で割ったときの余りが0ということは,
$x=gy+0$ ということであり,
$x=gy+0\to g, 0$ の最大公約数は $g\to x, y$ の最大公約数は $g\to\cdots\to a, b$ の最大公約数は $g$ と言う具合に最大公約数が求まる仕組みになっている。
ちなみに, ある2数を互除法を用いて計算していき, 余りが1になれば, その2数は互いに素の関係にあることが知られている。