Least Common Multiple - Computing The Least Common Multiple - Finding Least Common Multiples By Prime Factorization

Finding Least Common Multiples By Prime Factorization

The unique factorization theorem says that every positive integer greater than 1 can be written in only one way as a product of prime numbers. The prime numbers can be considered as the atomic elements which, when combined together, make up a composite number.

For example:

Here we have the composite number 90 made up of one atom of the prime number 2, two atoms of the prime number 3 and one atom of the prime number 5.

This knowledge can be used to find the LCM of a set of numbers.

Example: Find the value of lcm(8,9,21).

First, factor out each number and express it as a product of prime number powers.

The lcm will be the product of multiplying the highest power of each prime number together. The highest power of the three prime numbers 2, 3, and 7 is 23, 32, and 71, respectively. Thus,

This method is not as efficient as reducing to the greatest common divisor, since there is no known general efficient algorithm for integer factorization, but is useful for illustrating concepts.

This method can be illustrated using a Venn diagram as follows. Find the prime factorization of each of the two numbers. Put the prime factors into a Venn diagram with one circle for each of the two numbers, and all factors they share in common in the intersection. To find the LCM, just multiply all of the prime numbers in the diagram.

Here is an example:

48 = 2 × 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 3 × 5,

and what they share in common is two "2"s and a "3":

Least common multiple = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

Greatest common divisor = 2 × 2 × 3 = 12

This also works for the greatest common divisor (GCD), except that instead of multiplying all of the numbers in the Venn diagram, one multiplies only the prime factors that are in the intersection. Thus the GCD of 48 and 180 is 2 × 2 × 3 = 12.