GCF Calculator: greatest common factor with steps

How it works

Euclid: GCF(a, b) = GCF(b, a mod b), repeated until the remainder is 0; the last non-zero divisor is the GCF · More numbers: GCF(a, b, c) = GCF(GCF(a, b), c) · Prime factors: GCF = product of the shared primes, each at its lowest power · LCM(a, b) = a × b ÷ GCF(a, b)

The greatest common factor (GCF) is the largest whole number that divides every number in the list with no remainder. It is also called the greatest common divisor (GCD) or highest common factor (HCF). The calculator uses Euclid’s algorithm, which works quickly even for 12-digit numbers: divide the larger number by the smaller, replace the larger with the remainder, and repeat; the last non-zero divisor is the GCF. For three or more numbers it takes the GCF of the first two, then of that result and the next number, and so on. The steps show each division. It also factors every number into primes. The GCF is the product of the primes that all the numbers share, each raised to the lowest power it appears with, and the common factors are all the divisors of the GCF. Dividing each number by the GCF gives the smallest whole numbers in the same ratio, which is how fractions and ratios are reduced. The least common multiple is shown too, since GCF × LCM = a × b for two numbers. Zeros are skipped (every number divides 0) and negative signs are ignored.

Worked example

For 24 and 36 (the defaults): 36 = 1 × 24 + 12, then 24 = 2 × 12 + 0, so the GCF is 12. By prime factors, 24 = 2³ × 3 and 36 = 2² × 3²; the shared primes at their lowest power are 2² × 3 = 12. The common factors are 1, 2, 3, 4, 6 and 12, the numbers divided by the GCF are 2 and 3, and the least common multiple is 24 × 36 ÷ 12 = 72.

Sources: CalculatorSoup: Greatest Common Factor Calculator (methods and examples) · Calculator.net: GCF Calculator (prime factorization and Euclid examples) · Euclidean algorithm (Wikipedia)

Frequently asked questions