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

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

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.