Greatest common factor

The greatest common factor (GCF) of two or more numbers is the largest factor they share. The greatest common factor may be found using a number of methods such as listing factors, using prime factorization, or Euclid's algorithm, among others. The GCF of two numbers, such as 12 and 16, can be denoted as GCF(12, 16).

For smaller numbers, listing factors is usually not too hard to do and is helpful for finding the greatest common factor.

Listing factors to find the GCF

To find the greatest common factor of 8 and 12:

First: list the factors

Factors of 8: 1, 2, 4, 8
Factors of 12: 1, 2, 3, 4, 6, 12

Next: compare these factors and identify the largest factor that the two numbers share

The greatest common factor of 8 and 12 is 4.
This can also be written as GCF (8, 12) = 4.

Using prime factorization to find the GCF

To find the greatest common factor of 36 and 48,

First: find the prime factorization

The numbers 36 and 48 have the prime factors 2, 2, and 3 in common.

Next: multiply these prime factors: 2 × 2 × 3 = 12

GCF (36, 48) = 12

Knowing how to find the greatest common factor is helpful in expressing common fractions in their simplest form.

Using Euclid's algorithm to find the GCF

Prime factorization and listing factors to find the GCF can quickly get tedious as the numbers get larger. Euclid's algorithm for finding the GCF is one of a number of more efficient algorithms for finding the GCF.

Euclid's algorithm is an algorithm involving long division that is based on the principle that the GCF of two numbers doesn't change if the larger number is replaced with its difference with the smaller number. So, GCF(18, 34) is the same as GCF(34 - 18, 18), or GCF(16, 18). We won't go into detail to prove why the Euclidean algorithm works, but to use the algorithm to find the GCF, follow these steps:

  1. Divide the larger number by the smaller number. If the remainder is 0, the divisor is the GCF. If not continue to the next step.
  2. Divide the smaller number (the previous divisor) by the remainder. If the new remainder is 0, the divisor is the GCF.
  3. Continue the process of dividing the previous divisor by the remainder until there is no remainder. The divisor that results in a remainder of 0 is the GCF of the original two numbers.

Example

Find GCF(114, 288):

Note that the quotient doesn't really matter for this algorithm, and we're not completing the actual original long division problem.

After dividing 4 times, the remainder is 0, and the last divisor is 6. Therefore, based on the algorithm, GCF(114, 288) = 6. This can be tested by dividing both 114 and 288 by 6:

114 ÷ 6 = 19

288 ÷ 6 = 48

19 and 48 don't share any common factors, confirming that 6 is the GCF of 114 and 288.

This algorithm can also be used to find the GCF for more than 2 numbers by finding the GCF between the first two numbers then calculating the GCF of the result and the next number. This can be written as:

GCF(a, b, c) = GCF(GCF(a, b), c)