🏠 Home / 数学A / 整数の性質 / ユークリッドの互除法

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

【基本】ユークリッドの互除法の使い方 で書いた通り、大きな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 は、自然数であればいいので、上で証明した性質を繰り返し用いることもできます。

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

関連するページ

YouTubeもやってます

チャンネル登録はコチラから (以下は、動画のサンプルです)
慶應義塾大学薬学部2024年度数学第1問5 同志社大学文系2024年度数学第1問3 昭和大学医学部I期2024年度数学第2問 兵庫医科大学2024年度数学第3問 共通テスト2B2024年度第3問2のヒントについて 久留米大学医学部推薦2024年度数学第4問