Greatest Common Factor Calculator
Find the greatest common factor (GCF), also called the greatest common divisor (GCD) or highest common factor (HCF), of up to 15 whole numbers. Choose your preferred method, Euclidean algorithm, prime factorization, or listing all factors, and get the full step-by-step working, a list of every common factor, and the corresponding least common multiple.
Formula
Worked example
GCF of 24, 36 and 60 by prime factorisation: 24 = 2^3 x 3, 36 = 2^2 x 3^2, 60 = 2^2 x 3 x 5. Shared primes: 2 (lowest power 2^2) and 3 (lowest power 3^1). GCF = 4 x 3 = 12. LCM = 360. Common factors: 1, 2, 3, 4, 6, 12.
What the greatest common factor is
The greatest common factor (GCF) of two or more integers is the largest positive integer that divides every one of them with no remainder. It is also called the greatest common divisor (GCD) or highest common factor (HCF). For example, the divisors shared by 24 and 36 are 1, 2, 3, 4, 6 and 12, so their GCF is 12. When the only shared divisor is 1 the numbers are said to be relatively prime, or coprime, even though none of them needs to be prime itself. The GCF is always at least 1 (since 1 divides everything) and at most the smallest number in the set.
Three methods for finding the GCF
This calculator supports all three standard methods. The Euclidean algorithm is the fastest: it replaces the pair (a, b) with (b, a mod b) repeatedly until the remainder is zero, at which point the last non-zero value is the GCF. Prime factorisation decomposes each number into its prime factors (for example 60 = 2^2 x 3 x 5) and the GCF is the product of the primes common to every number, each raised to its lowest power across the set. Listing all factors enumerates every positive divisor of each number and finds the largest value that appears in all lists. All three methods give the same result; the choice is a matter of what you want to show or understand. For a list of more than two numbers, every method applies the same pairwise logic repeatedly, since the GCF operation is associative: gcf(a, b, c) = gcf(gcf(a, b), c).
GCF and LCM: the fundamental connection
The GCF and the least common multiple (LCM) are complementary. For any two positive integers a and b, their product equals the product of their GCF and LCM: gcf(a, b) x lcm(a, b) = a x b. This identity is one of the most useful in elementary number theory. It means you can always compute one from the other once you know the pair: lcm(a, b) = a x b / gcf(a, b). For three or more numbers the pairwise identity extends naturally by applying it repeatedly. Knowing both the GCF and the LCM together gives a complete picture of how a set of integers relate to one another through divisibility.
Where the GCF is used in practice
The most common everyday use is simplifying fractions: dividing both numerator and denominator by their GCF reduces a fraction to lowest terms in a single step. In cryptography and modular arithmetic the extended Euclidean algorithm, a close cousin, is used to find modular inverses. In algebra the GCF is the "greatest common term" that can be factored out of a polynomial. In scheduling and tiling problems the GCF tells you the largest tile size (or repeating unit) that fits an exact number of times into each dimension of a problem. Engineers use it to find the coarsest common measurement unit for two or more quantities, and it underlies the analysis of gear ratios and musical harmony.
GCF, LCM and factor counts for common pairs
| Numbers | GCF | LCM | Common factors | Relationship |
|---|---|---|---|---|
| 8, 12 | 4 | 96 | 1, 2, 4 | Common factor |
| 18, 24 | 6 | 72 | 1, 2, 3, 6 | Common factor |
| 7, 13 | 1 | 91 | 1 | Coprime |
| 24, 36, 60 | 12 | 360 | 1, 2, 3, 4, 6, 12 | Common factor |
| 15, 25 | 5 | 75 | 1, 5 | Common factor |
| 9, 28 | 1 | 252 | 1 | Coprime |
| 48, 64 | 16 | 192 | 1, 2, 4, 8, 16 | Common factor |
| 12, 18, 24 | 6 | 72 | 1, 2, 3, 6 | Common factor |
| 100, 75 | 25 | 300 | 1, 5, 25 | Common factor |
| 14, 42 | 14 | 42 | 1, 2, 7, 14 | One divides the other |
The GCF and LCM of frequently encountered number pairs, with coprime pairs flagged.
Frequently asked questions
What is the difference between GCF, GCD, HCF and GCD?
They are all the same thing. Greatest common factor (GCF), greatest common divisor (GCD), and highest common factor (HCF) each mean the largest integer that divides every number in the set without leaving a remainder. The term used varies by country and textbook, but the calculation and result are identical.
What is the GCF if the numbers share no common factor above 1?
The GCF is 1. Since 1 divides every integer, 1 is always a common factor. When it is the only one, the numbers are called relatively prime or coprime. For example, 7 and 13 are coprime and their GCF is 1, even though neither is itself a prime factor of the other.
How do I find the GCF using prime factorisation?
Write each number as a product of prime factors. For example, 36 = 2^2 x 3^2 and 60 = 2^2 x 3 x 5. Identify the primes that appear in every factorisation and, for each such prime, take the lowest exponent across all numbers. Multiply those together: 2^2 x 3^1 = 12. Select "Prime factorization" from the method dropdown to see this process worked out step by step.
Can I find the GCF of more than two numbers?
Yes, up to 15 numbers. Enter them separated by commas or spaces. The calculator folds the GCF across them one pair at a time, which is valid because the GCF is associative: gcf(a, b, c) = gcf(gcf(a, b), c).
What is the relationship between the GCF and the LCM?
For any two positive integers a and b: GCF(a, b) x LCM(a, b) = a x b. This means once you know the GCF you can compute the LCM without re-factorising: LCM = a x b / GCF. Toggle "Also show LCM" to see both results at once.
How do I use the GCF to simplify a fraction?
Find the GCF of the numerator and denominator, then divide both by it. For example, 36/60 simplified: GCF(36, 60) = 12, so 36/60 = (36/12)/(60/12) = 3/5. The result is in lowest terms because dividing by the greatest common factor removes all shared divisors at once.
Why is the Euclidean algorithm faster than listing factors?
Listing factors requires testing every integer up to the square root of n, which is slow for large n. The Euclidean algorithm reduces the pair to a much smaller pair at each step (the remainder is always strictly smaller than the divisor) and typically reaches zero in a logarithmic number of steps relative to the smaller number. For two 10-digit numbers the Euclidean algorithm finishes in fewer than 100 steps; listing factors would need billions.