Katana VentraIP

Least common multiple

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b.[1][2] Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero.[3] However, some authors define lcm(a, 0) as 0 for all a, since 0 is the only common multiple of a and 0.

The least common multiple of the denominators of two fractions is the "lowest common denominator" (lcd), and can be used for adding, subtracting or comparing the fractions.


The least common multiple of more than two integers a, b, c, . . . , usually denoted by lcm(a, b, c, . . .), is defined as the smallest positive integer that is divisible by each of a, b, c, . . .[1]

Formulas[edit]

Fundamental theorem of arithmetic[edit]

According to the fundamental theorem of arithmetic, every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors:

In commutative rings[edit]

The least common multiple can be defined generally over commutative rings as follows:


Let a and b be elements of a commutative ring R. A common multiple of a and b is an element m of R such that both a and b divide m (that is, there exist elements x and y of R such that ax = m and by = m). A least common multiple of a and b is a common multiple that is minimal, in the sense that for any other common multiple n of a and b, m divides n.


In general, two elements in a commutative ring can have no least common multiple or more than one. However, any two least common multiples of the same pair of elements are associates.[10] In a unique factorization domain, any two elements have a least common multiple.[11] In a principal ideal domain, the least common multiple of a and b can be characterised as a generator of the intersection of the ideals generated by a and b[10] (the intersection of a collection of ideals is always an ideal).

Anomalous cancellation

Coprime integers

Chebyshev function

Burton, David M. (1970). A First Course in Rings and Ideals. Reading, MA: Addison-Wesley.  978-0-201-00731-2.

ISBN

Crandall, Richard; Pomerance, Carl (2001), , New York: Springer, ISBN 0-387-94777-9

Prime Numbers: A Computational Perspective

Grillet, Pierre Antoine (2007). Abstract Algebra (2nd ed.). New York, NY: Springer.  978-0-387-71568-1.

ISBN

Hardy, G. H.; Wright, E. M. (1979), , Oxford: Oxford University Press, ISBN 978-0-19-853171-5

An Introduction to the Theory of Numbers (Fifth edition)

Landau, Edmund (1966), Elementary Number Theory, New York: Chelsea

Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: , LCCN 77-171950

D. C. Heath and Company

Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: , LCCN 77-81766

Prentice Hall