最小公倍数

2 つの整数aとbの最小公倍数は lcm( a , b ) と表記されます。^{[ 1 ]}古い教科書の中には [ a , b ] を使用するものもあります。^{[ 3 ] [ 4 ]}

${\displaystyle \operatorname {lcm} (4,6)}$

4の倍数は次のとおりです。

${\displaystyle 4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,...}$

6の倍数は次のとおりです。

${\displaystyle 6,12,18,24,30,36,42,48,54,60,66,72,...}$

4と6の公倍数は、両方のリストに含まれる数です。

${\displaystyle 12,24,36,48,60,72,...}$

In this list, the smallest number is 12. Hence, the least common multiple is 12.

Suppose there are two meshing gears in a machine, having m and n teeth, respectively, and the gears are marked by a line segment drawn from the center of the first gear to the center of the second gear. When the gears begin rotating, the number of rotations the first gear must complete to realign the line segment can be calculated by using ${\displaystyle \operatorname {lcm} (m,n)}$. The first gear must complete ${\textstyle {\frac {\オペレータ名 {lcm} (m,n)}{m}}}$ rotations for the realignment. By that time, the second gear will have made ${\textstyle {\frac {\オペレータ名 {lcm} (m,n)}{n}}}$ rotations.

Suppose there are three planets revolving around a star that take l, m, and n units of time, respectively, to complete their orbits. Assume that l, m, and n are integers. Assuming the planets started moving around the star after an initial linear alignment, all the planets attain a linear alignment again after ${\displaystyle \operatorname {lcm} (l,m,n)}$ units of time. At this time, the first, second and third planet will have completed ${\textstyle {\frac {\オペレータ名 {lcm} (l,m,n)}{l}}}$, ${\textstyle {\frac {\オペレータ名 {lcm} (l,m,n)}{m}}}$ and ${\textstyle {\frac {\オペレータ名 {lcm} (l,m,n)}{n}}}$ orbits, respectively, around the star.^[5]

The least common multiple can be computed from the greatest common divisor (gcd) with the formula

${\displaystyle \operatorname {lcm} (a,b)={\frac {|ab|}{\gcd(a,b)}}.}$

To avoid introducing integers that are larger than the result, it is convenient to use the equivalent formulas

${\displaystyle \operatorname {lcm} (a,b)=|a|\,{\frac {|b|}{\gcd(a,b)}}=|b|\,{\frac {|a|}{\gcd(a,b)}},}$

where the result of the division is always an integer.

These formulas are also valid when exactly one of a and b is 0, since gcd(a, 0) = |a|. However, if both a and b are 0, these formulas would cause division by zero; so, lcm(0, 0) = 0 must be considered as a special case.

To return to the example above,

${\displaystyle \operatorname {lcm} (21,6)=6\times {\frac {21}{\gcd(21,6)}}=6\times {\frac {21}{3}}=6\times 7=42.}$

最大公約数を計算するためのユークリッドの互除法のように、素因数分解を必要としない高速アルゴリズムが存在します。非常に大きな整数については、関連する 3 つの演算 (乗算、最大公約数、除算) に対してさらに高速なアルゴリズムがあります。高速乗算を参照してください。これらのアルゴリズムは、同じ大きさの因数に対してより効率的であるため、上記の例のように、最小公倍数の最大の引数を引数の最大公約数で割る方が効率的です。

一意因数分解定理は、 1より大きいすべての正の整数は、素数の積としてただ1通りの方法で表すことができることを示しています。素数は、合成数を構成する原子的な要素と考えることができます。

例えば：

${\displaystyle 90=2^{1}\cdot 3^{2}\cdot 5^{1}=2\cdot 3\cdot 3\cdot 5.}$

ここで、合成数90は、素数2の原子1個、素数3の原子2個、および素数5の原子1個から構成されている。

この事実は、一連の数値の最小公倍数を求める際に利用できます。

例：lcm(8,9,21)

それぞれの数を因数分解し、素数の累乗の積として表してください。

${\displaystyle {\begin{aligned}8&=2^{3}\\9&=3^{2}\\21&=3^{1}\cdot 7^{1}\end{aligned}}}$

最小公倍数は、各素数の最高次数を掛け合わせた積になります。3 つの素数 2、3、7 の最高次数は、それぞれ 2³ ^、 3² ^、 7¹^です。したがって、

${\displaystyle \operatorname {lcm} (8,9,21)=2^{3}\cdot 3^{2}\cdot 7^{1}=8\cdot 9\cdot 7=504.}$

この方法は、最大公約数に還元するほど効率的ではありません。なぜなら、整数因数分解のための一般的な効率的なアルゴリズムは知られていないからです。

