GCD / LCM Calculator

About this tool

Find the greatest common divisor and least common multiple of two or more whole numbers — useful for simplifying fractions to lowest terms, finding a common denominator, or solving classic scheduling/repeating-cycle math problems.

The Euclidean algorithm. Finding the GCD of two numbers doesn't require checking every possible divisor — the Euclidean algorithm gets there in a handful of steps by repeatedly replacing the larger number with the remainder of dividing it by the smaller, until the remainder hits zero. For 12 and 18: 18 ÷ 12 leaves remainder 6, then 12 ÷ 6 leaves remainder 0, so the GCD is the last non-zero remainder, 6. This is one of the oldest algorithms in mathematics, dating to Euclid's Elements around 300 BCE, and it's still the standard method because it converges so fast — even for enormous numbers, it typically needs only a few dozen steps.

GCD and LCM are linked by a simple identity: for any two numbers, GCD(a,b) × LCM(a,b) = a × b. Once you have the GCD, the LCM falls out directly as (a × b) ÷ GCD(a,b) — which is exactly how this tool computes it, rather than searching for multiples directly.

Worked example. For 12, 18, and 30: the GCD is 6 (the largest number dividing all three evenly — 12÷6=2, 18÷6=3, 30÷6=5), and the LCM is 180 (the smallest number all three divide into evenly — 180÷12=15, 180÷18=10, 180÷30=6).

More than two numbers. GCD and LCM both extend cleanly beyond two inputs by combining them pairwise: GCD(a,b,c) = GCD(GCD(a,b), c), and the same pairwise approach works for LCM. The order the numbers are combined in doesn't matter — GCD and LCM are both associative, so the final answer is the same regardless of which pair is combined first.

Where this shows up in practice: reducing a fraction to lowest terms (divide numerator and denominator by their GCD), finding a common denominator to add or compare fractions (their LCM), scheduling repeating events that need to line up (two processes running every 12 and 18 seconds next align after their LCM, 36 seconds), and gear-ratio or tiling problems where whole-number repeats matter.

To apply the GCD directly to simplify a fraction, use the fraction converter; for scaling a ratio to its simplest whole-number form, the ratio calculator. Since the Euclidean algorithm's remainder-based logic underlies primality testing too, see the prime checker for a related number-theory tool.

Frequently asked questions

What is GCD used for?

The GCD (also called GCF, greatest common factor) is the largest number that divides all your inputs evenly — it's exactly what you divide a fraction's numerator and denominator by to simplify it to lowest terms.

What is LCM used for?

The LCM is the smallest number that all your inputs divide into evenly — commonly needed to find a common denominator when adding or comparing fractions, or to figure out when repeating events (like two blinking lights) line up again.

How is this calculated for more than two numbers?

Using the Euclidean algorithm pairwise: GCD(a,b,c) = GCD(GCD(a,b),c), and similarly for LCM, which extends cleanly to any number of inputs.

How does the Euclidean algorithm actually work?

Repeatedly divide the larger number by the smaller and replace the larger with the remainder, until the remainder is zero — the last non-zero remainder is the GCD. It converges in only a handful of steps even for very large numbers.

Is there a shortcut between GCD and LCM?

Yes — for two numbers, GCD × LCM = the product of the two numbers. Once you know the GCD, LCM = (a × b) ÷ GCD, which is faster than searching for common multiples directly.

What's the GCD of two numbers that share no common factor?

1 — numbers with a GCD of 1 are called "coprime" or "relatively prime," and their LCM is simply their product (since there's nothing to divide out).

Does the order I enter the numbers matter?

No — both GCD and LCM give the same result regardless of the order the numbers are listed in.