Least Common Multiple
The least common multiple of two numbers 
and 
, variously denoted
(this work; Zwillinger 1996,
p. 91; Råde and Westergren 2004, p. 54), 
(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.
(Andrews 1994,
p. 22; Guy 2004, pp. 312-313), or ![[a,b]](/images/equations/LeastCommonMultiple/Inline6.gif)
, is the smallest
positive number 
for which there exist positive integers
and 
such that
 |
(1)
|
The least common multiple 
of
more than two numbers is similarly defined.
The least common multiple of 
, 
, ... is implemented
in the Wolfram Language as LCM[a,
b, ...].
The least common multiple of two numbers 
and 
can be obtained
by finding the prime factorization of each
 |  |  |
(2)
|
 |  |  |
(3)
|
where the 
s are all prime
factors of 
and 
, and if 
does not occur
in one factorization, then the corresponding exponent is taken as 0. The least common
multiple is then given by
 |
(4)
|
For example, consider 
.
 |  |  |
(5)
|
 |  |  |
(6)
|
so
 |
(7)
|
The plot above shows 
for rational
, which is equivalent to the numerator
of the reduced form of 
.
The above plots show a number of visualizations of 
in the
-plane. The figure on the left is
simply 
, the figure in the middle is
the absolute values of the two-dimensional discrete
Fourier transform of 
(Trott
2004, pp. 25-26), and the figure at right is the absolute value of the transform
of 
.
The least common multiples of the first 
positive integers
for 
, 2, ... are 1, 2, 6, 12, 60, 60, 420,
840, ... (OEIS A003418; Selmer 1976), which
is related to the Chebyshev function 
. For 
, 
(Nair 1982ab, Tenenbaum 1990). The prime number
theorem implies that
 |
(8)
|
as 
, in other words,
 |
(9)
|
as 
.
Let 
be a common multiple of 
and 
so that
 |
(10)
|
Write 
and 
,
where 
and 
are relatively
prime by definition of the greatest common
divisor 
. Then 
, and from
the division lemma (given that 
is divisible
by 
and 
),
we have 
is divisible
by 
, so
 |
(11)
|
 |
(12)
|
The smallest 
is given by 
,
 |
(13)
|
so
 |
(14)
|
The LCM is idempotent
 |
(15)
|
 |
(16)
|
 |  |  |
(17)
|
 |  |  |
(18)
|
 |
(19)
|
and satisfies the absorption law
 |
(20)
|
It is also true that
 |  |  |
(21)
|
 |  |  |
(22)
|
 |  |  |
(23)
|
RELATED WOLFRAM SITES: 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 
." §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. "Least Common Multiple." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/LeastCommonMultiple.html
Contact the MathWorld Team
least common multiple
