いきなり結論から入るが、2つの整数a, bの最小公倍数lcm(a, b)は次のようにして求めることができる。
$$lcm(a, b) =\frac{ab}{gcd(a,b)} $$
ここでgcd(a, b)とは、aとbの最大公約数のことである。
証明
d =gcd(a,b)とし、a = a’d, b = b’d とする。このときgcd(a’, b’) = 1である。
そうすると、lcm(a, b) = a’b’dであるから
$$lcm(a, b) =\frac{a}{d}× \frac{b}{d}×d =\frac{ab}{d} $$
となる(証明終)。
具体的な数値をいれて考える
たとえばa = 84, b = 90の場合について考えてみる。このときaとbを素因数分解すると、
a = 2・2・3・7
b = 2・３・3・5
であるから、d = gcd(a, b) = 2×3 = 6となる。よって
a’ = 2×7 = 14 (a = 14×6)
b’ = 3×5 = 15 (b = 15×6)
となる。このときたしかにgcd(14, 15) = 1である。
最小公倍数lcm(a, b)とは、aで割ってもbで割っても余りが出ない数の中で最小のものであるから、aの素因数(2,2,3,7)とbの素因数(2,3,3,5)を全てかけて、同じ数を二乗している部分を一乗にしてやればもとめることができる。
(2×2×3×7) ×(2×3×3×5) = ｛(2×7)×(3×5)｝×(2×3)2となるから、これを2×3で割ってやることにより、lcm(a, b) =(2×7)×(3×5)×(2×3) ＝1260となる。ここで
(2×7) = a’
(3×5) = b’
(2×3) = d
であるから、lcm(a, b) = a’b’dとなっている。これを変形すれば、確かに
$$lcm(a, b) =\frac{a}{d}× \frac{b}{d}×d =\frac{ab}{d} $$
となる。実際に数値を入れて計算してみると、lcm(a,b) = (84×90)/6 = 1260 となる。
この計算のいいところ
この計算式を用いると、gcd(a,b)さえわかれば、コンピュータで簡単に計算することができる。
素因数分解によってlcm(a, b)を求めることもできるが、素因数分解はコンピュータにとって非常に難しい処理なので、数字が大きくなるとものすごく時間がかかってしまう。
一方、gcd(a, b)を用いて計算する場合、簡単な除算でlcm(a, b)を求めることができるので、とても高速に最小公倍数を求めることができる。
gcd(a, b)もユークリッド互除法というアルゴリズムを用いれば、高速に計算することができるので、「gcd(a,b)さえわかれば」の部分が問題になることはない。詳しくは別の記事に書いたので、そちらを見てほしい。
pyhonによる最小公倍数計算の実装
最小公倍数計算を行うための、pythonコードを掲載する。
【入力コード】
def gcd(a,b): //解説1 r = a % b while r != 0: a = b b = r r = a % b return b def lcm(a, b): //解説2 return (a*b)//gcd(a,b)) print("lcm(86,90) = ", + lcm(84,90))
【出力結果】
lcm(86,90) = 1260
「解説1」の部分は、ユークリッド互除法によるa,bの最大公約数gcd(a,b)を求める関数の定義である。詳しくはこちら。
最初にgcd(a,b)の計算を定義したら、あとは「(a×b)÷gcd(a,b)」とpythonコードで書かくだけ(解説2の部分)。
ユークリッド互除法の部分も含めて、コード全体を眺めてみると、計算のほとんどが除算である。先にも述べたように素因数分解などの重い処理が含まれていない。ユークリッド互除法の計算量は O(log n)であるから、これも大して重い処理ではない。gcd(a,b)やlcm(a,b)の計算はかなり高速に行えることがわかる。
どこで最小公倍数の計算を使うか
最小公倍数を高速に求められたとして、どこで使うのか。一つ例を挙げると、RSA暗号の処理に用いる。lcm(p-1,q-1)のという計算が必要になるので、この時に用いる。
RSA暗号ではp,qは500ビット以上のすごく大きな数となるため、このような高速なアルゴリズムを使う必要がある。