GCF and LCM Calculator

How it works

The greatest common factor (GCF, also called the greatest common divisor or highest common factor) is the largest whole number that divides every number you entered. The least common multiple (LCM) is the smallest positive whole number that every one of them divides into.

The GCF is found with the Euclidean algorithm: divide the larger number by the smaller, replace the larger with the remainder, and repeat until the remainder is zero. The last non-zero remainder is the GCF. For three or four numbers the algorithm runs on the first two, then on that result and the next number, and so on.

The LCM of two numbers is their product divided by their GCF. For more numbers the same rule is applied one number at a time. The prime-factor comparison shows the same answers a different way: the GCF takes the lowest power of every prime the numbers share, and the LCM takes the highest power of every prime that appears in any of them.

Use the GCF to reduce a fraction or to find the largest equal pieces something can be cut into; use the LCM to find a common denominator or when repeating events next coincide.

Formula

gcd(a, b) = gcd(b, a mod b)       gcd(a, 0) = a     (Euclidean algorithm)
lcm(a, b) = |a × b| ÷ gcd(a, b)
gcd(a, b, c) = gcd(gcd(a, b), c)   lcm(a, b, c) = lcm(lcm(a, b), c)

Example

For 12, 18 and 30: gcd(12, 18) runs 18 = 1 × 12 + 6, then 12 = 2 × 6 + 0, so gcd(12, 18) = 6; then 30 = 5 × 6 + 0, so the GCF of all three is 6. The LCM is lcm(lcm(12, 18), 30) = lcm(36, 30) = 36 × 30 ÷ 6 = 180.

By prime factors, 12 = 2^2 × 3, 18 = 2 × 3^2 and 30 = 2 × 3 × 5. The lowest shared powers are 2 × 3 = 6 (the GCF); the highest powers are 2^2 × 3^2 × 5 = 180 (the LCM).

For 1,071 and 462: 1,071 = 2 × 462 + 147, 462 = 3 × 147 + 21, 147 = 7 × 21 + 0, so the GCF is 21 and the LCM is 1,071 × 462 ÷ 21 = 23,562.

Assumptions and limitations

• Inputs must be whole numbers. Negative numbers are allowed and are treated as their absolute value, because factors and multiples are defined on magnitudes: the GCF of −12 and 18 is 6.
• Numbers 1 and 2 are required and cannot be zero. Numbers 3 and 4 are optional; a blank or 0 in either is ignored rather than treated as a value.
• Each number can be at most 1,000,000,000,000 (10^12), and the LCM must fit in 9,007,199,254,740,991 (2^53 − 1) to be shown exactly.
• The GCF of two numbers that share no prime factor is 1; such numbers are called coprime, and their LCM is their product.

Frequently asked questions