最小公倍数

例えば、2と7の最小公倍数は14である。

最も簡単な求め方は、両者の積と、両者の最大公約数との商である。つまり二つの自然数aとbに対する最大公約数をgcd(a,b)とすると、最小公倍数はa×b÷gcd(a,b)である。

最大公約数はユークリッドの互除法を応用すると桁数が多いものも比較的簡単に求めることができるので、これを利用すればコンピュータプログラムでも簡単に最小公倍数を算出できる。

lcm.c (C言語による例)