Least common multiple

From Citizendium
Revision as of 05:43, 23 April 2010 by imported>Peter Schmitt (restore)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
Student Level [?]
 
This editable Main Article is under development and subject to a disclaimer.

The least common multiple (often abbreviated lcm, or l.c.m.) of two or more natural numbers is the smallest number which is a multiple of (i.e., is divided evenly by) both (or all) the numbers. Since the product of the numbers is a multiple of each of the numbers, and since a multiple of a number is greater than the number, the least common multiple of some numbers is a number between the greatest of these numbers and their product (inclusive), and it therefore can be determined (at least in principle) by testing finitely many numbers.

The least common multiple of two numbers equals their product if and only if their greatest common divisor is 1, i.e., if they are relatively prime. The least common multiple of three or more numbers equals their product if and only if they are pairwise relatively prime.

The least common multiple of two numbers a and b usually is written as lcm(a,b), or, if no confusion is to be expected, simply as [a,b].

Finding the least common multiple

A theoretically important method to determine the least common multiple uses prime factorization: Every prime factor of one of the numbers must be a prime factor of the least common multiple. The least common multiple therefore is the product of all prime factors taken with the highest power occurring in one of the numbers. However, since prime factorization is not efficient, this is at most practical for small numbers (or for numbers whose factorization is already known). This product expression shows that the least common multiple can be characterized by the following property: The lcm is a common multiple, and it divides evenly every common multiple.

In order to efficiently calculate the least common multiple of two numbers, first determine the greatest common divisor (using the Euclidean algorithm) and then use

lcm(a,b) = ab/gcd(a,b).

The least common multiple can be calculated by repeating this:

lcm(a,b,c) = lcm(a,lcm(b,c))

Examples

For instance,

  • lcm(4,9) = 36, lcm(4,6) = 12, and lcm(4,12) = 12, because
the smallest multiples of 9 are 9,18,27, 36, the fourth is the smallest one divisible by 4, thus the lcm is 36;
the smallest multiples of 6 are 6,12, the second is the smallest one divisible by 4, thus the lcm is 12;
the smallest multiple of 12 is 12 which is divisible by 4, thus the lcm is 12;
  • lcm(72,108) = 216, because
the prime factorizations 72 = 22 • 2 • 3 and 108 = 2 • 2 • 333 require three factors 2 (from 72) and three factors (from 108), thus the lcm = 2 • 2 • 2 • 3 • 3 • 3 = 216.
  • lcm(6,10,15) = 30, as can be seen either
from the prime factorizations 6 = 2 • 3, 10 = 2 • 5, and 15 = 3 • 5 which produce lcd(6,10,15) = 2 • 3 • 5 = 30, or
from the lists of smallest multiples: 6,12,18,24,30 for 6, and 10,20,30 for 10, and 15,30 for 15.

Applications

In elementary arithmetic, the least common multiple occurs when fractions are added and a reduced fraction is wanted:

For any number of fractions, the least common multiple of the denominators is the least common denominator, i.e., the denominator of their sum in its reduced form.

Formulas

bounds
gcd and lcm
prime factor representation