TOPICS
Search

Least Common Multiple

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The least common multiple of two numbers a and b, variously denoted LCM(a,b) (this work; 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), or [a,b], is the smallest positive number (multiple) m for which there exist positive integers n_a and n_b such that

n_aa=n_bb=m.
(1)

The least common multiple LCM(a,b,c,...) of more than two numbers is similarly defined.

The least common multiple of a, b, ... is implemented in the Wolfram Language as LCM[a, b, ...].

The least common multiple of two numbers a and b can be obtained by finding the prime factorization of each

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

where the p_is are all prime factors of a and b, and if p_i does not occur in one factorization, then the corresponding exponent is taken as 0. The least common multiple is then given by

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

For example, consider LCM(12,30).

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

so

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

The plot above shows LCM(1,r) for rational r=m/n, which is equivalent to the numerator of the reduced form of m/n.

LCMArray

The above plots show a number of visualizations of LCM(i,j) in the (i,j)-plane. The figure on the left is simply LCM(i,j), the figure in the middle is the absolute values of the two-dimensional discrete Fourier transform of LCM(i,j) (Trott 2004, pp. 25-26), and the figure at right is the absolute value of the transform of 1/LCM(i,j).

LeastCommonMultipleDensity

The least common multiples of the first n positive integers for n=1, 2, ... are 1, 2, 6, 12, 60, 60, 420, 840, ... (OEIS A003418; Selmer 1976), which is related to the Chebyshev function psi(n). For n>=7, LCM(1,2,...,n)>2^n (Nair 1982ab, Tenenbaum 1990). The prime number theorem implies that

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

as n->infty, in other words,

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

as n->infty.

Let m be a common multiple of a and b so that

m=ha=kb.
(10)

Write a=a_1GCD(a,b) and b=b_1GCD(a,b), where a_1 and b_1 are relatively prime by definition of the greatest common divisor GCD(a_1,b_1)=1. Then ha_1=kb_1, and from the division lemma (given that ha_1 is divisible by b_1 and GCD(b_1,a_1)=1), we have h is divisible by b_1, so

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

The smallest m is given by n=1,

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

so

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

The LCM is idempotent

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

commutative

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

associative

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

distributive

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

and satisfies the absorption law

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

It is also true that

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

See also

Chebyshev Functions, Greatest Common Divisor, Least Common Denominator, Mangoldt Function, Multiple, Relatively Prime Explore this topic in the MathWorld classroom

Related Wolfram sites

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

Explore with Wolfram|Alpha

References

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.

Referenced on Wolfram|Alpha

Least Common Multiple

Cite this as:

Weisstein, Eric W. "Least Common Multiple." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LeastCommonMultiple.html

Subject classifications