Greatest Common Factor

This GCF calculator finds the largest number dividing all inputs, using the Euclidean algorithm — the oldest algorithm still in common use. The LCM is computed alongside via the identity lcm(a, b) × gcd(a, b) = a × b.

The Euclidean Algorithm

Instead of listing every factor, Euclid's method replaces the larger number with the division remainder until one reaches zero: gcd(48, 72) = gcd(48, 24) = gcd(24, 0) = 24, then gcd(24, 36) = 12, and gcd(12, 60) = 12. Each step shrinks the numbers dramatically, so even large inputs resolve in a handful of iterations.

Where GCF Shows Up

Simplifying fractions, factoring expressions, finding common denominators, distributing items into equal groups, and solving modular arithmetic problems all reduce to finding the GCF first.