Encyclopedia > Least common multiple

  Article Content

Least common multiple

The least common multiple (LCM) of two integers a and b is the smallest positive integer that is a multiple of both a and b. If there is no such positive integer, i.e., if either a or b is zero, then lcm(a,b) is defined to be zero.

The least common multiple is useful when adding or subtracting fractions, because it yields the lowest common denominator. Consider for instance

2/21 + 1/6 = 4/42 + 7/42 = 11/42
the denominator 42 was used because lcm(21,6) = 42.

In case not both a and b are zero, the least common multiple can be computed by using the greatest common divisor (or GCD) of a and b,

a b
lcm(a, b) = ---------
gcd(a, b)
 
Thus, the Euclidean algorithm for the GCD also gives us a fast algorithm for the LCM. As an example, the LCM of 12 and 15 is 12 × 15 / 3 = 60.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Great River, New York

... out with 29.0% under the age of 18, 5.0% from 18 to 24, 29.0% from 25 to 44, 24.2% from 45 to 64, and 12.7% who are 65 years of age or older. The median age is 39 years. ...

 
 
 
This page was created in 58.5 ms