Find the greatest common factor (GCF) of 2 or more integers. Euclid's algorithm and prime factorization steps are both shown. The least common multiple (LCM) is also computed.
Enter 2 or 3 positive integers. Leave the third blank to find GCF of two numbers.
The greatest common factor of two integers is the largest number that divides both of them with no remainder. There are two standard methods: Euclid's algorithm and the prime factorization method.
The GCF is useful for simplifying fractions. If you want to reduce 36/48 to lowest terms, divide both by their GCF of 12: 36/12 = 3 and 48/12 = 4, giving 3/4.
The prime factorization method links directly to the factoring calculator, where you can get the full factor breakdown for each number before comparing them. For rounding results to a specific number of significant figures, try the rounding calculator.
For a formal treatment, see Wolfram MathWorld on the greatest common divisor.
The greatest common factor (GCF) of two or more integers is the largest integer that divides all of them with no remainder. For 48 and 36, the GCF is 12, because 12 is the largest number that divides both evenly. It is also called the greatest common divisor (GCD).
Divide the larger number by the smaller and take the remainder. Replace the larger with the smaller and the smaller with the remainder. Repeat until the remainder is 0. The last non-zero remainder is the GCF. For 48 and 36: 48 mod 36 = 12, then 36 mod 12 = 0, so GCF = 12.
Factor each number into primes. The GCF is the product of the prime factors they share, each raised to the lowest power it appears in any of the numbers. For 48 = 2^4 x 3 and 36 = 2^2 x 3^2, the shared primes are 2^2 and 3^1, so GCF = 4 x 3 = 12.
The least common multiple (LCM) is the smallest positive integer that is divisible by all the numbers. For any two integers a and b, LCM(a, b) = (a x b) / GCF(a, b). For 48 and 36: LCM = (48 x 36) / 12 = 144.
A GCF of 1 means the numbers share no common prime factors. They are called coprime, or relatively prime. For example, 8 and 15 are coprime because 8 = 2^3 and 15 = 3 x 5 share no prime factors.
Editor at Encore Editorial, Chris Terry sets the editorial standards here and turns dense topics into plain English. He has written widely on education, finance, and consumer markets.