Least common multiple

From Knowino
Jump to: navigation, search

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].

Contents

[edit] 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 of three (and more) numbers can be calculated by repeating this:

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

[edit] Examples

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;
the prime factorizations 72 = 2 • 2 • 2 • 3 • 3 and 108 = 2 • 2 • 3 • 3 • 3 require three factors 2 (from 72) and three factors 3 (from 108), thus the lcm = 2 • 2 • 2 • 3 • 3 • 3 = 216.
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.

[edit] Applications

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

\frac ab + \frac cd = \frac {ad+cb}{bd} = { a \cdot { d \over \mathop{\rm gcd}(c,d) } + c \cdot { b \over \mathop{\rm gcd}(c,d) } \over \mathop{\rm lcm}(b,d)}

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.

[edit] Formulas

bounds 
\max(a,b) \le \mathop{\rm lcm} (a,b) \le ab
gcd and lcm 
\mathop{\rm gcd} (a,b) \mathop{\rm lcm} (a,b) = ab
prime factor representation 
a = \prod_{p\ \rm prime} p^{a(p)} \ \textrm{\ and\ }\ b = \prod_{p\ \rm prime} p^{b(p)} \ \Rightarrow \ \mathop{\rm lcm}(a,b) = \prod_{p\ \rm prime} p^{\max(a(p),b(p))}
Information.svg Some content on this page may previously have appeared on Citizendium.
Retrieved from "http://knowino.org/wiki/Least_common_multiple"
Personal tools
Variants
Actions
Navigation
Community
Toolbox