最小公倍數- 維基百科，自由的百科全書 - Wikipedia
文章推薦指數： 80 %
最小公倍數是數論中的一個概念。
... 的公倍數有無限個，而所有正的公倍數中，最小的公倍數就叫做最小公倍數。
同樣地，若干個整數公有的 ... 與最大公因數之關係編輯.
最小公倍數
語言
監視
編輯
最小公倍數是數論中的一個概念。
若有一個數
X
{\displaystyleX}
，可以被另外兩個數
A
{\displaystyleA}
、
B
{\displaystyleB}
整除，且
X
{\displaystyleX}
大於（或等於）
A
{\displaystyleA}
和
B
{\displaystyleB}
，則
X
{\displaystyleX}
為
A
{\displaystyleA}
和
B
{\displaystyleB}
的公倍數。
A
{\displaystyleA}
和
B
{\displaystyleB}
的公倍數有無限個，而所有正的公倍數中，最小的公倍數就叫做最小公倍數。
同樣地，若干個整數公有的倍數中最小的正整數稱為它們的最小公倍數。
n
{\displaystylen}
整數
a
1
,
a
2
,
⋯
,
a
n
{\displaystylea_{1},a_{2},\cdots,a_{n}}
的最小公倍數一般記作：
[
a
1
,
a
2
,
⋯
,
a
n
]
{\displaystyle[a_{1},a_{2},\cdots,a_{n}]}
，或者參照英文記法記作
lcm
(
a
1
,
a
2
,
⋯
,
a
n
)
{\displaystyle\operatorname{lcm}(a_{1},a_{2},\cdots,a_{n})}
，其中lcm是英語中「最小公倍數」一詞（leastcommonmultiple）的首字母縮寫。
對分數進行加減運算時，要求兩數的分母相同才能計算，故需要擴分；標準的計算步驟是將兩個分數的分母擴分成它們的最小公倍數，然後將擴分後的分子相加。
目次
1與最大公因數之關係
2計算方法
2.1遞歸計算多個整數的最小公倍數
3程式代碼
3.1C#
3.2C
3.3C++
3.4PASCAL
3.5JAVA
3.6RUBY
3.7Python
3.8Golang
4應用
5參見
6參考來源
與最大公因數之關係編輯
兩個整數的最小公倍數與最大公因數之間有如下的關係：
lcm
(
a
,
b
)
=
|
a
⋅
b
|
gcd
(
a
,
b
)
{\displaystyle\operatorname{lcm}(a,b)={\frac{|a\cdotb|}{\operatorname{gcd}(a,b)}}}
計算方法編輯
最小公倍數可以通過多種方法得到，最直接的方法是列舉法，從小到大列舉出其中一個數（如最大數）的倍數，當這個倍數也是另一個數的倍數時，就求得最小公倍數。
另一個方法是利用公式
lcm
(
a
1
,
a
2
)
=
a
1
a
2
gcd
(
a
1
,
a
2
)
{\displaystyle\operatorname{lcm}(a_{1},a_{2})={\frac{a_{1}a_{2}}{\gcd(a_{1},a_{2})}}}
來求解，這時首先要知道它們的最大公因數。
而最大公因數可以通過短除法得到。
利用整數的唯一分解定理，還可以用質因數分解法。
將每個整數進行質因數分解。
對每個質數，在質因數分解的表達式中尋找次數最高的乘冪，最後將所有這些質數乘冪相乘就可以得到最小公倍數。
譬如求216、384和210的最小公倍數。
對216、384和210來說：
216
=
2
3
×
3
3
{\displaystyle216=2^{3}\times3^{3}}
，
384
=
2
7
×
3
1
{\displaystyle384=2^{7}\times3^{1}}
，
210
=
2
1
×
3
1
×
5
1
×
7
1
{\displaystyle210=2^{1}\times3^{1}\times5^{1}\times7^{1}}
。
其中
2
{\displaystyle2}
對應的最高次乘冪為
2
7
{\displaystyle2^{7}}
；
3
{\displaystyle3}
對應的最高次乘冪為
3
3
{\displaystyle3^{3}}
；
5
{\displaystyle5}
和
7
{\displaystyle7}
對應的最高次乘冪分別是
5
1
{\displaystyle5^{1}}
與
7
1
{\displaystyle7^{1}}
。
將這些乘冪乘起來，就可以得到最小公倍數：
[
216
,
384
,
210
]
=
2
7
×
3
3
×
5
1
×
7
1
=
120960
{\displaystyle[216,384,210]=2^{7}\times3^{3}\times5^{1}\times7^{1}=120960}
。
遞歸計算多個整數的最小公倍數編輯
可以遞歸求出多個整數的最小公倍數：欲求
lcm
(
a
1
,
.
.
.
,
a
n
)
(
n
≥
3
)
{\displaystyle\operatorname{lcm}(a_{1},...,a_{n})(n\geq3)}
，只需求
lcm
(
a
1
,
.
.
.
,
a
n
−
2
,
lcm
(
a
n
−
1
,
a
n
)
)
{\displaystyle\operatorname{lcm}(a_{1},...,a_{n-2},\operatorname{lcm}(a_{n-1},a_{n}))}
。
這利用了性質
lcm
(
a
1
,
a
2
,
a
3
)
=
lcm
(
lcm
(
a
1
,
a
2
)
,
a
3
)
{\displaystyle\operatorname{lcm}(a_{1},a_{2},a_{3})=\operatorname{lcm}(\operatorname{lcm}(a_{1},a_{2}),a_{3})}
。
該性質證明如下：
記
a
1
,
a
2
,
a
3
{\displaystylea_{1},a_{2},a_{3}}
的質因數分解分別為
∏
i
=
1
n
p
i
e
1
i
,
∏
i
=
1
n
p
i
e
2
i
,
∏
i
=
1
n
p
i
e
3
i
{\displaystyle\prod_{i=1}^{n}p_{i}^{e_{1i}},\prod_{i=1}^{n}p_{i}^{e_{2i}},\prod_{i=1}^{n}p_{i}^{e_{3i}}}
，其中
p
i
{\displaystylep_{i}}
是第
i
{\displaystylei}
個質數。
那麼根據最小公倍數的定義，
lcm
(
a
1
,
a
2
,
a
3
)
=
∏
i
=
1
n
p
i
max
(
e
1
i
,
e
2
i
,
e
3
i
)
{\displaystyle\operatorname{lcm}(a_{1},a_{2},a_{3})=\prod_{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i},e_{3i})}}
，
lcm
(
lcm
(
a
1
,
a
2
)
,
a
3
)
=
lcm
(
∏
i
=
1
n
p
i
max
(
e
1
i
,
e
2
i
)
,
a
3
)
=
∏
i
=
1
n
p
i
max
(
max
(
e
1
i
,
e
2
i
)
,
e
3
i
)
=
∏
i
=
1
n
p
i
max
(
e
1
i
,
e
2
i
,
e
3
i
)
{\displaystyle\operatorname{lcm}(\operatorname{lcm}(a_{1},a_{2}),a_{3})=\operatorname{lcm}(\prod_{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i})},a_{3})=\prod_{i=1}^{n}p_{i}^{\max(\max(e_{1i},e_{2i}),e_{3i})}=\prod_{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i},e_{3i})}}
，
證畢。
程式代碼編輯
以下使用輾轉相除法求得最大公因數，之後再求最小公倍數。
C#編輯
intGCD(inta,intb)
{
returna%b==0?b:GCD(b,a%b);
}
intLCM(inta,intb)
{
returna*b/GCD(a,b);
}
C編輯
intGCD(inta,intb){
if(b)while((a%=b)&&(b%=a));
returna+b;
}
intLCM(inta,intb){
returna*b/GCD(a,b);
}
C++編輯
template
將分母擴分時，會把所有分數的分母擴分為它們的最小公倍數，然後將分子相加。
例如：
2
21
+
1
6
=
4
42
+
7
42
=
11
42
{\displaystyle{2\over21}+{1\over6}={4\over42}+{7\over42}={11\over42}}
其中分母42就是21與6的最小公倍數。
參見編輯
公倍數
公因數
最大公因數參考來源編輯
柯召，孫綺，孫琦.《数论讲义》.高等教育出版社.2005.ISBN 753205473X.
阿爾伯特·H·貝勒著談祥柏譯.《数论妙趣：数学女王的盛情款待》.上海教育出版社.1998.ISBN 7040091909.
取自「https://zh.wikipedia.org/w/index.php?title=最小公倍數&oldid=71413804」
延伸文章資訊
- 1最大公因数和最小公倍数之间的关系是什么？有什么规律？
最大公因数：7. 最小公倍数：2×2×3×7=84. 扩展资料：. 最大公约数的求法：. （1）用分解质因数的方法，把公有的质因数相乘。 （2）用短除法的形式求两 ...
- 2如何理解兩個數的最大公因數和最小公倍數的關係？ - 每日頭條
一般用a、b表示a、b的最小公倍數，如6，8=24，6，9，12=72，求最小公倍數通常可採用列舉法，短除法、分解質因數法、輾轉相除法、最小公倍數的特點主要有、 ...
- 3- 最大公因數與最小公倍數
也可以由. 72. 18. ＝4 得到「18 是72 的因數」。 我們利用這樣的方式來判別標準分解式的因數、倍數。 利用短除法求幾個數的最大公因數 ...
- 4數的最大公因數和最小公倍數是什麼關係 - 櫻桃知識
互質的兩個數,最大公因數是1,最小公倍數是兩數的乘積。 成倍數關係的兩個數,最大公因數是那個小數,最小公倍數是那個大數。 最大公因數,是用來分數約分 ...
- 5最大公因數乘以最小公倍數=兩數的乘積(為什麼) -- MPM數學
最大公因數乘以最小公倍數=兩數的乘積(為什麼) -- MPM數學_新生代(亞東分校) 2012/11/08 19:49 分享最大公因數* 最小公倍數= 兩數的乘積ga7.
