最小公倍数

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,...}$

このリストの中で最小の数は12です。したがって、最小公倍数は12です 。

機械に噛み合う2つの歯車があり、それぞれ歯数がmとnであるとします。歯車は、最初の歯車の中心から2番目の歯車の中心まで引かれた線分でマークされています。歯車が回転し始めると、線分を再び合わせるために最初の歯車が完了する必要のある回転数は、次の式を使用して計算できます。${\displaystyle \operatorname {lcm} (m,n)}$最初のギアは完了する必要があります${\textstyle {\frac {\オペレータ名 {lcm} (m,n)}{m}}}$再調整のための回転。その時点で、2速ギアは${\textstyle {\frac {\オペレータ名 {lcm} (m,n)}{n}}}$回転。

恒星の周りを公転する3つの惑星があり、それぞれの公転周期はl、m、n単位であるとします。l 、m、nは整数とします。惑星が最初に直線状に並んだ後、恒星の周りを動き始めたと仮定すると、すべての惑星は 1秒後に再び直線状に並びます。${\displaystyle \operatorname {lcm} (l,m,n)}$時間の単位。この時点で、第１、第２、第３惑星は${\textstyle {\frac {\オペレータ名 {lcm} (l,m,n)}{l}}}$、${\textstyle {\frac {\オペレータ名 {lcm} (l,m,n)}{m}}}$そして${\textstyle {\frac {\オペレータ名 {lcm} (l,m,n)}{n}}}$それぞれ恒星の周りを公転する。^{[ 5 ]}

最小公倍数は、最大公約数(gcd) から次の式で計算できます。

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

結果よりも大きな整数を導入することを避けるために、同等の式を使用すると便利です。

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

除算の結果は常に整数となる。

これらの式は、 aとbのうち一方だけが0の場合にも有効です。なぜなら、gcd( a , 0) = | a |だからです。ただし、 aとbの両方が0の場合は、また、bが0の場合、これらの式はゼロ除算を引き起こします。したがって、lcm(0, 0) = 0 は特別なケースとして考慮する必要があります。

上記の例に戻ると、

${\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 ]}