最大公約数と最小公倍数

AtCoderのPythonのバージョンは3.8.2なので、最小公倍数を求める関数が標準ライブラリに存在しない。

そこで以下のようなコードが推奨されているのだが、今回はなぜそれでうまくいくのかを解説する。

def my_lcm(x, y):
    return (x * y) // math.gcd(x, y)

上のコードは数式で書くと以下のようになる。

$lcm(x,y)=\frac{x \times y}{gcd(x, y)}$

つまり2つの値の最小公倍数( $lcm$ )を求めたければ、それらの積を最大公約数( $gcd$ )で割ればよいということ。
これは $gcd$ と $lcm$ が図のような関係になっていることから導くことができる。

ある数を素因数分解したとき、同じ素数についてはひとまとめにして素因数のかたまりと呼ぶことにする。
上の例では60を2と3と5の素因数のかたまりに分解している。

2つの数の各素因数のかたまりについて、指数が大きい方の積が最小公倍数。小さい方の積が最大公約数になる。

これは言い換えると2つの数の各素因数のかたまりについて、必ず一方が最小公倍数に、他方が最大公約数に使われているということ。

$lcm(x, y) \times gcd(x, y)= x \times y$

よって2つの数の積を $gcd$ で割れば $lcm$ が残る。

ちなみに

$lcm(x,y)=\frac{x \times y}{gcd(x, y)}$

この式は3つ以上の数の最小公倍数については一般には成り立たない。真ん中の素因数のかたまりも残ってしまうため。