ユークリッド互除法

質問

２９４４１と３２９３４の最大公約数をユークリッド互除法で求めて答えが１とでました。さらに最小公倍数を求めろとあるのですが、ユークリッド法でどうやって最小公約数を求めるのですか？

回答No.2

oyaoya65

ユークリッドの互除法で
29441と32934の最大公約数GCDがでてきませんでしたが？

余りがゼロになる直前の余りが最大公約数GCDですね。
これが
＞１とでました。
ということは計算間違いか、ユークリッド互除法を正しく理解されていないようですね。参考URLで復習してみてください。

GCD=499とでてくれば計算があっているということです。
a=29441=GCDx59
b=32934=GCDx2x3x11
最小公倍数GCM=ab/GCD=29441x32934/499=59x2x3x11
となりますね。

GCMのあとの計算はできますね。

参考URL：

http://tambara.ms.u-tokyo.ac.jp/oshima050812.pdf

回答No.1

rabbit_cat

GCM(a,b) = a*b/GCD(a,b)
です。

お礼

回答ありがとうございます。すいませんこれがどういう意味かわからないのですが・・・