Greatest Common Factor Calculator - GCF, GCD, and HCF

The greatest common factor of a set of positive integers is the largest positive integer that divides every member of the set. U.S. elementary books usually print GCF. Number theory, programming languages, and this site’s code comments usually print GCD (greatest common divisor). Many UK and Commonwealth curricula print HCF (highest common factor). For positive integers the three abbreviations are synonyms. This calculator treats them as the same output.

The default example is 48, 18, 30 → GCF 6. Shared positive divisors of those three numbers are 1, 2, 3, and 6; 6 is the greatest. You can check by dividing: 48 ÷ 6 = 8, 18 ÷ 6 = 3, 30 ÷ 6 = 5, and 8, 3, and 5 are coprime as a triple (no integer greater than 1 divides all three). When the GCF is at most one billion, the page also lists every common factor - they are exactly the divisors of the GCF.

Computation uses the Euclidean algorithm with BigInt, folded across the list: gcd(a, b, c) = gcd(gcd(a, b), c). That is faster than intersecting three complete factor lists, and it works for integers far larger than 48. Listing common factors is the slow part, which is why it is skipped when GCF > 10⁹ even though the GCF itself remains exact. For the opposite problem - smallest shared multiple - use the least common multiple calculator. For a combined table, see the common factor calculator. For one integer’s complete divisor list, see the factor calculator.

Using this greatest common factor finder is straightforward:

1. Paste at least two positive integers in the textarea. Commas, spaces, or new lines are all fine. The default is 48, 18, 30.
2. Read the GCF. If it is ≤ 1,000,000,000, read the common-factor chips; the GCF chip is highlighted.
3. Copy the summary, or clear the box. The last list is saved locally for up to 30 days.

Note: zero is rejected. gcd(a, 0) = |a| is a programming convention, not a grade-school GCF exercise.

Euclid’s observation is that any common divisor of a and b is also a common divisor of b and the remainder a − qb. Repeating that replacement shrinks the numbers without changing the GCF. It does not require listing factors at all.

Worked remainder chain for 48 and 18

• 48 = 2 × 18 + 12
• 18 = 1 × 12 + 6
• 12 = 2 × 6 + 0
• Last non-zero remainder: 6

Fold in 30

• gcd(6, 30): 30 = 5 × 6 + 0
• So gcd(48, 18, 30) = 6

Binary GCD (Stein’s algorithm) and Lehmer’s GCD are faster for huge integers in a C library. For a browser calculator, the plain remainder loop on BigInt is simple, exact, and fast enough for 500-digit inputs. This page does not switch algorithms behind your back.

If d divides every number in the set, then d divides the GCF (because the GCF is an integer linear combination of the numbers - Bézout - and any common divisor divides that combination). Conversely, every divisor of the GCF divides every original number. So the common-factor list is not a separate search: it is the factor list of one integer, the GCF. For GCF = 6 that list is 1, 2, 3, 6. Listing is skipped above 10⁹ for the same reason a factor calculator caps a trial-division loop: √(10⁹) is already 31,623 iterations; √(a 40-digit GCF) is not a UI feature.

A fraction a/b in lowest terms is the unique (positive) representation where gcd(a, b) = 1. To reduce 48/18, compute gcd(48, 18) = 6 and divide both parts: 8/3. Mixed numbers should be written as improper fractions first. If you need the reduced fraction typeset with a bar, jump to the fraction calculator after you read the GCF here. Canceling “any” common factor (dividing 48/18 by 2 to get 24/9) is valid but incomplete; only dividing by the GCF finishes the job in one step.

The same GCF appears when you scale ratios, simplify unit rates, and cancel in rational algebraic expressions whose coefficients are integers. Polynomial GCD is a different algorithm (Euclid on polynomials) and is not this page.

For two positive integers, gcd(a, b) × lcm(a, b) = a × b. From gcd(48, 18) = 6 you can recover lcm(48, 18) = 48 × 18 / 6 = 144 without listing multiples. The identity fails to extend naively to three numbers: gcd(48, 18, 30) × lcm(48, 18, 30) is not 48 × 18 × 30. Use the LCM calculator when the least common multiple is the unknown; do not multiply three inputs and divide by this GCF.

In prime-power language, GCF keeps the minimum exponent of each prime and LCM keeps the maximum. 48 = 2⁴ × 3, 18 = 2 × 3², 30 = 2 × 3 × 5. Minimum exponents: 2¹ × 3¹ = 6. Maximum exponents (for LCM of the triple): 2⁴ × 3² × 5 = 720.

Grade-school GCF is often taught as “list the factors, star the ones that appear in every list, pick the largest star.” For 48 the factors are 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. For 18: 1, 2, 3, 6, 9, 18. For 30: 1, 2, 3, 5, 6, 10, 15, 30. The intersection is 1, 2, 3, 6 - which is exactly the divisor list of 6, the GCF this page prints. Listing is honest for two-digit homework and collapses for 12-digit homework. Euclid does not care how many factors 48 has; it only cares about remainders. Use listing to believe the definition, then use Euclid to compute.

