Using Prime Factorization to Find the GCF

In my other lesson, I discussed the procedure on how to find the Greatest Common Factor using the List Method. This method is only effective when dealing with smaller numbers.

That’s why we need to learn a backup method to determine the GCF when larger numbers are involved. This alternate method takes advantage of the usefulness of Prime Factorization.

a triangle with an exclamation point

I must caution you that there is a prerequisite for this lesson. You will need to have an understanding of how to perform prime factorization on an integer.

Please don’t feel bad if you need to take the refresher lesson. Trust me, it is easy! You will soon realize that you are back here in no time. Here’s the link: Integer Prime Factorization

Steps on How to Determine the GCF using Prime Factorization

a he/his person climbing up the stairs

These are the steps on how to find the greatest common factor of two numbers using Prime Factorization. Although this method can be extended to find the GCF of multiple numbers, I just want to focus on two numbers.

1) Write the Prime Factorization of each number. In other words, express each number as a product of numbers written in an exponential form. Obviously, the base will always be a prime number. 

2) Identify the numbers that have the same base. Disregard the exponent for now.

3) Compare the exponents of the numbers with a common base. Select the number which has the least exponent value. For instance, in [latex]{2^2}[/latex] and [latex]{2^4}[/latex], choose [latex]{2^2}[/latex] because its exponent has a lesser value than that of [latex]{2^4}[/latex], that is, [latex]2 < 4[/latex].

4) Multiply the numbers that you selected in step #3 to determine the greatest common factor.

Examples of Determining the Greatest Common Factor (GCF) using Prime Factorization

Example 1: What is the GCF of 36 and 120 ?

Begin by expressing each number into its prime factorized form.

36 = 2^2*3^2 and 120 = 2^3*3*5

Next, we identify the exponential numbers that have the same base. Notice that [latex]{2^2}[/latex] and [latex]{2^3}[/latex] have a common base of [latex]2[/latex]. On the other hand, [latex]{3^2}[/latex] and [latex]3[/latex] have a common base of [latex]3[/latex]. We ignore [latex]5[/latex] for a simple reason that [latex]36[/latex] doesn’t have a prime factor of [latex]5[/latex]. Again, it must be common to both.

take it slow written inside a hexagon

I need you to slow down here before continuing. The integer [latex]3[/latex] appears to have no exponent. If ever you see a positive integer which doesn’t have an exponent on its upper right corner, don’t jump into conclusion that it has an exponent of zero. That’s wrong! This is a common pitfall of many of my students. The fact is, it is assumed to have an exponent of [latex]1[/latex]. Therefore, [latex]3[/latex] is equal to [latex]{3^1}[/latex].

For emphasis, we encircle the numbers that have a common base using the same color. Red circles for [latex]{2^2}[/latex] and [latex]{2^3}[/latex] while blue for [latex]{3^2}[/latex] and [latex]3[/latex].

2 squared and 2 cube have a common base of 2 while 3 squared and 3 have a common base of 3.

Now we are going to select which number has the least exponent value for each common prime factor.

  • In the case of [latex]{2^2}[/latex] and [latex]{2^3}[/latex], we pick [latex]{2^2}[/latex] because [latex]2 < 3[/latex].
  • For [latex]{3^2}[/latex] and [latex]3[/latex], we pick [latex]3[/latex] because [latex]1 < 3[/latex].

The arrows indicated the numbers that we chose.

we chose two squared and three

The final step is to multiply the numbers that we have selected from the previous step. The chosen numbers are those that have a common prime number base with the least exponent value. Therefore, the GCF of [latex]36[/latex] and [latex]120[/latex] is [latex]{2^2}[/latex] times [latex]3[/latex] which equals to [latex]12[/latex].

the GCF of 36 and 120 is 12.

Example 2: What is the GCF of 150 and 180?

This problem is not different from the first one. The numbers are just relatively larger. Finding the GCF of these two numbers should take extra work – especially with the prime factorization part. But the steps remain the same which should give us a boost of confidence.

Start by prime factorizing 150 and 180.

150 = 2 times 3 times 5^2 180 = 2^2 times 3^2 times 5

Now we identify the numbers with a common base. They are color-coded for emphasis.

  • Common base of [latex]2[/latex] and [latex]{2^2}[/latex] is [latex]2[/latex].
  • Common base of [latex]3[/latex] and [latex]{3^2}[/latex] is [latex]3[/latex].
  • Common base of [latex]{5^2}[/latex] and [latex]5[/latex] is [latex]5[/latex].
