主题
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)

另请参阅

切比雪夫函数, 最大公约数, 最小公分母, 曼戈尔特函数, 倍数, 互质 在 MathWorld 课堂中探索此主题

相关 Wolfram 网站

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

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上引用

最小公倍数

请引用为

Weisstein, Eric W. “最小公倍数。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/LeastCommonMultiple.html

主题分类