Find GCF by Prime Factorization

Before looking at how to find the greatest common factor, GCF by prime factorization, we can look at a recap of what prime factors are and how to find them.

Prime Factorization of Numbers

We can start by just looking at a random number for an example, let’s say 36.

The approach for prime factorization of 36, is to keep dividing by prime numbers, until the answer of the division ends up being a prime number.

Look to start off by trying to divide by the lowest prime number there is, which is 2.

1) 36 ÷ 2 = 18
2) 18 ÷ 2 = 9
3) 9 ÷ 2 = 4.5 Doesn’t divide exactly, so try to start with the next prime number instead, 3.
4) 9 ÷ 3 = 3

3 is a prime number, so we can stop the division here.

Now, the different prime numbers that are used to divide at each stage, should give back the original number that was started with, if multiplied together with the last prime number obtained after division.

In this case with 36, 2 was used a total of 2 times for exact division, and 3 one time before we eventually obtained the prime number of 3.

So we can do: 2 × 2 × 3 × 3 = 36

This sum form can be simplified with an exponent/power, to give the following. 2^² × 3^² = 36

In this form, 2 and 3 are factors that are prime.
That completes finding the prime factorization for 36.

Find GCF by Prime Factorization

Prime factorization is interesting in its own right. But it does have some further applications that can be very handy.
When wishing to obtain the lowest common multiple of two numbers, we can find this LCM by prime factorization.

How it Works:

Let’s look at the two numbers 16 and 28.

First thing to do is to prime factorize both numbers separately.

16

1) 16 ÷ 2 = 8
2) 8 ÷ 2 = 4
3) 4 ÷ 2 = 2 PRIME NUMBER

28

1) 28 ÷ 2 = 14
2) 14 ÷ 2 = 7 PRIME NUMBER

16 ) 2 × 2 × 2 × 2 = 16 => 2^² × 2^² = 16
28 ) 2 × 2 × 7 = 28 => 2^² × 7 = 28

When prime factorized, the numbers 16 and 28 both share one 2, and another 2.

These prime factors that are shared, when multiplied together, will give the greatest common factor (GCF), of the two numbers.

2 × 2 = 4 => The greatest common factor of 16 and 28 is 4.

We can also see this to be true by listing the factors of each number.

16 ) 1 , 2 , 4 , 8 , 16
28 ) 1 , 2 , 4 , 7 , 14 , 28

Examples

1.1

Greatest common factor of 18 and 78?

Solution

18

1) 18 ÷ 2 = 9
2) 9 ÷ 2 = 4.5 Doesn’t divide exactly.
3) 9 ÷ 3 = 3 PRIME NUMBER

78

1) 78 ÷ 2 = 39
2) 39 ÷ 2 = 19.5 Doesn’t divide exactly.
3) 39 ÷ 3 = 13 PRIME NUMBER

18 ) 2 × 3 × 3 = 18 => 2 × 3^² = 18

78 ) 2 × 3 × 13 = 78

When prime factorized, the numbers 18 and 78 both share one 2, and one 3.

2 × 3 = 6 => The greatest common factor of 18 and 78 is 6.

1.2

Gcf by prime factorization of 16 and 30?

Solution

16

1) 16 ÷ 2 = 8
2) 8 ÷ 2 = 4
3) 4 ÷ 2 = 2 PRIME NUMBER

30

1) 30 ÷ 2 = 15
2) 15 ÷ 2 = 7.5 Doesn’t divide exactly.
3) 15 ÷ 3 = 5 PRIME NUMBER

16 ) 2 × 2 × 2 × 2 = 16 => 2^² × 2^² = 16

30 ) 2 × 3 × 5 = 30

When prime factorized, the numbers 16 and 30 only share one 2.

So 2 is the greatest common factor.

Home
Arithmetic/Numbers

Return to TOP of page