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

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

No.3 ベストアンサー 回答者： kukineko 回答日時： 2007/10/21 08:10

１です。

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

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

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

この回答へのお礼

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

お礼日時：2007/10/21 10:01

No.2 回答者： ka1234 回答日時： 2007/10/20 15:02

こんにちは。

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

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

L=Gab・・・[1]

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

No.1 回答者： kukineko 回答日時： 2007/10/20 14:56

ａ，ｂの最大公約数をＧとすると

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

この回答への補足

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

補足日時：2007/10/20 18:15