Two ways to find the greatest common factor
The greatest common factor of a set of whole numbers is the largest whole number that divides every one of them with no remainder. Schools in Australia and the UK usually call it the highest common factor (HCF), mathematicians and programmers say greatest common divisor (GCD), and American textbooks say GCF. All three names mean the same thing.
Euclid’s method: gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a
Here a and b are the two numbers, and “a mod b” is the remainder left when a is divided by b. Each step swaps the pair for a smaller pair with the same common factors, and the last remainder before zero is the answer. For more than two numbers, find the GCF of the first two, then the GCF of that result and the third number, and so on.
Prime factorisation: GCF = product of each shared prime raised to its lowest exponent
Write each number as a product of primes. A prime belongs in the GCF only if it appears in every number, and it is raised to the smallest power it has in any of them.
Worked example: the GCF of 1071 and 462
By Euclid’s method. Divide, keep the remainder, and repeat with the previous divisor.
- 1071 ÷ 462 = 2 remainder 147, because 2 × 462 = 924 and 1071 − 924 = 147.
- 462 ÷ 147 = 3 remainder 21, because 3 × 147 = 441 and 462 − 441 = 21.
- 147 ÷ 21 = 7 remainder 0.
The remainder has reached zero, so the last divisor, 21, is the greatest common factor.
By prime factorisation. 1071 = 3² × 7 × 17 and 462 = 2 × 3 × 7 × 11. The shared primes are 3 and 7. The lowest power of 3 is 3¹ and the lowest power of 7 is 7¹, so the GCF is 3 × 7 = 21. Both methods agree.
Three numbers. For 84, 126 and 210, first gcd(84, 126) = 42, then gcd(42, 210) = 42. Dividing each number by 42 leaves 2, 3 and 5, which share nothing further.
Which method to use
Prime factorisation is easy to follow for small numbers and shows why the answer is what it is. It becomes impractical quickly, because factorising a large number is hard work. Euclid’s method never factorises anything. It only divides, and the numbers shrink fast: the count of division steps is never more than five times the number of digits in the smaller number. The slowest cases are neighbouring Fibonacci numbers, such as 89 and 55, which need 9 steps against a limit of 10. This is why the calculator can handle 30-digit numbers instantly by Euclid’s method but shows the prime factorisation only when every number is 1,000,000,000,000 or less.
Where the GCF is used
Simplifying fractions and ratios
Dividing the top and bottom of a fraction by their GCF puts it in lowest terms in one step: 462/1071 becomes 22/51 after dividing both by 21. Ratios work the same way, so 84 : 126 : 210 simplifies to 2 : 3 : 5.
Splitting things into equal groups
The GCF is the largest group size that uses everything up. A floor measuring 360 cm by 480 cm can be covered with whole square tiles of at most 120 cm, the GCF of the two sides, and it takes 3 × 4 = 12 of them.
Finding the least common multiple
For two numbers, the GCF multiplied by the least common multiple equals the product of the numbers. With 1071 and 462 the product is 494,802, so the least common multiple is 494,802 ÷ 21 = 23,562. This shortcut holds for exactly two numbers and fails for three or more.
Points that trip people up
- A GCF of 1 is a valid answer. Numbers such as 8 and 15 share no factor other than 1. They are called coprime, even though neither is prime.
- Zero is allowed. Every whole number divides 0, so gcd(a, 0) = a. Only gcd(0, 0) has no answer.
- The GCF can never be larger than the smallest number. If one number divides all the others, it is the GCF: gcd(12, 36) = 12.
- Common primes are multiplied, not added. For 1071 and 462 the answer is 3 × 7 = 21, not 3 + 7 = 10.
- Use the lowest exponent, not the highest. Taking the highest power of every prime gives the least common multiple instead.