Greatest Common Factor (GCF) Calculator
Enter two or more whole numbers to find their greatest common factor, also called the greatest common divisor. Each division step of the Euclidean algorithm is listed so you can follow it.
The Euclidean algorithm
The greatest common factor of two numbers is the largest whole number that divides both without a remainder. Rather than listing every factor, the Euclidean algorithm uses one fact: gcd(a, b) equals gcd(b, a mod b). Divide the larger number by the smaller, keep the remainder, and repeat with the smaller number and the remainder until the remainder is zero. The last non-zero remainder is the answer.
For 1071 and 462: 1071 = 2 × 462 + 147, then 462 = 3 × 147 + 21, then 147 = 7 × 21 + 0. The GCF is 21. The method needs only a handful of divisions even for numbers with many digits.
More than two numbers
The operation can be chained because gcd(a, b, c) = gcd(gcd(a, b), c). The table above shows each pair in turn, with the running result carried forward. The order of the numbers does not change the final answer.
What the GCF is used for
- Reducing fractions. Dividing numerator and denominator by their GCF gives the lowest terms in one step.
- Simplifying ratios. The same division reduces 12 : 18 to 2 : 3.
- Equal grouping. The GCF of 48 and 18 is 6, so 48 items and 18 items can each be split into identical groups of at most 6 per group with nothing left over.
- Factoring. Pulling out a common factor is the first step in factorising expressions with whole-number coefficients.
Checking your answer by hand
Two quick checks catch most slips. First, the GCF must divide every input exactly, so divide each number by it and confirm there is no remainder. Second, the quotients you get must themselves be coprime, meaning their GCF is 1. For 48 and 18 the GCF 6 gives 8 and 3, which share no factor, so 6 cannot be made larger. If the quotients still share a factor, the number you found was a common factor but not the greatest one. Listing factors works for small numbers, but the Euclidean steps stay short even for twelve-digit inputs.
Useful facts and limits
If the GCF is 1 the numbers are coprime, even when none of them is prime on its own, as with 8 and 15. The GCF of two numbers multiplied by their least common multiple equals their product, which is why the matching LCM is shown. Both are linked to the LCM calculator. This page accepts positive whole numbers up to one trillion; negative numbers and decimals are outside its scope. For fractions, use the fraction calculator.
Worked example
A classic pair for the Euclidean algorithm: 1071 and 462. Three divisions are enough to reach the answer.
Inputs
| Whole numbers | 1071, 462 |
|---|
Result
Greatest common factor of 1071, 462.
| GCF (GCD) | 21 |
|---|---|
| Matching LCM | 23562 |
| Numbers divided by the GCF | 51, 22 |
Euclidean algorithm steps (remainder 0 ends each pair)
| Division | Remainder |
|---|---|
| 1071 = 2 × 462 + 147 | 147 |
| 462 = 3 × 147 + 21 | 21 |
| 147 = 7 × 21 + 0 | 0 |
Accuracy note: Results use standard double-precision arithmetic, so very large or very small values may be rounded. Check important results by another method.
Frequently asked questions
Are GCF, GCD and HCF the same thing?
Yes. Greatest common factor, greatest common divisor and highest common factor all name the largest whole number that divides every number in the list exactly.
What is the GCF of 48 and 18?
Both divide by 6 and no larger number divides both, so the GCF is 6. Euclid: 48 = 2 × 18 + 12, 18 = 1 × 12 + 6, 12 = 2 × 6 + 0.
What does it mean if the GCF is 1?
The numbers share no common factor other than 1 and are called coprime or relatively prime. A fraction with a coprime numerator and denominator is already in lowest terms.
Can I find the GCF of three or more numbers?
Yes. Find the GCF of the first two, then find the GCF of that result with the next number, and continue. This calculator accepts up to twelve numbers.
How does the GCF relate to the LCM?
For two numbers, GCF × LCM = the product of the numbers. Knowing one gives the other quickly.
Related calculators
References and sources
- Euclid, Elements Book VII, Propositions 1 and 2: the original statement of the Euclidean algorithm.
- Knuth, D. E., The Art of Computer Programming, Volume 2, for the analysis of the algorithm.