two and two squared are highlighted in orange, three and three squared are highlighted with green and 5 squared and five are highlighted with blue.

For the numbers that have a common base, select the number with the smallest exponent value. Between [latex]2[/latex] and [latex]{2^2}[/latex], we chose [latex]2[/latex]. Between [latex]3[/latex] and [latex]{3^2}[/latex], we chose [latex]3[/latex]. And finally, we chose [latex]5[/latex] between [latex]{5^2}[/latex] and [latex]5[/latex].

we chose two, three and five

For the last step, we multiply together the numbers we have chosen from the previous step to determine the GCF. Thus, the GCF of 150 and 180 is 2 times 3 times 5 which is equal to 30.

The GCF of 150 and 180 is 30.

Example 3: What is the GCF of 1,260 and 1,960?

Let’s take this skill of finding the greatest common factor to the next level. This time we will find the GCF of two numbers that have numerical values between 1,000 and 2,000.

By now, you’ve probably realized that finding the GCF of these numbers using the list method is going to be cumbersome. This is the reason why I have to create a separate lesson on finding the GCF using the Prime Factorization method. It is more efficient, accurate, and prone to less errors especially when you are working it out by hand.

To get to the heart of this method, you will need to have a good grasp on how to prime factorize a positive integer using the Prime Factor Tree.

I can’t overemphasize the importance of Prime Factor Tree. Trust me, it will be your best friend from here on out during your study of algebra in general.

blue and orange nuts

In a nutshell, here’s the method of prime factorization using the Prime Factor Tree. Start dividing the given number by the smallest prime number which is [latex]2[/latex]. If [latex]2[/latex] evenly divides the number, draw a diagonal down towards the left (branch of the tree) of the given number and write [latex]2[/latex]. Then, write the quotient by drawing a diagonal down towards the right. The quotient will become part of the trunk of the tree.

Keep dividing the subsequent quotients by [latex]2[/latex] while recording your results as branches (divisors) and part of the trunk (quotients that are composite numbers). Keep going until such time when [latex]2[/latex] can no longer divide the quotient. That’s when you move to the next prime number which is [latex]3[/latex], and so on. Repeat the process until the quotient is a prime number. This is when you stop.

❖ Here’s the Prime Factor Tree of the number 1,260 and its Prime Factorization.

An illustration showing the prime factor tree of 1,260.
1260 = 2^2*3^2*5*7

❖ Below is the Prime Factor Tree of the number 1,960 and its Prime Factorization.

An illustration showing the prime factor tree of 1,1960.
1960 = 2^3*5*7^2

Finally, since we have successfully prime factorized the two large numbers, we can now proceed as usual just like in examples #1 and #2.

  • Write the prime factorizations of 1260 and 1960 side by side. It’s a good practice to align the numbers with the same base.
1260 = 2^2*3^2*5*7 and 1960 = 2^3*space*5*7^2
  • Identify the numbers written in exponential form that have the same base. Just like before, don’t mind the exponents yet.
two squared and two cube have the same base of two, five and five have the base of five, and seven and seven squared have an exponent of seven.
  • Compare the exponents of the exponential numbers having a common base. Select the exponential number that has the least exponent value. Between [latex]{2^2}[/latex] and [latex]{2^3}[/latex], we chose [latex]{2^2}[/latex], not [latex]{2^3}[/latex], because the exponent of the former is less than the latter. Ignore [latex]{3^2}[/latex] because it has no matching number with a base of [latex]3[/latex]. For [latex]5[/latex] and [latex]5[/latex] , simply select [latex]5[/latex] since they are exactly the same – a duplicate for that matter. And finally, we chose [latex]7[/latex] over [latex]{7^2}[/latex] for the same reason that [latex]1 < 2[/latex].
we choose two squared and five
  • The last step to get the greatest common factor of 1,260 and 1,960 is to multiply the numbers we have selected from the previous step. Therefore, the GCF of 1,260 and 1,960 is equal to [latex]{2^2}[/latex] times [latex]5[/latex] times [latex]7[/latex] which gives us [latex]140[/latex].
The GCF of 1260 and 1960 is 140.

You may also be interested in these related math lessons or tutorials:

Finding GCF using the List Method

Finding LCM using the List Method

Use Prime Factorization to Find LCM