Extension: GCF and LCM using prime factorizations

To find the GCF of two numbers we can always create a list of factors, like we've learned previously. But there is a faster way using factor trees. To find the greatest common factor of 126 and 294, we start by drawing their factor trees:

Prime factorization in expanded form:

126 = 2 \times 3 \times 3 \times 7

Prime factorization in expanded form:

294 = 2 \times 3 \times 7 \times 7

We then find what factors appear in both factorizations:126 = 2 \times 3 \times 3 \times 7

294 = 2 \times 3 \times 7 \times 7They have one 2, one 3, and one 7 in common. The greatest common factor is the product of the common prime factors, 2 \times 3 \times 7 = 42.

Examples

Example 1

Find the greatest common factor of 150 and 560.

Worked Solution

Create a strategy

Check the numbers that appear in both factorizations, then multiply these together.

Apply the idea

List the prime factorizations first:

150 = 2 \times 3 \times 5 \times 5

560 = 2 \times 2 \times 2 \times 2 \times 5 \times 7

Both factorizations contain one 2 and one 5, so we should multiply these together to find the GCF.

\displaystyle \text{GCF}	\displaystyle =	\displaystyle 2 \times 5
\displaystyle \text{ }	\displaystyle =	\displaystyle 10	Evaluate the product

So the GCF of 150 and 560 is 10.

Watch question walkthrough

Example 2

Use a Venn Diagram to find the greatest common factor of 45 and 30.

Worked Solution

Create a strategy

List the prime factors of 45 and 30, and then multiply the common factors.

Apply the idea

The prime factorization of 45 is: 3^2\times 5

The prime factorization of 30 is: 2\times 3\times 5

Put each prime factor in the correct place in the Venn diagram. Any common factors should be placed in the intersection of the two circles.

Multiply the numbers in the intersection of the two circles.

3\times 5 = 15

The product of the intersecting numbers is the GCF, 15.

To find the LCM of two numbers we can always create a list of multiples, like we've done before. But just like for GCF, there is a faster way using factor trees. To find the least common multiple of 126 and 294, we look again at their factor trees and state the prime factorizations in expanded form, since we found that already:

Prime factorization in expanded form:

126 = 2 \times 3 \times 3 \times 7

Prime factorization in expanded form:

294 = 2 \times 3 \times 7 \times 7

To find the least common multiple, we first find the GCF by multiplying the prime numbers that they have in common. We did this in the section above and found the GCF is equal to 42.

Now we multiply the GCF by all the remaining prime numbers.

Let's look at what prime numbers we have left:126 = 2 \times 3 \times 3 \times 7

294 = 2 \times 3 \times 7 \times 7

We've already used the 2's, 3's, and 7's that they have in common. The prime factors remaining are one 3 and one 7. So the least common multiple will be the product of the GCF and the remaining prime factors.42 \times 3 \times 7 = 882

Examples

Example 3

Consider the following prime factorizations:

54 = 2 \times 3 \times 3 \times 3

36 = 2 \times 2 \times 3 \times 3

Find the least common multiple of 54 and 36.

Worked Solution

Create a strategy

Find the GCF, then multiply by the remaining factors.

Apply the idea

\displaystyle \text{GCF}	\displaystyle =	\displaystyle 2 \times 3 \times 3	Multiply the common factors
\displaystyle \text{GCF}	\displaystyle =	\displaystyle 18	Evaluate the product
\displaystyle \text{LCM}	\displaystyle =	\displaystyle 18 \times 2 \times 3	Multiply by the remaining factors
\displaystyle \text{LCM}	\displaystyle =	\displaystyle 108	Evaluate the product

Example 4

What is the least common multiple of 10 and 12?

Worked Solution

Create a strategy

List the prime factors of 10 and 12, and write the common prime factors in the intersection of the two circles on a Venn Digram. Mulitply all the numbers on the Venn Diagram to get the least common multiple.

Apply the idea

The prime factorization of 10 is: 2\times5

The prime factorization of 12 is:2^2\times 3

Put each prime factor in the correct place in the Venn diagram. Any common factors should be placed in the intersection of the two circles.

Multiply the numbers from all three sections of the circles.

2\times 2 \times 3 \times 5=60

The product of all the prime numbers in the Venn diagram is the LCM, 60.