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

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

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

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

例えば,　最大公約数がの2数, があるとします。ただし, は互いに素である。
意味的にはこの2数の差の最大公約数もになるということです。
つまり,
であり, の最大公約数はになります。
このとき, をで割った余りというのは, の差をとる作業を何回か繰り返して残ったものなので, その繰り返した回数をとすると,
となります。このがをで割った余りで, このとき, の最大公約数もとなります。
とすると, は
と書け, これより,
となる。
このことから, の最大公約数は, の最大公約数と等しいと言えます。
この原理を繰り返し用いることで, 最大公約数を求めることを実現しており, ちょうど余りが0になるときのが最大公約数になります。
以下にその流れ的なものを記すと, をで割ったときの余りが0ということは,
ということであり,
の最大公約数はの最大公約数はの最大公約数はと言う具合に最大公約数が求まる仕組みになっている。
ちなみに, ある2数を互除法を用いて計算していき, 余りが1になれば, その2数は互いに素の関係にあることが知られている。