最小公倍数

Smallest positive number divisible by two integers

{2, 3, 4, 5, 7}のすべての部分集合の最小公倍数を示すベン図

算術と数論において、2つの整数aとbの最小公倍数( LCM )、最小公倍数、または最小公倍数( SCM ) は、通常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の倍数です。5 × 2 = 10なので、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個の歯を持つ2 つの歯車が噛み合っており、1 つ目の歯車の中心から 2 つ目の歯車の中心まで線分が引かれているとします。歯車が回転し始めると、線分が再び揃うまでに 1 つ目の歯車が何回転しなければならないかは、 を用いて計算できます。1 つ目の歯車は、再び揃うまでに 回転する必要があります。その時までに、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番目の惑星はそれぞれl 、 m、n単位の公転周回を完了していることになる。^[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 に、≥ を ≤ に置き換えて得られる式も真です。 (≤ は割り算として定義されていることに注意してください)。

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

交換法則 ${\displaystyle \operatorname {lcm} (a,b)=\operatorname {lcm} (b,a),}$ ${\displaystyle \gcd(a,b)=\gcd(b,a).}$

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

吸収の法則 ${\displaystyle \operatorname {lcm} (a,\gcd(a,b))=a,}$ ${\displaystyle \gcd(a,\operatorname {lcm} (a,b))=a.}$

べき等法則 ${\displaystyle \operatorname {lcm} (a,a)=a,}$ ${\displaystyle \gcd(a,a)=a.}$

最小公倍数と最大公約数の観点から除算を定義する ${\displaystyle a\geq b\iff a=\operatorname {lcm} (a,b),}$ ${\displaystyle a\leq b\iff a=\gcd(a,b).}$

この格子は分配的であることも示されている^[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の公倍数とは、Rの元mのうち、 aとb の両方がm を割り切るようなもの（つまり、Rの元xとyが存在し、 ax = mかつby = mとなるもの）をいう。aとbの最小公倍数とは、 aとbの他の任意の公倍数nに対してm がnを割り切る という意味で最小となる公倍数をいう。

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

参照

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

注記

1. Weisstein, Eric W. 「最小公倍数」. mathworld.wolfram.com . 2020年8月30日閲覧。
2. ハーディ＆ライト、§ 5.1、p.48
3. Long (1972, p. 39)
4. ペットフレッツォ＆ビルキット（1970年、56ページ）
5. 「NASA​​ SpaceMath」（PDF） .
6. 次の3つの式はLandau, Ex. III.3, p. 254より引用。
7. Crandall & Pomerance、例2.4、p.101。
8. ロング（1972年、41ページ）
9. ペットフレッツォ＆ビルキット（1970年、58ページ）
10. バートン 1970、94ページより。
11. グリレ 2007年、142ページ。

参考文献

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Least_common_multiple&oldid=1315885354"