It can be helpful to think of prime factorization in the form of a tree:

 

    As you may already have noticed, there is more than one way to find the prime factorization of a number. We could have first resolved 36 into 6 6, for example, and then determined the prime factorization from there. So don’t worry—you can’t screw up. No matter which path you take, you will always get the same result. That is, as long as you do your arithmetic correctly. Just for practice, find the prime factorizations for 45 and 41.

 

 

    Since the only factors of 41 are 1 and 41, 41 is a prime number. It is therefore its own prime factorization.

 

 

    The greatest common factor (GCF) of two numbers is the greatest factor that they have in common. Finding the GCF of two numbers is especially useful in certain applications, such as manipulating fractions (we explain why later in this section).

 

    In order to find the GCF of two numbers, we must first produce their prime factorizations. What is the greatest common factor of 18 and 24, for example?

 

    First, their prime factorizations:

 

    The greatest common factor is the greatest integer that can be written as a product of common prime factors. That is to say, the GCF is the “overlap,” or intersection, of the two prime factorizations. In this case, both prime factorizations contain 2 3 = 6. This is their GCF.

 

    Here’s another example:

    First:

    So, the product of the prime factors that they share is 2⁴ 3 = 48, which is their GCF.

 

    For practice, find the GCF of the following pairs of integers:

1. 12 and 15
2. 30 and 45
3. 13 and 72
4. 14 and 49
5. 100 and 80

    Compare your answers to the solutions:

1. 12 = 2² 3. 15 = 3 5. The GCF is 3.
2. 30 = 2 3 5. 45 = 3² 5. The GCF is 3 5 = 15.
3. 13 = 1 13. 72 = 2³ 3. There are no common prime factors. The GCF is 1.
4. 14 = 2 7. 49 = 7². The GCF is 7.
5. 100 = 2² 5². 80 = 2⁴ 5. The GCF is 2² 5 = 20.