【標準】ユークリッドの互除法の原理

【基本】ユークリッドの互除法の使い方 で書いた通り、大きな2つの数の最大公約数を求めるためには、ユークリッドの互除法を用いて、余りとの最大公約数を考えていけばいいんでしたね。

しかし、なぜそれでいいんでしょうか。ここでは、ユークリッドの互除法の原理について説明していきます。教科書にも書いてある内容ですが、証明は少し分かりにくいかもしれません。

「余りとの最大公約数を考えればいい」というのは、次が成り立つことが関係しています。

ユークリッドの互除法の原理
自然数 $a,b$ に対し、 ab で割ったときの商を q 、余りを $r \ (\ne 0)$ とする。
このとき、「ab の最大公約数」は、「 br の最大公約数」に等しい。
証明
$a,b$ の最大公約数を G 、 $b,r$ の最大公約数を g とおく。

条件より、 $a=bq+r$ が成り立つ。右辺は g で割り切れるので、 ag で割り切れる。よって、$a,b$ は g で割り切れる。この2つの公約数の最大のものが G なので、\[ G\geqq g \ \cdots (1) \]が成り立つ

$a=bq+r$ から、 $a-bq=r$ も成り立つ。左辺は G で割り切れるので、 rG で割り切れる。よって、 $b,r$ は G で割り切れる。この2つの公約数の最大のものが g なので、\[ g\geqq G \ \cdots (2) \]が成り立つ

(1)(2)より、 $G=g$ となるので、「ab の最大公約数」と「 br の最大公約数」が等しいことがわかる。

【証明終】

これにより、「ab の最大公約数」を求めるには、「b と、『ab で割った余り』との最大公約数」を求めればいい、ということがわかります。

ab は、自然数であればいいので、上で証明した性質を繰り返し用いることもできます。

また、割り切れた場合は、割った数がそのまま最大公約数になることがわかりますね。