主題
Search

最小公倍數

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

兩個數 a 和 b 的最小公倍數，通常表示為 LCM(a,b) (本文; Zwillinger 1996, p. 91; Råde and Westergren 2004, p. 54), lcm(a,b) (Gellert et al. 1989, p. 25; Graham et al. 1990, p. 103; Bressoud and Wagon 2000, p. 7; D'Angelo and West 2000, p. 135; Yan 2002, p. 31; Bronshtein et al. 2007, pp. 324-325; Wolfram Language), l.c.m.(a,b) (Andrews 1994, p. 22; Guy 2004, pp. 312-313), 或 [a,b], 是使得存在正整數 n_a 和 n_b 的最小正數 (倍數) m，滿足以下條件：

n_aa=n_bb=m.
(1)

多個數的最小公倍數 LCM(a,b,c,...) 也類似地定義。

a, b, ... 的最小公倍數在 Wolfram Language 中實現為LCM[a, b, ...].

兩個數 a 和 b 的最小公倍數可以透過找到每個數的素因數分解來獲得

a=p_1^(a_1)...p_n^(a_n)
(2)
b=p_1^(b_1)...p_n^(b_n),
(3)

其中 p_is 是 a 和 b 的所有素因子，如果在其中一個分解中沒有出現 p_i，則相應的指數取 0。然後最小公倍數由下式給出

LCM(a,b)=product_(i=1)^np_i^(max(a_i,b_i)).
(4)

例如，考慮 LCM(12,30)。

12=2^2·3^1·5^0
(5)
30=2^1·3^1·5^1,
(6)

因此

LCM(12,30)=2^2·3^1·5^1=60.
(7)
LCM

上面的圖顯示了有理數 r=m/n 的 LCM(1,r)，這等價於 m/n 的簡化形式的分子。

LCMArray

上面的圖顯示了 LCM(i,j) 在 (i,j)-平面中的一些視覺化表示。左圖只是 LCM(i,j)，中間的圖是 LCM(i,j) 的二維離散傅立葉變換的絕對值 (Trott 2004, pp. 25-26)，右圖是 1/LCM(i,j) 的變換的絕對值。

LeastCommonMultipleDensity

前 n 個正整數的最小公倍數，對於 n=1, 2, ... 是 1, 2, 6, 12, 60, 60, 420, 840, ... (OEIS A003418; Selmer 1976)，這與切比雪夫函式 psi(n) 相關。對於 n>=7, LCM(1,2,...,n)>2^n (Nair 1982ab, Tenenbaum 1990)。素數定理意味著

LCM(1,2,...,n)=e^(n(1+o(1)))
(8)

當 n->infty 時，換句話說，

(ln(LCM(1,2,...,n)))/n->1
(9)

當 n->infty 時。

設 m 是 a 和 b 的公倍數，使得

m=ha=kb.
(10)

寫成 a=a_1GCD(a,b) 和 b=b_1GCD(a,b)，其中 a_1 和 b_1 根據最大公約數 GCD(a_1,b_1)=1 的定義是互質的。那麼 ha_1=kb_1，根據除法引理（考慮到 ha_1 可被 b_1 整除且 GCD(b_1,a_1)=1），我們有 h 可被 b_1 整除，所以

h=nb_1
(11)
m=ha=nb_1a=n(ab)/(GCD(a,b)).
(12)

最小的 m 由 n=1 給出，

LCM(a,b)=(ab)/(GCD(a,b)),
(13)

因此

GCD(a,b)LCM(a,b)=ab
(14)

最小公倍數是冪等的

LCM(a,a)=a,
(15)

交換律

LCM(a,b)=LCM(b,a),
(16)

結合律

LCM(a,b,c)=LCM(LCM(a,b),c)
(17)
=LCM(a,LCM(b,c)),
(18)

分配律

LCM(ma,mb,mc)=mLCM(a,b,c),
(19)

並滿足吸收律

GCD(a,LCM(a,b))=a.
(20)

同樣成立的是

LCM(ma,mb)=(GCD(ma)GCD(mb))/(GCD(ma,mb))
(21)
=m(ab)/(GCD(a,b))
(22)
=mLCM(a,b).
(23)

另請參閱

切比雪夫函式, 最大公約數, 最小公分母, 曼戈爾特函式, 倍數, 互質 在 課堂中探索此主題

相關 Wolfram 網站

http://functions.wolfram.com/IntegerFunctions/LCM/

使用 探索

參考文獻

Andrews, G. E. Number Theory. New York: Dover, 1994.Bressoud, D. M. and Wagon, S. A Course in Computational Number Theory. London: Springer-Verlag, 2000.Bronshtein, I. N.; Semendyayev, K. A.; Musiol, G.; and Muehlig, H. Handbook of Mathematics, 5th ed. Berlin: Springer, 2007.D'Angelo, J. P. and West, D. B. Mathematical Thinking: Problem-Solving and Proofs, 2nd ed. Upper Saddle River, NJ: Prentice-Hall, 2000.Gellert, W.; Gottwald, S.; Hellwich, M.; Kästner, H.; and Künstner, H. (Eds.). VNR Concise Encyclopedia of Mathematics, 2nd ed. New York: Van Nostrand Reinhold, 1989.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science. Reading, MA: Addison-Wesley, 1990.Guy, R. K. "Density of a Sequence with l.c.m. of Each Pair Less than x." §E2 in Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, pp. 312-313, 2004.Jones, G. A. and Jones, J. M. "Least Common Multiples." §1.3 in Elementary Number Theory. Berlin: Springer-Verlag, pp. 12-13, 1998.Nagell, T. "Least Common Multiple and Greatest Common Divisor." §5 in Introduction to Number Theory. New York: Wiley, pp. 16-19, 1951.Nair, M. "A New Method in Elementary Prime Number Theory." J. London Math. Soc. 25, 385-391, 1982a.Nair, M. "On Chebyshev-Type Inequalities for Primes." Amer. Math. Monthly 89, 126-129, 1982b.Råde, L. and Westergren, B. Mathematics Handbook for Science and Engineering. Berlin: Springer, 2004.Selmer, E. S. "On the Number of Prime Divisors of a Binomial Coefficient." Math. Scand. 39, 271-281, 1976.Sloane, N. J. A. Sequence A003418/M1590 in "The On-Line Encyclopedia of Integer Sequences."Tenenbaum, G. Introduction à la théorie analytique et probabiliste des nombres. Publications de l'Institut Cartan, pp. 12-13, 1990.Trott, M. The Mathematica GuideBook for Programming. New York: Springer-Verlag, 2004. http://www.mathematicaguidebooks.org/.Yan, S. Y. Number Theory for Computing, 2nd ed. Berlin: Springer, 2002.Zwillinger, D. (Ed.). "Least Common Multiple." §2.3.6 in CRC Standard Mathematical Tables and Formulae, 30th ed. Boca Raton, FL: CRC Press, p. 91, 1996.

在 上引用

最小公倍數

請引用為

Weisstein, Eric W. “最小公倍數。” 來自 Web 資源。 https://mathworld.tw/LeastCommonMultiple.html

主題分類