最小公倍数

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

定義

2つ以上の整数 $a_{1},\ldots ,a_{n}$ の最小公倍数とは、 $a_{1},\ldots ,a_{n}$ の公倍数のうち最小の正整数である。

つまり、 $a_{1},\ldots ,a_{n}$ を、素数 (prime) $p$ を用いて

$a_{j}=\varepsilon _{j}\prod _{p:\,\mathrm {prime} }p^{e_{p}(j)}\ \ \ (e_{p}(j)\geq 0,\ \ \varepsilon _{j}=\pm 1)$

と素因数分解したとき、 $a_{1},\ldots ,a_{n}$ の最小公倍数は

$\prod _{p:\,\mathrm {prime} }p^{\max\{e_{p}(1),\ldots ,e_{p}(n)\}}$

で与えられる。

例えば、12 と 16 の最小公倍数は 48 である。

12 = 2²×3¹

16 = 2⁴

48 = 2⁴×3¹

諸概念

公倍数は最小公倍数の倍数である。

証明

$a,b,c,\cdots ,z$ の最小公倍数を $l$ とする． $a,b,c,\cdots ,z$ の一般の公倍数を $m$ とし， $m=ql r,\quad (0<r<l)$ と置く。変形して $r=m-ql$ …① ①右辺は $m$ は $a,b,c,\cdots ,z$ の公倍数、 $l$ も同じく $a,b,c,\cdots ,z$ の公倍数。よって①の左辺 $r$ は $a,b,c,\cdots ,z$ の公倍数になる。しかし $0<r<l$ となり、最小公倍数 $l$ よりも一般公倍数 $r$ が小さく矛盾．すなわち $r=0$ 。よって公倍数 $m=ql$ であり最小公倍数の倍数となっている．(証明終）