GCD & LCM Calculator

How to use GCD & LCM Calculator

1. Enter two or more whole numbers.
2. Read the GCD and LCM, with the Euclidean steps shown.
3. Use the GCD to reduce a fraction, or the LCM to find a common denominator.
4. The GCD of any number and 0 is that number; the LCM of anything with 0 is 0.
5. A GCD of 1 means the numbers are coprime.
6. Negative inputs are treated by magnitude — divisors are conventionally positive.

How the GCD is actually computed

Not by factorising — that is slow. Euclid’s algorithm repeatedly replaces the larger number with its remainder when divided by the smaller, until the remainder is zero; the last non-zero value is the GCD. For 48 and 18: 48 mod 18 is 12, 18 mod 12 is 6, 12 mod 6 is 0, so the answer is 6. It takes only a handful of steps even for enormous numbers, which is why it is around 2,300 years old and still the algorithm every computer uses.

The LCM comes free

Once you have the GCD, the LCM is a × b ÷ GCD. For 4 and 6: 24 ÷ 2 = 12. The relationship is exact and holds for any pair, which is why no separate algorithm is needed. For more than two numbers, fold: the LCM of a, b and c is the LCM of (the LCM of a and b) and c. Note that a × b can overflow long before the LCM does, so careful implementations divide before multiplying.

What each one is for

GCD reduces fractions: 18/24 divided through by their GCD of 6 gives 3/4. It also answers tiling and cutting questions — the largest square tile that fills a 48 by 18 room without cutting is 6 units. It is the basis of the RSA key-generation step that checks an exponent is coprime to the totient. LCM finds common denominators, and answers the recurrence question: two buses leaving every 12 and 18 minutes coincide every 36.

Coprime numbers

When the GCD is 1 the numbers are coprime — they share no factor but 1, even if neither is prime. 8 and 15 are coprime. That property matters more than it looks: coprime gear tooth counts spread wear evenly rather than mating the same pair each revolution, coprime hash table strides visit every slot, and coprimality is the condition that makes modular inverses exist, which is what public-key cryptography rests on.