What is the greatest common factor?
A factor (or divisor) of a number divides it exactly. The greatest common factor of several numbers is the biggest value that is a factor of all of them. It goes by other names too: greatest common divisor (GCD), highest common factor (HCF) and greatest common measure. For 12 and 18 the common factors are 1, 2, 3 and 6, so the GCF is 6.
The GCF is the tool behind simplifying fractions. To reduce 18/24, divide the top and bottom by GCF(18, 24) = 6 and you land on 3/4 in a single step.
Method 1: list the factors
Write every factor of each number, circle the ones that appear everywhere, and pick the largest. It is easy to follow and fine for numbers under a few hundred, but the lists grow quickly.
Method 2: prime factorization
Write each number as a product of primes, keep the primes shared by all of them, and multiply those together using the smallest exponent of each. For 16, 88 and 104:
- 16 = 2 × 2 × 2 × 2
- 88 = 2 × 2 × 2 × 11
- 104 = 2 × 2 × 2 × 13
Three 2s are common to all three, so the GCF is 2 × 2 × 2 = 8.
Method 3: the Euclidean algorithm
Euclid noticed that the GCF of two numbers does not change if you replace the larger by its remainder after dividing by the smaller. Repeat until the remainder is zero, and the last nonzero remainder is the answer.
Example with 268,442 and 178,296:
| Division | Remainder |
|---|---|
| 268,442 = 1 × 178,296 + 90,146 | 90,146 |
| 178,296 = 1 × 90,146 + 88,150 | 88,150 |
| 90,146 = 1 × 88,150 + 1,996 | 1,996 |
| 88,150 = 44 × 1,996 + 326 | 326 |
| 1,996 = 6 × 326 + 40 | 40 |
| 326 = 8 × 40 + 6 | 6 |
| 40 = 6 × 6 + 4 | 4 |
| 6 = 1 × 4 + 2 | 2 |
| 4 = 2 × 2 + 0 | 0 |
The chain finishes with a last nonzero remainder of 2, so GCD(268,442, 178,296) = 2. Because numbers this size would be painful to factor by hand, the Euclidean algorithm is the method of choice for large inputs.
More than two numbers
The GCF is associative, so for a list you compute it pairwise and carry the result forward: GCD(a, b, c) = GCD(GCD(a, b), c). Continuing the example, GCD(268,442, 178,296, 66,888) = GCD(2, 66,888) = 2.
Handy facts
- If the GCF is 1 the numbers are called coprime or relatively prime.
- The GCF can never exceed the smallest number in the list.
- If one number divides all the others, it is the GCF.
- For two numbers, GCF × LCM equals the product of the numbers.
Worked example
Find GCF(330, 75, 450, 225). The factorizations are 330 = 2 × 3 × 5 × 11, 75 = 3 × 5 × 5, 450 = 2 × 3 × 3 × 5 × 5 and 225 = 3 × 3 × 5 × 5. The only primes present in every number are one 3 and one 5, so the GCF is 3 × 5 = 15.
Choosing a method
For small numbers, listing factors is the most intuitive way to see what is going on, and it makes a good teaching aid. Prime factorization is the best choice when you also want the least common multiple, since the same factorizations feed both answers. The Euclidean algorithm wins whenever the numbers are big or you only need the GCF, because each step shrinks the problem dramatically: the remainder is always less than half of the larger number after two steps, so even 18-digit inputs finish in under a hundred divisions.
Real-world uses
- Cutting a 48 by 36 inch board into the largest possible identical squares: the side is GCF(48, 36) = 12 inches.
- Splitting 56 red and 42 blue marbles into identical bags with nothing left over: at most GCF(56, 42) = 14 bags.
- Reducing ratios such as 150:90 to 5:3 by dividing both sides by 30.
- Finding the common period of two repeating gear teeth or schedule patterns.