同様の方法は、ベン図を用いて以下のように示すこともできます。各円には2つの数の素因数分解を示し、共通するすべての因数を交差部分に示します。最小公倍数は、図中のすべての素数を掛け合わせることで求められます。

以下に例を示します。

48 = 2 × 2 × 2 × 2 × 3、

180 = 2 × 2 × 3 × 3 × 5、

共通する「2」が2つと「3」が1つある。

最小公倍数 = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

最大公約数 = 2 × 2 × 3 = 12

積 = 2 × 2 × 2 × 2 × 3 × 2 × 2 × 3 × 3 × 5 = 8640

これは最大公約数（gcd）にも適用できますが、ベン図のすべての数を掛け合わせる代わりに、共通部分にある素因数だけを掛け合わせます。したがって、48と180の最大公約数は2  ×  2  ×  3  =  12です。

算術の基本定理によれば、1より大きいすべての整数は、因数の位数を除いて、素数の積として一意に表すことができる。

${\displaystyle n=2^{n_{2}}3^{n_{3}}5^{n_{5}}7^{n_{7}}\cdots =\prod _{p}p^{n_{p}},}$

ここで、指数n ₂、n ₃、 ... は非負の整数です。たとえば、84 = 2 ² 3 ¹ 5 ⁰ 7 ¹ 11 ⁰ 13 ⁰ ...

2 つの正の整数が与えられた場合${\textstyle a=\prod _{p}p^{a_{p}}}$そして${\textstyle b=\prod _{p}p^{b_{p}}}$それらの最大公約数と最小公倍数は、次の式で与えられる。

${\displaystyle \gcd(a,b)=\prod _{p}p^{\min(a_{p},b_{p})}}$

そして

${\displaystyle \operatorname {lcm} (a,b)=\prod _{p}p^{\max(a_{p},b_{p})}.}$

以来

${\displaystyle \min(x,y)+\max(x,y)=x+y,}$

これにより

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

実際、負の指数を許容すれば、すべての有理数は素数の積として一意に表すことができます。このようにすると、上記の公式は依然として有効です。例えば、次のようになります。

${\displaystyle {\begin{aligned}4&=2^{2}3^{0},&6&=2^{1}3^{1},&\gcd(4,6)&=2^{1}3^{0}=2,&\operatorname {lcm} (4,6)&=2^{2}3^{1}=12.\\[8pt]{\tfrac {1}{3}}&=2^{0}3^{-1}5^{0},&{\tfrac {2}{5}}&=2^{1}3^{0}5^{-1},&\gcd \left({\tfrac {1}{3}},{\tfrac {2}{5}}\right)&=2^{0}3^{-1}5^{-1}={\tfrac {1}{15}},&\operatorname {lcm} \left({\tfrac \end{aligned}}$

正の整数は、割り切れるかどうかによって部分的に順序付けすることができます。aがbを割り切る場合（つまり、bがaの整数倍である場合）、a ≤ b（または同等に、b ≥ a）と表記します。（ここでは、通常の大きさに基づく≤の定義は使用しません。）

この順序付けの下では、正の整数は格子となり、その交わりは最大公約数で、結合は最小公倍数で与えられる。証明はやや面倒ではあるが、単純明快である。最小公倍数と最大公約数が交わりと結合の公理を満たすことを確認するだけでよい。最小公倍数と最大公約数をこのより一般的な文脈に置くと、両者の間に双対性が確立される。

整数変数、最大公約数、最小公倍数、≤、≥ を含む式が真である場合、最大公約数を最小公倍数と入れ替え、≥ を ≤ に入れ替えて得られる式も真である。（≤ は割り切れるという意味で定義されていることを思い出してください。）

以下の双対式のペアは、一般的な格子理論上の恒等式の特殊な場合である。

また、この格子は分配的であることも示せる^{[ 6 ]}。つまり、lcmはgcdに対して分配的であり、gcdはlcmに対して分配的である。

${\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c)),}$

${\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c)).}$

このアイデンティティは自己双対性を持つ。

${\displaystyle \gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (b,c),\operatorname {lcm} (a,c))=\operatorname {lcm} (\gcd(a,b),\gcd(b,c),\gcd(a,c)).}$

• D をω ( D )個の異なる素数の積とする(つまり、Dは平方因子を持たない)。

そして^{[ 7 ]}

${\displaystyle |\{(x,y)\;:\;\operatorname {lcm} (x,y)=D\}|=3^{\omega (D)},}$

ここで、絶対線 || は集合の濃度を表します。

• どれも${\displaystyle a_{1},a_{2},\ldots ,a_{r}}$がゼロの場合、

${\displaystyle \operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2},\ldots ,a_{r-1}),a_{r}).}$^{[ 8 ] [ 9 ]}