The subtractive version of Euclid (repeatedly replace the larger number by the difference of the two) is what Euclid’sElements actually describes. It yields the same GCF and can take many more steps: gcd(48, 18) by subtraction is 48−18=30, 30−18=12, 18−12=6, 12−6=6, 6−6=0. The modern remainder form is the subtraction loop with the obvious shortcut of doing many subtractions at once (division). This calculator uses remainders, not a hundred subtractions.

Coprime triples. gcd(8, 9, 25) = 1 even though none of the pairwise gcds is 1 wait - gcd(8,9)=1 already, so the triple is 1. A more interesting pattern is pairwise sharing without a triple share: gcd(6, 10, 15) = 1 because 6 and 10 share 2, 6 and 15 share 3, 10 and 15 share 5, and nothing bigger than 1 divides all three. Pairwise GCF is not the same as GCF of the set. Always fold the whole list; do not average the pairwise answers.

gcd(100, 45, 80). gcd(100, 45) = 5, then gcd(5, 80) = 5. Common factors 1 and 5. gcd(96, 36, 60) = 12; common factors 1, 2, 3, 4, 6, 12.gcd(17, 19, 23) = 1 (three primes).gcd(81, 27, 9) = 9, and 9 already divides both of the others so the GCF equals the smallest input. Whenever the smallest input divides all the others, you can stop: that smallest input is the GCF.

Negative integers and gcd in programming: most libraries return a non-negative gcd, with gcd(a, 0) = |a|. This page refuses negatives and zero so a fourth-grade word problem cannot accidentally hit a programming convention. If you need gcd of integers that may be zero, a computer-algebra prompt is the right tool, not a GCF worksheet helper.

A fraction-reduction drill: 96/36. gcd = 12, so 8/3. 100/45 reduces by 5 to 20/9. 48/18 reduces by 6 to 8/3 - same reduced fraction as 96/36, which is how you notice 96/36 = 48/18 = 8/3. That observation is the GCF doing its job, not a coincidence of the decimal expansion.

If you already have prime factorizations, GCF is the product of shared primes raised to the minimum exponent. You do not need that factorization to run this page, and factoring a 40-digit integer can be harder than Euclid on the same integer. That is the whole point of the remainder algorithm: it finds the greatest shared factor without finding any prime. For classroom numbers the two methods agree, which is a useful check: factor 48 as 2⁴×3, 18 as 2×3², 30 as 2×3×5, min exponents 2¹×3¹ = 6, matching Euclid.

Unique factorization is why the min-exponent recipe works. It is also why 1 cannot be prime: if 1 were a prime, the “min exponent of 1” would be a nonsense extra factor in every GCF. Keep 1 in the common-factor list (it always divides) and out of the prime list.

Euclid is easier to trust after two or three fully written chains besides the default 48 and 18. gcd(252, 198): 252 = 1×198 + 54, 198 = 3×54 + 36, 54 = 1×36 + 18, 36 = 2×18 + 0, so GCF = 18. Both 252 and 198 are multiples of 18 (14 and 11). gcd(1071, 462): 1071 = 2×462 + 147, 462 = 3×147 + 21, 147 = 7×21 + 0, so GCF = 21. Fibonacci-adjacent pairs are the slow case: consecutive Fibonacci numbers are coprime, and Euclid takes a step for each remainder, which is why Fibonacci inputs are the worst case of the algorithm. gcd(89, 55) still finishes instantly in a browser: 89 = 1×55 + 34, 55 = 1×34 + 21, 34 = 1×21 + 13, 21 = 1×13 + 8, 13 = 1×8 + 5, 8 = 1×5 + 3, 5 = 1×3 + 2, 3 = 1×2 + 1, 2 = 2×1 + 0, GCF = 1.

For three numbers, never skip the fold. gcd(252, 198, 36) starts from gcd(252, 198) = 18, then gcd(18, 36) = 18. Adding 36 did not change the GCF because 18 already divides 36. Adding 10 would: gcd(18, 10) = 2. The common-factor chips would then shrink from the divisors of 18 (1, 2, 3, 6, 9, 18) to the divisors of 2 (1, 2). Watching the chip list shorten as you paste a new coprime-ish integer is the fastest way to feel what “greatest common” means.

Integer coefficients in a linear combination also reveal the GCF. Bézout’s identity says gcd(a, b) is the smallest positive integer of the form ax + by with x, y integers (possibly negative). 18 = 252×(−3) + 198×4, for example, after back-substitution of the remainder chain. This page does not print the Bézout coefficients - that is extended Euclid - but it prints the GCF those coefficients must generate. If a contest problem asks for x and y as well, run extended Euclid on paper using the same remainders you just checked here.

A last classroom pattern: GCF of a stack of even numbers is at least 2; GCF of consecutive integers is 1; GCF of an even and an odd may still exceed 1 (gcd(15, 25) = 5). Parity is a hint, not a proof. Always finish Euclid.