【質問】数学(高校):ユークリッドの互除法はどういう原理のものですか?

〔質問〕
ユークリッドの互除法はどういう原理のものですか?
何をやっているのかがわかりません
〔回答〕
ユークリッドの互除法の原理は、最大公約数を求める際に「複雑な2数の比較から、より簡単な2数の比較に落とし込んでいる」というものです。

(※ 以下、文章ではわかりづらい場合、動画解説はこちら
例えば、以下の「56と21の最大公約数を求めたい」という場合、56も21も何かの倍数なのであれば、黄色の部分(56と、21の2個分との差)も同じく「それ」の何個か分になっているはずです。
ということは、わざわざ「56と21」という大きめの数で考えなくても、「21と黄色の14」とで考えれば「赤1個分」を求めることはできる、ということになります。
これが上記の「複雑な2数の比較から、より簡単な2数の比較に落とし込んでいる」というものです。

 
 
また、この「差の部分が答えの何個か分になっている」という原理を踏まえると、例えば「24と36」の場合も、必ずしも 36÷24 の順の計算をしなくても、「24は36から-12したもの」という見方で「24と-12」の比較をしてもよく、
さらに、この「-12」も、「赤が何個分か」という見方をする上では、勝手に絶対値の「12」として扱ってもいいことになります。

 
 
互除法の基本問題であれば具体的な2数で最大公約数を求めるものが出題されるため、「大きい方÷小さい方」ということをしていけばそれで十分ですが、文字式で与えられた場合はこの原理が本領を発揮します。

例えば「2n+1 と n+3」の比較を行う際、2n+1=(n+3)×2-5 ということで「余りが-5(?)」ということになりますが、これも上記の「24と36」の例と同様で別に「5」として扱ってよく、よって「n+3 と 5」に話を落とし込んで構いませんし、
また、「2n+1 も、n+3 も、5 も何かの倍数」ということであれば、絶対に「n+3 と 5」にしないといけないわけでもなく、「2n+1 と 5」という比較の仕方をしても問題ありません。
(上記の「56と21」の場合も「21と14」の比較ではなく「56と21」の比較にしても問題はない)

 

※ 理解を優先するために、あえて大雑把に書いてある場合があります

 
アンケートへのご協力をお願いします(所要2~3分)
「将来設計・進路」に関するアンケートを実施しています。ご協力いただける方はこちらよりお願いします
(Googleフォームにアクセスします)

当サイト及びアプリは、上記の企業様のご協力、及び、広告収入により、無料で提供されています