読者です 読者をやめる 読者になる 読者になる

ブログの名前なんて適当で良いのでは

説明を求めるな、記事を読め

最大公約数はユークリッド互除法、じゃあ最小公倍数は?

はてなブログ初回の記事にあまり良いのが思いつかなかったので最近知って驚いたことについて書くことにした。

 

 散々、小学校などで習ってきた最小公倍数(LCM:Least Common Multiple)という概念。これと対をなすような最大公約数(GCD:Greatest Common Divisior)という概念もある。

 情報工学の分野の勉強をしていて、試行割り算法や、ユークリッドの互除法などにより最大公約数を高速に求めるアルゴリズムは知っていた。そこで最小公倍数を高速に求めるアルゴリズムについて調べてみた。

 

結論:任意の整数a,bにおいて最小公倍数を求めるアルゴリズムは以下である。

LCM(a,b) = ab/GCD(a,b)

 

あまりに簡素だが、今まで知らなかったが故に意外な衝撃だった。みんな普通は知っている公式だったのだろうか・・・。

 

簡単だが証明しておくと、

a=a’g , b=b’g とおく.

( a’ , b’ は互いに素)LCM(a,b)=a’b’g だから ab=GCD(a,b)L(a,b) 

ということらしい。