スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

最大公約数と最小公倍数

最大公約数 (Greatest Common Divisor; GCD) と最小公倍数 (Least Common Multiple; LCM) のはなし

Tag : 数学

以下、a, b を正整数、gcd(a,b), lcm(a,b) をそれぞれ a と b の最大公約数、最小公倍数とする。
このとき、次が成立することは有名。
a × b = gcd(a,b) × lcm(a,b) …… (*)

人によっては自明でないかもしれないから、私の持っているイメージを簡単に書いておく。

a = 2a1 3a2 5a3 ..
b = 2b1 3b2 5b3 ..

と素因数分解する。ここで、ai, bi0 以上の整数。
もちろん、ある i0 より大きな i では、つねに ai = bi = 0 となっている。

このとき、gcd(a,b) と lcm(a,b) は次のように素因数分解される。
gcd(a,b) = 2min(a1,b1) 3min(a2,b2) 5min(a3,b3) ..
lcm(a,b) = 2max(a1,b1) 3max(a2,b2) 5max(a3,b3) ..


かけあわせると、指数法則より
gcd(a,b) × lcm(a,b)
= 2min(a1,b1) + max(a1,b1) 3min(a2,b2) + max(a2,b2) 5min(a3,b3) + max(a3,b3) ..


もちろん、x + y = max(x,y) + min(x,y) なので、(*) 式を得る。

雑にいえば、素因数を上からすりきり一杯までとったのが LCM で、下から重なる部分だけをとったのが GCD。


正整数 a, G, L が勝手に与えられたとき、gcd(a,b) = G かつ lcm(a,b) = L となる b を見つけることができるか?
という問題について考えてみる。

注意しないといけないのは、
「(*) 式より、b = G × L / a とすればいい」とするのは間違いだということ。
(*) は、a, b, gcd(a,b), lcm(a,b) についての関係式なので、今回のような勝手な G, L に対して使ってはいけない。
実際、a = 6, G = 3, L = 10 とすれば G × L / a = 5 だが、gcd(6,5) = 1 ≠ G である。

しかし、一方で (*) 式は良い必要条件になる。
というのも、gcd(a,b) = G かつ lcm(a,b) = L となる b は、もしあれば b = G × L / a をみたしているはずだから。
( このことから、b は存在すれば唯一であることもわかる。)
なので、この問題に対する 1 つの解答は、

b' = G × L / a を計算してみて、gcd(a,b') = G かつ lcm(a,b') = L となっていれば b = b' である。
そうでなければ、そのような b は存在しない。

となる。 ( もちろん、b' が整数にならなければ直ちに b は存在しないことがわかる。)


余談
b が存在するための、より簡単な必要十分条件はないだろうか?
たとえば、G = gcd(a,b), L = lcm(a,b) なのだから、当然 G は a の約数、L は a の倍数でないといけない。
しかし、この条件だけではまだ反例が作れる。たとえば、a = 3, G = 1, L = 9 など。
解答もとむ。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。