What the greatest common factor actually is
The greatest common factor of a set of whole numbers is the largest number that divides all of them exactly. British textbooks call it the highest common factor (HCF); number theorists call it the greatest common divisor (GCD). All three names describe the same object, and this calculator uses them interchangeably.
Take 48 and 180. The factors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24 and 48. The factors of 180 are 1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90 and 180. The numbers appearing in both lists are 1, 2, 3, 4, 6 and 12 — six of them — and the largest is 12. That is the GCF, and the count of six is what this calculator reports as the number of shared factors.
Notice something about that list of six: every one of them divides 12. This is not a coincidence, and it is the single most useful fact about the GCF. The common factors of a set of numbers are exactly the divisors of their greatest common factor. So once you have the GCF you have the whole list, which is why the calculator can report how many common factors exist without ever enumerating them.
You reach for the GCF whenever something has to be split into equal whole parts. Reducing a fraction to lowest terms means dividing numerator and denominator by their GCF. Writing a ratio in simplest form is the same operation. Cutting a 48-inch board and a 180-inch board into identical pieces with nothing left over means cutting 12-inch pieces — four from the first, fifteen from the second.
Why the Euclidean algorithm works
You could find the GCF by listing every factor of every number, but that becomes hopeless past a few thousand. Euclid's method, set out in Book VII of the Elements around 300 BC, replaces the search with a short chain of divisions and is still the algorithm every computer-algebra system uses.
The whole method rests on one observation. Suppose d divides both a and b. Write the division of a by b as a = q·b + r. Then r = a − q·b, and since d divides a and divides b, it divides that whole right-hand side — so d divides r too. Run the argument backwards and any divisor of b and r also divides a. The pair (a, b) and the pair (b, r) therefore have identical sets of common divisors, so they have the same greatest one.
That gives you a rewrite rule: replace (a, b) with (b, a mod b) and the answer does not change. Each rewrite makes the second number strictly smaller, so the process has to stop, and it stops when the remainder hits zero. At that point the pair is (d, 0), and since everything divides zero, the greatest common divisor of that pair is simply d. The last non-zero remainder is the answer.
The method is fast in a way that is easy to underestimate. Two consecutive Fibonacci numbers are the worst possible input, and even then the number of divisions grows only in proportion to the number of digits. Numbers with hundreds of digits are handled in well under a hundred steps, which is why RSA key generation leans on it.
For three or more numbers you do not need a new idea. Because any common divisor of a, b and c is a common divisor of gcd(a, b) and c, you can fold the list: gcd(a, b, c) = gcd(gcd(a, b), c). This calculator folds left to right, which is why the step list shows one Euclidean chain followed by a folding step.
Worked example: the GCF of 48 and 180, done twice
Method 1 — the Euclidean algorithm. Start with the larger number on the left.
- 180 ÷ 48 = 3 remainder 36, because 3 × 48 = 144 and 180 − 144 = 36. Write
180 = 3×48 + 36. - Now use the pair (48, 36). 48 ÷ 36 = 1 remainder 12:
48 = 1×36 + 12. - Now the pair (36, 12). 36 ÷ 12 = 3 remainder 0:
36 = 3×12 + 0. - The remainder is zero, so the last non-zero remainder, 12, is the GCF. Three divisions, no factor lists.
Method 2 — prime factorization. Break each number into primes with repeated division:
- 48 = 2 × 24 = 2 × 2 × 12 = 2 × 2 × 2 × 6 = 2⁴ × 3.
- 180 = 2 × 90 = 2 × 2 × 45 = 2² × 9 × 5 = 2² × 3² × 5.
- Take each prime that appears in both lists, raised to the lower of the two exponents. For 2 that is min(4, 2) = 2. For 3 that is min(1, 2) = 1. The prime 5 appears only in 180, so it contributes nothing.
- GCF = 2² × 3¹ = 4 × 3 = 12. The two methods agree, as they must.
The LCM comes free. Swap “lower exponent” for “higher exponent” and you get the least common multiple: 2⁴ × 3² × 5 = 16 × 9 × 5 = 720. Check it against the product rule: 48 × 180 = 8,640, and 8,640 ÷ 12 = 720. ✓
How many common factors? The GCF is 12 = 2² × 3, so its divisor count is (2 + 1) × (1 + 1) = 6 — matching the six numbers 1, 2, 3, 4, 6, 12 found by hand earlier.
How to read the result
A GCF of 1 means the numbers are coprime. They share no prime factor at all. Coprime does not mean either number is prime — 35 and 64 are coprime and neither is prime. When a fraction's numerator and denominator are coprime, the fraction is already in lowest terms and cannot be reduced further.
A GCF equal to the smaller number means that number divides the other one. gcd(64, 1024) = 64 tells you 64 goes into 1024 exactly. Whenever the answer equals one of your inputs, you have found a divisibility relationship, not just a shared factor.
The GCF can never exceed the smallest number you entered, and it is always at least 1. If you get an answer larger than your smallest input, you have mistyped something.
The count of common factors is worth a second look because it grows with the structure of the GCF, not its size. A GCF of 64 = 2⁶ has seven divisors; a GCF of 60 = 2²·3·5, though smaller, has (2+1)(1+1)(1+1) = 12. Numbers built from many distinct small primes are the ones with lots of factors, which is exactly why 12, 24, 60 and 360 turn up so often in units of measurement.
Finally, treat the least common multiple as the mirror image of the answer. The GCF is the largest number that goes into both; the LCM is the smallest number both go into. Their product is the product of the two original numbers, every time, for a pair — which is the identity the LCM calculator is built on.
GCF and LCM of some standard pairs
| a | b | a in primes | b in primes | GCF | LCM | a × b |
|---|---|---|---|---|---|---|
| 12 | 18 | 2²·3 | 2·3² | 6 | 36 | 216 |
| 48 | 180 | 2⁴·3 | 2²·3²·5 | 12 | 720 | 8,640 |
| 35 | 64 | 5·7 | 2⁶ | 1 | 2,240 | 2,240 |
| 100 | 75 | 2²·5² | 3·5² | 25 | 300 | 7,500 |
| 270 | 192 | 2·3³·5 | 2⁶·3 | 6 | 8,640 | 51,840 |
| 1,071 | 462 | 3²·7·17 | 2·3·7·11 | 21 | 23,562 | 494,802 |
| 1,024 | 64 | 2¹⁰ | 2⁶ | 64 | 1,024 | 65,536 |
Check any row: 21 × 23,562 = 494,802, which is 1,071 × 462. The identity holds for pairs only — it does not extend unchanged to three or more numbers.
The product rule does not survive a third number
For two numbers, GCF × LCM = a × b. For three it fails. Take 48, 180 and 210: the GCF is 6 and the LCM is 5,040, so the product of the two is 30,240 — while 48 × 180 × 210 = 1,814,400. Students reach for the two-number shortcut on a three-number problem constantly, and it is wrong every time the three numbers share a prime unevenly. For three or more numbers, fold pairwise or use the prime-exponent method: minimum exponents for the GCF, maximum exponents for the LCM.
Mistakes that produce the wrong GCF
- Stopping at the first common factor you notice. 4 divides both 48 and 180, but so does 12. The greatest common factor is the one you want; a smaller common factor still leaves the fraction reducible.
- Multiplying every shared prime instead of taking the lower exponent. Both 48 and 180 contain 2 and 3, but 48 has 2⁴ and 180 has 2². You take 2², not 2⁶.
- Including a prime that appears in only some of the numbers. 5 divides 180 but not 48, so it plays no part in the GCF — even though it belongs in the LCM.
- Forgetting that 1 is always a common factor. When no prime is shared, the answer is 1, not “none”. Every pair of integers has a greatest common factor.
- Using the two-number product rule on three numbers. See the callout above.
- Confusing factors with multiples. Factors divide into the number and are never larger than it; multiples are built from it and are never smaller. Reducing a fraction needs the GCF; adding fractions needs the LCM.
- Feeding in a decimal. Divisibility is a property of integers. Scale 1.2 and 1.8 up to 12 and 18 first, take the GCF of those, then scale the answer back down.
Where the GCF fits among related tools
The GCF and the LCM are the two halves of the same idea and they show up on opposite sides of fraction arithmetic. You need the GCF to simplify: divide numerator and denominator by it and the fraction is in lowest terms. You need the LCM to combine: adding or subtracting fractions requires a common denominator, and the least common denominator is the LCM of the two denominators.
Underneath both sits the fundamental theorem of arithmetic: every integer greater than 1 factors into primes in exactly one way, apart from the order of the factors. That uniqueness is what makes “take the lower exponent” a well-defined instruction, and it is the reason the two methods in the worked example cannot disagree. If you want the factorizations themselves, use the prime factorization calculator.
Two extensions are worth knowing about. The extended Euclidean algorithm tracks integers x and y alongside the remainders so that it finishes with a·x + b·y = gcd(a, b) — Bézout's identity — which is how modular inverses and RSA private keys are computed. And the same rewrite rule works on polynomials, where it produces the greatest common divisor of two polynomials and underpins partial-fraction decomposition.
If you are here to reduce a fraction rather than to study the algorithm, the simplifying fractions calculator applies the GCF for you in one step. To see the divisions themselves laid out digit by digit, use the long division calculator.
Key terms
- Factor (divisor)
- A whole number that divides another exactly, leaving remainder 0. 12 is a factor of 48 because 48 ÷ 12 = 4 with nothing left over.
- Common factor
- A number that is a factor of every number in your set. Every common factor of a set divides the set's greatest common factor.
- Coprime (relatively prime)
- Two or more integers whose greatest common factor is 1. They need not be prime themselves — 8 and 9 are coprime.
- Bézout's identity
- For any integers a and b there exist integers x and y with a·x + b·y = gcd(a, b). The extended Euclidean algorithm finds them.
- Fundamental theorem of arithmetic
- Every integer above 1 has exactly one prime factorization, up to the order of the factors. It is what makes the min-exponent rule valid.