ユーグリットの互除法の概要と証明

ユーグリットの互除法についてまとめます。

定理は以下のようになります

自然数a,bについて、aをbで割った余りをrとすると、
aとbの最大公約数は、bとrの最大公約数に等しい

ユーグリットの互助法を使い319と143の最大公約数を求めてみます。

定理より319と143の最大公約数と319を143で割った余り33と商143の最大公約数は等しい、

319と143の最大公約数 = 143と33の最大公約数

今度は、143と33の最大公約数に着目して、143と33の最大公約数と143を33で割った余り11と商33の最大公約数が等しいから、

143と33の最大公約数 = 33と11の最大公約数

最後に、33と11の最大公約数と33を11で割った余り0との最大公約数に等しいということになりますが、
これ以上は簡単にできませんが、

33と11の最大公約数は11と簡単に求めることができます。

よって、=を辿って、319と143の最大公約数 = 33と11の最大公約数
ですから、319と143の最大公約数は11と求めることができます。

自然数a,bの公約数をdとします。

aとbは自然数l,mとd用いて、

$a = ld$

$b = md$

と表せます。

整数の割り算の等式より、

$a = bq + r - ①$

①にb = mdを代入して

$a = mdq + r - ②$

②をrについてまとめると

$r = d(l - mq) - ③$

③からdがrの約数であることがわかります。

また、dはa,bの公約数なので、dはbを割り切ります。
なので、dはrとbの公約数になります。

同様の方法で、d'がbとrの公約数だとすると、d'はaとbの公約数であることがわかります。

よって、aとbの公約数の集合とrとbの公約数の集合は正しく、最大公約数も同じになります。

初版:2020/4/19