【標準】ユークリッドの互除法の原理
🕒 2016/05/01
🔄 2023/05/01
【基本】ユークリッドの互除法の使い方 で書いた通り、大きな2つの数の最大公約数を求めるためには、ユークリッドの互除法を用いて、余りとの最大公約数を考えていけばいいんでしたね。
しかし、なぜそれでいいんでしょうか。ここでは、ユークリッドの互除法の原理について説明していきます。教科書にも書いてある内容ですが、証明は少し分かりにくいかもしれません。
「余りとの最大公約数を考えればいい」というのは、次が成り立つことが関係しています。
ユークリッドの互除法の原理
自然数 $a,b$ に対し、 a を b で割ったときの商を q 、余りを $r \ (\ne 0)$ とする。
このとき、「a と b の最大公約数」は、「 b と r の最大公約数」に等しい。
このとき、「a と b の最大公約数」は、「 b と r の最大公約数」に等しい。
証明
$a,b$ の最大公約数を G 、 $b,r$ の最大公約数を g とおく。
条件より、 $a=bq+r$ が成り立つ。右辺は g で割り切れるので、 a も g で割り切れる。よって、$a,b$ は g で割り切れる。この2つの公約数の最大のものが G なので、\[ G\geqq g \ \cdots (1) \]が成り立つ
$a=bq+r$ から、 $a-bq=r$ も成り立つ。左辺は G で割り切れるので、 r も G で割り切れる。よって、 $b,r$ は G で割り切れる。この2つの公約数の最大のものが g なので、\[ g\geqq G \ \cdots (2) \]が成り立つ
(1)(2)より、 $G=g$ となるので、「a と b の最大公約数」と「 b と r の最大公約数」が等しいことがわかる。
【証明終】
条件より、 $a=bq+r$ が成り立つ。右辺は g で割り切れるので、 a も g で割り切れる。よって、$a,b$ は g で割り切れる。この2つの公約数の最大のものが G なので、\[ G\geqq g \ \cdots (1) \]が成り立つ
$a=bq+r$ から、 $a-bq=r$ も成り立つ。左辺は G で割り切れるので、 r も G で割り切れる。よって、 $b,r$ は G で割り切れる。この2つの公約数の最大のものが g なので、\[ g\geqq G \ \cdots (2) \]が成り立つ
(1)(2)より、 $G=g$ となるので、「a と b の最大公約数」と「 b と r の最大公約数」が等しいことがわかる。
【証明終】
これにより、「a と b の最大公約数」を求めるには、「b と、『a を b で割った余り』との最大公約数」を求めればいい、ということがわかります。
a と b は、自然数であればいいので、上で証明した性質を繰り返し用いることもできます。
また、割り切れた場合は、割った数がそのまま最大公約数になることがわかりますね。
