What is the difference between GCD and LCM?

GCD is the largest number that divides all your values; LCM is the smallest number they all divide into. GCD is at most the smallest value, LCM at least the largest.

How does the Euclidean algorithm work?

Divide the larger number by the smaller, then repeat using the divisor and remainder until the remainder is zero. The last non-zero divisor is the GCD.

How do I find the LCM quickly?

Multiply the two numbers and divide by their GCD, since GCD times LCM always equals the product of the pair.

What does coprime mean?

Two numbers with a GCD of 1. They share no common factors, so a fraction made from them is already in lowest terms.

GCD and LCM Calculator - Highest Common Factor

GCD and LCM Calculator

The greatest common divisor is the largest number dividing all your values; the lowest common multiple is the smallest number they all divide into. Both come up constantly in fractions.

Formula

GCD × LCM = a × b

GCD is the largest number dividing both; LCM is the smallest both divide
Euclid: GCD(a, b) = GCD(b, a mod b) until the remainder is zero

12 and 18: GCD 6, LCM 36, and 6 × 36 = 216 = 12 × 18

Finding the GCD

The Euclidean algorithm is far faster than listing factors: divide the larger number by the smaller, then repeat with the divisor and the remainder until the remainder is zero. The last non-zero divisor is the GCD.

For 12 and 18: 18 ÷ 12 leaves 6; 12 ÷ 6 leaves 0. The GCD is 6.

Also called the highest common factor, and it is what you divide by to simplify a fraction to lowest terms.

Finding the LCM

Once you have the GCD, the LCM follows immediately:

LCM = (a × b) ÷ GCD

For 12 and 18: (12 × 18) ÷ 6 = 36.

This works because GCD × LCM = a × b for any pair — 6 × 36 = 216 = 12 × 18. A useful check on your arithmetic.

Where They Are Used

GCD simplifies fractions and reduces ratios. LCM gives the common denominator when adding fractions with different bottoms, and answers scheduling questions: two buses leaving every 12 and 18 minutes coincide every 36.

Numbers whose GCD is 1 are called coprime. They share no factors, which is why 8/15 cannot be simplified even though neither number is prime.

Quick Reference

Worked pairs, showing the product rule holding each time.
a	b	GCD	LCM	GCD × LCM	a × b
12	18	6	36	216	216
8	12	4	24	96	96
7	13	1	91	91	91
24	36	12	72	864	864

Frequently Asked Questions

What is the difference between GCD and LCM?: GCD is the largest number that divides all your values; LCM is the smallest number they all divide into. GCD is at most the smallest value, LCM at least the largest.
How does the Euclidean algorithm work?: Divide the larger number by the smaller, then repeat using the divisor and remainder until the remainder is zero. The last non-zero divisor is the GCD.
How do I find the LCM quickly?: Multiply the two numbers and divide by their GCD, since GCD times LCM always equals the product of the pair.
What does coprime mean?: Two numbers with a GCD of 1. They share no common factors, so a fraction made from them is already in lowest terms.