最小公倍数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

移動：案内, 検索

最小公倍数（さいしょうこうばいすう、英: least common multiple）とは、0 ではない複数の整数の公倍数のうち最小のものをさす。たびたび、L.C.M.等の省略形で記述される。

[編集] 定義

２つ以上の整数 $a_1,\ldots, a_n$ の最小公倍数とは、 $a_1,\ldots, a_n$ の公倍数のうち最小の正整数である。

つまり、 $a_1,\ldots, a_n$ を

$a_j = \varepsilon_j\prod_{p;\operatorname{prime}}p^{e_p(j)}\ \ \ (e_p(j)\ge 0,\ \ \varepsilon_j=\pm 1)$

と素因数分解したとき、 $a_1,\ldots, a_n$ の最小公倍数は

$\prod_{p;\operatorname{prime}}p^{\max\{e_p(1),\ldots,e_p(n)\}}$

で与えられる。

例えば、30 と 42 の最小公倍数は 210 である。

[編集] 諸概念

正整数 a、b に対して、a と b の最大公約数 $\scriptstyle\operatorname{gcd}(a,\ b)$ と最小公倍数 $\scriptstyle\operatorname{lcm}(a,\ b)$ との間には

$\operatorname{gcd}(a,\ b)\cdot\operatorname{lcm}(a,\ b) = ab$

という関係がある。

しかし、この関係式は３つ以上の正整数に対しては一般には成立しない。例えば、 $a=2$ 、 $b=6$ 、 $c=15$ とすると $\scriptstyle\operatorname{gcd}(a,\ b,\ c) = 1$ 、 $\scriptstyle\operatorname{lcm}(a,\ b,\ c) = 30$ であるが、 $abc=180$ である。