ユークリッドの互除法について（高１数学）

質問

いつも大変お世話になっております。

ユークリッドの互除法についての質問です。

計算のやり方は知っているので、答えは出せるのですが、なぜそのように計算すると計算結果が最大公約数になるのかがよくわかりません。

私の持っている問題集には、以下のように解説があります。

　「N＝M×ａ＋Lのとき、NとMの最大公約数は、MとLの最大公約数と等しい。

　　理由は、
　　N＝M×ａ＋Lなので、MとLの公約数は、Nの約数　・・・（１）
　　L＝N－M×ａなので、NとMの公約数は、Lの約数　・・・（２）」
とあります。
　（１）、（２）のそれぞれは理解できるのですが、その先がよくわかっておりません。

　アドバイスいただけると助かります。
　よろしくお願い致します。

回答No.3

tmpname · ベストアンサー

aとbの最大公約数というのは、文字通り「aとbの公約数のうち、最大のもの」です。で、aとbとの公約数というのは、「aの約数でもありbの約数でもある数」の事ですね。

(1)で言っているのは、「MとLの公約数は、NとMとの公約数である」、つまり「MとLの公約数であって、NとMとの公約数『でない』ものはない」、という事。

(2)はその逆で、「NとMとの公約数は、MとLの公約数である」、つまり「NとMの公約数であって、MとLとの公約数『でない』ものはない」、という事。

両方あわせて、「NとMとの公約数全体は、MとLとの公約数全体と一致する」と言っているのであって、で先程の「最大公約数とは何だっけ？」というのを思い出せば分かるはずです。

お礼

tmpnameさん

　ご回答いただきありがとうございました。
　納得いたしました。

回答No.2

hugen

(NとMの最大公約数) = g　と　すると
L = N -M-M-・・・-M =(gの倍数)-(gの倍数) = (gの倍数)
M = (gの倍数)
(MとLの最大公約数) = G　　とすると ,　　G≧g 　
また、
N = L + M + M + ・・・+ M = (Gの倍数) + (Gの倍数) = (Gの倍数)
M = (Gの倍数)　　より　、
G = (NとMの公約数)
(NとMの最大公約数)≧(NとMの公約数) だから　、　　g≧G
以上より　、　　　G≧g≧G

お礼

hugenさん

　ご回答いただきありがとうございました。
　納得いたしました。

回答No.1

Tacosan

「その先がよくわかっておりません」の「その先」というのは, 「NとMの最大公約数は、MとLの最大公約数と等しい」というところですか? それとも, そこは分かるけど「ユークリッドの互除法で最大公約数が求まる」というところが分からないということですか?

お礼

Tacosanさん

　お時間いただきありがとうございました。

補足

Tacosanさん

　言葉足らずで申し訳ございません。
　（１）と（２）から「NとMの最大公約数は、MとLの最大公約数と等しい」となるところが理解できていない状況です。

　よろしくお願いします。