最小公倍数

算術と数論において、 ２つの整数aとbの最小公倍数、最低公倍数、または最小公倍数は、通常lcm( a ,  b )と表記され、 aとb の両方で割り切れる最小の正の整数である。^{[1] [2]}整数をゼロで割る方法は定義されていない ため、この定義はaとbが両方ともゼロと異なる場合にのみ意味を持つ。 ^{[3]ただし、} aと 0の唯一の公倍数は 0 であるため、すべてのaについて lcm( a , 0) を 0 と 定義する著者もいる。

2 つの分数の分母の最小公倍数は「最小公分母」(LCD) であり、分数の加算、減算、比較に使用できます。

2つ以上の整数a、b、c、...の最小公倍数は、通常lcm( a、  b、  c 、...)と表記され、 a、b、c、...のそれぞれで割り切れる最小の正の整数として定義されます^[1]

ある数の倍数とは、その数と整数の積です。たとえば、 10 は 5 × 2 = 10 なので 5 の倍数であり、10 は 5 と 2 で割り切れます。10 は 5 と 2 の両方で割り切れる最小の正の整数であるため、5 と 2 の最小公倍数です。同じ原理で、10 は -5 と -2 の最小公倍数でもあります。

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 です。

単純な分数を足し算、引き算、比較する場合、分母の最小公倍数（最小公分母と呼ばれることが多い）が使用されます。これは、各分数がこの分母を持つ分数として表すことができるためです。たとえば、

${\displaystyle {2 \over 21}+{1 \over 6}={4 \over 42}+{7 \over 42}={11 \over 42}}$

ここで分母に 42 が使用されているのは、それが 21 と 6 の最小公倍数だからです。

機械に、それぞれm 個とn 個の歯を持つ2 つのかみ合った歯車があり、最初の歯車の中心から 2 番目の歯車の中心まで線分が引かれて、歯車がマークされているとします。歯車が回転し始めると、線分を再調整するために最初の歯車が完了する必要がある回転数は、 を使用して計算できます。最初の歯車は、再調整のために 回転する必要があります。その時点で、2 番目の歯車は 回転していることになります。 ${\displaystyle \operatorname {lcm} (m,n)}$${\displaystyle \operatorname {lcm} (m,n) \over m}$${\displaystyle \operatorname {lcm} (m,n) \over n}$

ある恒星の周りを回る 3 つの惑星があり、各惑星が軌道を一周するのにそれぞれl、m、n単位の時間がかかるとします。 l、m、nは整数とします。惑星が最初の直線的な一列の後に恒星の周りを回り始めたと仮定すると、すべての惑星は単位時間後に再び直線的な一列になります。この時点で、1 番目、2 番目、3 番目の惑星はそれぞれ、恒星の周りを一周します。[ ^5]${\displaystyle \operatorname {lcm} (l,m,n)}$${\displaystyle \operatorname {lcm} (l,m,n) \over l}$${\displaystyle \operatorname {lcm} (l,m,n) \over m}$${\displaystyle \operatorname {lcm} (l,m,n) \over n}$

最小公倍数を計算する方法はいくつかあります。

最小公倍数は最大公約数（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」と 1 つの「3」を共有しています。

最小公倍数 = 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 {1}{3}},{\tfrac {2}{5}}\right)&=2^{1}3^{0}5^{0}=2,\\[8pt]{\tfrac {1}{6}}&=2^{-1}3^{-1},&{\tfrac {3}{4}}&=2^{-2}3^{1},&\gcd \left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2^{-2}3^{-1}={\tfrac {1}{12}},&\operatorname {lcm} \left({\tfrac {1}{6}},{\tfrac {3}{4}}\right)&=2^{-1}3^{1}={\tfrac {3}{2}}.\end{aligned}}}$

正の整数は、割り切れる度合いによって部分的に順序付けられることがあります。つまり、a がb を割り切れる場合（つまり、bがaの整数倍の場合）、a ≤ b（または同等に、b ≥ a）と書きます。（通常の絶対値に基づく ≤ の定義はここでは使用されないことに注意してください。）

この順序付けでは、正の整数は格子になり、meet はgcd によって与えられ、join はlcm によって与えられます。証明は簡単ですが、少し面倒です。つまり、lcm と gcd が meet と join の公理を満たしていることを確認するだけです。lcm と gcd をこのより一般的なコンテキストに置くと、それらの間の双対性が確立されます。

整数変数、gcd、lcm、≤、≥ を含む式が真である場合、gcd を lcm に置き換え、≥ を ≤ に置き換えて得られる式も真です。 (≤ は除算として定義されていることに注意してください)。

次の双対式のペアは、一般的な格子理論的恒等式の特殊なケースです。

この格子は分配的であることも示されている^[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]}

最小公倍数は、一般に可換環上で次のように定義できます。

aとb を可換環Rの元とする。aとbの公倍数とは、 aとb の両方がm を割り切るようなRの元 m のことである（つまり、ax = mかつby = mとなるようなRの元xとy が存在する）。aとbの最小公倍数とは、 aとbの他の任意の公倍数nに対してm がn を割り切る という意味で最小となる公倍数のことである。

一般に、可換環の2つの元は、最小公倍数がないか、1つ以上ある。しかし、同じ元ペアの任意の2つの最小公倍数は、関連元である。^[10]一意の因数分解領域では、任意の2つの元に最小公倍数がある。^[11]主イデアル領域では、 aとbの最小公倍数は、 aとbによって生成されるイデアルの共通部分の生成元として特徴付けることができる^[10]（イデアルの集合の共通部分は常にイデアルである）。

• 異常なキャンセル
• 互いに素な整数
• チェビシェフ関数

• バートン、デイビッド・M（1970年）。『環と理想論入門』。マサチューセッツ州レディング：アディソン・ウェスレー。ISBN 978-0-201-00731-2。
• クランドール、リチャード、ポメランス、カール（2001）、素数：計算の観点、ニューヨーク：シュプリンガー、ISBN 0-387-94777-9
• グリエ、ピエール・アントワーヌ (2007)。抽象代数(第 2 版)。ニューヨーク州ニューヨーク州：スプリンガー。ISBN 978-0-387-71568-1。
• ハーディ、GH; ライト、EM (1979)、数論入門（第5版）、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-853171-5
• ランドー、エドマンド（1966）、初等数論、ニューヨーク：チェルシー
• ロング、カルビン T. (1972)、初等数論入門(第 2 版)、レキシントン: DC ヒース アンド カンパニー、LCCN  77-171950
• ペットフレッツォ、アンソニー J.; バーキット、ドナルド R. (1970)、数論の要素、イングルウッド クリフス:プレンティス ホール、LCCN  77-81766