LCM GCD Calculator - Free Math Tool

LCM & GCD Calculator: How It Works

The greatest common divisor is the largest number dividing two values evenly; the lowest common multiple is the smallest number both divide into. They are opposite ends of the same relationship, and one formula connects them.

The connection

GCD(a, b) × LCM(a, b) = a × b

Find one and the other follows. For 12 and 18: GCD is 6, so LCM = (12 × 18) ÷ 6 = 36. This is the practical route, because finding the GCD is fast and finding the LCM directly is not.

Euclid's algorithm

Repeatedly replace the larger number with the remainder of dividing it by the smaller, until the remainder is zero. The last non-zero value is the GCD.

Step	Calculation	Remainder
1	48 ÷ 18	12
2	18 ÷ 12	6
3	12 ÷ 6	0 — stop

GCD(48, 18) = 6. Three steps, no factorisation. The algorithm is about 2,300 years old and is still what computers use, because its running time grows only logarithmically — even for numbers with hundreds of digits.

Prime factorisation as an alternative

12 = 2² × 3, and 18 = 2 × 3².

GCD takes the lowest power of each shared prime: 2¹ × 3¹ = 6.
LCM takes the highest power of every prime present: 2² × 3² = 36.

This method is more illuminating and much slower — factoring large numbers is computationally hard, which is exactly what cryptography relies on. Use it to understand, use Euclid to compute.

Where each is used

Task	Which
Simplifying a fraction	GCD — divide both parts by it
Adding fractions	LCM — of the denominators
Reducing an aspect ratio	GCD — 1920:1080 ÷ 120 = 16:9
Synchronising repeating events	LCM — buses every 12 and 18 minutes meet every 36
Cutting material without waste	GCD — largest identical piece from two lengths
Gear ratios and cycles	Both

Coprime numbers

When the GCD is 1, two numbers share no factors and are called coprime. Their LCM is simply their product. Coprimality matters well beyond arithmetic: RSA key generation depends on choosing an exponent coprime to a particular value, and gear designers deliberately use coprime tooth counts so that any given pair of teeth meets as rarely as possible, spreading wear evenly.

More than two numbers

Both extend by association: GCD(a, b, c) = GCD(GCD(a, b), c), and the same for LCM. Compute pairwise, left to right. For LCM, watch for overflow — the LCM of several moderately sized numbers grows fast, and the LCM of 1 through 20 already exceeds 232 million.

Frequently Asked Questions

What is the fastest way to find a GCD?

Euclid's algorithm — repeatedly replace the larger number with the remainder of dividing it by the smaller until the remainder is zero. It needs no factorisation and its running time grows only logarithmically.

How do I find the LCM once I have the GCD?

Divide the product of the two numbers by their GCD. For 12 and 18 with a GCD of 6, the LCM is (12 × 18) ÷ 6 = 36. This is far faster than searching for common multiples.

When do I need the LCM rather than the GCD?

The LCM for adding fractions with different denominators and for synchronising repeating cycles. The GCD for simplifying fractions, reducing ratios, and dividing quantities into the largest equal parts.

What does coprime mean?

Two numbers whose GCD is 1 — they share no common factor other than 1. Their LCM is simply their product. Coprimality is central to RSA key generation and to gear design, where it spreads wear evenly.

Can I use these with more than two numbers?

Yes. Both are associative, so compute pairwise: GCD(a, b, c) is GCD of GCD(a,b) with c. Watch for overflow when computing LCMs of several numbers, as the result grows very quickly.

Why is prime factorisation not used for large numbers?

Because factoring large numbers is computationally hard — the difficulty that public-key cryptography depends on. Euclid's algorithm sidesteps factorisation entirely and works efficiently even on numbers with hundreds of digits.