ユークリッドの互除法の謎に迫る

質問

• ユークリッドの互除法についての質問です。計算方法はわかるけど、なぜ計算結果が最大公約数になるのかがわからない。
• 問題集によると、N＝M×ａ＋Lのとき、NとMの最大公約数は、MとLの最大公約数と等しい。なぜそうなるの？
• N＝M×ａ＋LとL＝N－M×ａの関係から、MとLの公約数はNの約数であり、NとMの公約数はLの約数となる。

回答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さん

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