最大公約数から最小公倍数

質問

ユークリッドの互除法についてなんですが、あるサイトでの公式？というか、
例》ａとｂの最大公約数を求めろ。
式がr(余り)＝a-(a÷b)b
それはわかったんです。
ですが、最大公約数から最小公倍数を出すという作業がわかりません。それと、手でやっているのでコンピューターは使っていません。
わかりやすく教えてください！

回答No.3

kukineko · ベストアンサー

１です。１点訂正です。
＞（Ａ，Ｂは互いに素の素数）
は（Ａ，Ｂは互いに素の整数）です^^;

＞では、(a)２０８と(b)１１７の場合。
＞最大公約数が１３なので、
＞ａ＝Ｇ×Ａとは、２０８＝１３×Ａ＝１６ということで良いんですか？
＞そして、
＞最小公倍数Ｌ＝a×b÷最大公倍数Ｇ
＞ということで、Ｌ＝２０８×１１７÷１３＝１８７２
＞で良いんですか？

そのとおりです。
普通通り？に素因数分解で最小公倍数を求めてもらっても１，８７２になると思いますよ。
２０８＝１３×１６
１１７＝１３×９
最小公倍数は１３×９×１６＝１，８７２
となります。

お礼

大変わかりやすく、参考になりました。
有難うございます（＾▽＾）♪

回答No.2

ka1234

こんにちは。

＞最大公約数から最小公倍数を出すという作業がわかりません。

これは互除法とは関係ないと思います。
整数A, Bについて、ユークリッドの互除法により最大公約数Gが求まったとすると、
A=Ga かつ B=Gb （aとbは互いに素）と置ける。
するとAとBの最小公倍数Lは

L=Gab・・・[1]

として求まります。なぜ、[1]で求まるかというと、最小公倍数というのは、「AとBの素因数を全て拾い上げる」ということですので、共通因数を全てGとして引き抜いておくと、あとは共通しないaとbだけ残り、それを掛け算すれば求まる訳です。

回答No.1

kukineko

ａ，ｂの最大公約数をＧとすると
ａ＝Ｇ×Ａ
ｂ＝Ｇ×Ｂ
（Ａ，Ｂは互いに素の素数）
と表示出来ます。
最小公倍数はＧ×Ａ×Ｂですから
Ｇ×Ａ×Ｂ＝（Ｇ×Ａ）×（Ｇ×Ｂ）／Ｇ＝ａ×ｂ／Ｇ
となります。

補足

では、(a)２０８と(b)１１７の場合。
最大公約数が１３なので、
ａ＝Ｇ×Ａとは、２０８＝１３×Ａ＝１６ということで良いんですか？
そして、
最小公倍数Ｌ＝a×b÷最大公倍数Ｇ
ということで、Ｌ＝２０８×１１７÷１３＝１８７２
で良いんですか？