The greatest common factor of two numbers is the largest number that divides both without a remainder. It is the tool you reach for when simplifying a fraction, splitting a quantity into equal groups, or reducing a ratio to its simplest form. Its counterpart, the least common multiple, answers the opposite question: the smallest number both divide into.
The two are linked by a neat identity — GCF(a, b) × LCM(a, b) = a × b — so finding one immediately gives you the other.
Three ways to find it
- Listing factors: write out every factor of each number and take the largest shared one. Fine for small numbers, impractical beyond about a hundred.
- Prime factorisation: break both into primes and multiply the shared ones. 48 = 2⁴×3 and 60 = 2²×3×5, so the GCF is 2²×3 = 12.
- Euclidean algorithm: divide the larger by the smaller, replace the pair with the divisor and remainder, repeat until the remainder is zero. Fast enough for numbers of any size, which is why computers use it.
The Euclidean algorithm worked through
Take 1,071 and 462. 1,071 ÷ 462 leaves 147. Now take 462 and 147: that leaves 21. Now 147 and 21: the remainder is zero, so the GCF is 21. Three steps, no factorisation, and the method dates to Euclid around 300 BC — it is among the oldest algorithms still in everyday use.
Where it is genuinely useful
- Simplifying fractions: divide numerator and denominator by their GCF to reach lowest terms in one step. 18/24 with a GCF of 6 becomes 3/4.
- Dividing into equal groups: 24 pens and 36 pencils split into at most 12 identical packs.
- Reducing ratios: 45:60 simplifies to 3:4.
- Tiling and layout: the largest square tile that fits a room exactly is the GCF of its dimensions.
- Cryptography: the Euclidean algorithm underpins the key generation used in RSA.
Edge cases
The GCF of any number and zero is that number, since everything divides zero. Two numbers whose only common factor is 1 are called coprime — 8 and 15, for instance — and coprimality, not primality, is what matters in most number-theory applications. Prime numbers are automatically coprime with everything they do not divide.
Related tools
- Fraction Calculator — simplification applied
- Factorial Calculator
- Scientific Calculator
- Browse all free tools