Skip to content

GCD and LCM Calculator

3 integers

GCD
6
LCM
72

Parsed: 12, 18, 24

Estimates for educational purposes — not financial, medical, or legal advice. See terms.

Compute the greatest common divisor (GCD) and least common multiple (LCM) of any list of integers. Useful for simplifying fractions, finding common denominators, solving diophantine equations, and anywhere in mathematics where you need a shared factor or period.

GCD via the Euclidean algorithm

GCD is computed using the ancient Euclidean algorithm, which exploits the identity gcd(a, b) = gcd(b, a mod b). Starting from two numbers, you repeatedly replace the larger one with the remainder of dividing it by the smaller, until one of them hits zero. The other one is then the GCD. The algorithm terminates in O(log(min(a, b))) steps — fast enough to handle integers up to JavaScript’s Number.MAX_SAFE_INTEGER (about 9 × 10¹⁵) without breaking a sweat.

For lists of more than two integers, the tool reduces pairwise: gcd(a, b, c) = gcd(gcd(a, b), c). Order doesn’t matter because GCD is associative.

LCM from GCD

The tool computes LCM using the identity lcm(a, b) = |a × b| / gcd(a, b). Compute the GCD first, then divide the product of the two inputs by it. This is faster than computing LCM directly (which would require factoring), and uses GCD which you’re computing anyway. The tool divides before multiplying where possible to keep intermediate values smaller, which matters for large inputs approaching the safe-integer boundary.

Like GCD, LCM generalises to lists via pairwise reduction.

Example: simplifying a fraction

Simplifying 12/18 to its lowest terms: GCD(12, 18) = 6, so divide top and bottom by 6 → 12/6 = 2, 18/6 = 3, giving 2/3. Any fraction a/b simplified to lowest terms is a/gcd(a, b) over b/gcd(a, b). The fraction calculator does this simplification as part of any arithmetic operation on fractions.

Example: common denominator

Adding 1/4 + 1/6. Common denominator = LCM(4, 6) = 12. Rewrite: 3/12 + 2/12 = 5/12. The LCM gives you the smallest denominator where both fractions share the same base, which keeps the arithmetic clean and the result in lowest terms (or close to it).

Example: scheduling two events

Event A happens every 4 days, event B every 6 days. Both happen together every LCM(4, 6) = 12 days. If event C happens every 8, all three align every LCM(4, 6, 8) = 24 days. LCM is the standard tool for any “when does this cycle repeat?” question.

Example: coprime detection

Two integers are coprime (share no common factor other than 1) if and only if GCD = 1. GCD(14, 15) = 1 → coprime. GCD(14, 21) = 7 → not coprime. The tool doesn’t have a dedicated “coprime yes/no” output, but the GCD value itself answers the question.

Why not factorisation

A naive approach to GCD is to factor both numbers, find shared prime factors, and multiply. That works for small numbers but scales badly — factoring is computationally hard, which is literally what RSA encryption relies on. The Euclidean algorithm sidesteps factoring entirely and runs in logarithmic time regardless of whether the inputs are primes, composites, or giant numbers. For any serious GCD computation, Euclid beats factorisation hands down.

What this tool does not do

It doesn’t handle non-integers. Rationals and irrationals don’t have GCD or LCM in the usual sense; the tool rejects fractional and non-integer inputs with a parse error.

It doesn’t show the factorisation of your inputs. “What are the prime factors of 60?” is a different question — use the prime number checker which includes a factorisation mode. The tool just returns GCD and LCM.

It doesn’t support integers larger than 2⁵³. JavaScript numbers are double-precision floats with 53 bits of integer precision, so inputs beyond about 9 × 10¹⁵ lose precision. For arbitrary-precision GCD / LCM, you need a library that supports BigInt (like JavaScript’s built-in BigInt type, or a dedicated big-number package).

It doesn’t compute Bézout coefficients. For ax + by = gcd(a, b), the extended Euclidean algorithm finds x and y too — useful for modular inverses and Diophantine equations. The tool runs the basic Euclidean algorithm only.

It doesn’t display the step-by-step Euclidean algorithm. For pedagogical purposes showing “48 = 2×18 + 12, then 18 = 1×12 + 6, then 12 = 2×6 + 0” would be useful, but the tool just returns the final answer. For the walkthrough, a textbook or a dedicated step-by-step tool is the right resource.

Frequently asked questions

What's the difference between GCD and LCM?

GCD (greatest common divisor, also called highest common factor or HCF) is the largest integer that divides all your inputs exactly. For 12 and 18, GCD = 6, because 6 divides both 12 (twice) and 18 (three times), and there's no larger integer that does. LCM (least common multiple) is the smallest positive integer that all your inputs divide into exactly. For 4 and 6, LCM = 12, because 12 is a multiple of both 4 (three times) and 6 (twice), and there's no smaller positive integer that is. GCD shrinks down; LCM builds up.

Why is GCD(0, 0) = 0?

By convention. Strictly, every integer divides 0 (since 0 divided by anything is 0 with no remainder), so there's no 'greatest' common divisor of 0 and 0 in the usual sense. Some definitions return undefined or throw; others return 0 as a sensible sentinel. The tool uses the 0-return convention because it keeps the recursive formula gcd(a, 0) = |a| consistent and doesn't force callers to special-case the all-zeros input.

Why is LCM of anything with 0 equal to 0?

Because 0 is a multiple of every integer (n × 0 = 0 for any n), so 0 is always a common multiple — and it's the smallest non-negative one. Some conventions define LCM only over positive integers, in which case lcm(0, anything) is undefined. The tool returns 0 because it's the straightforward extension of the lcm(a, b) = |ab| / gcd(a, b) formula: when either input is 0, the formula gives 0 / something, which is 0.

How does the Euclidean algorithm work?

It's based on the fact that gcd(a, b) = gcd(b, a mod b) — the GCD doesn't change when you replace the larger number with the remainder of dividing it by the smaller. Keep replacing, and the numbers shrink until one hits zero; the other one is then the GCD. For gcd(48, 18): 48 mod 18 = 12, so gcd(48, 18) = gcd(18, 12). 18 mod 12 = 6, so = gcd(12, 6). 12 mod 6 = 0, so = gcd(6, 0) = 6. Terminates in O(log(min(a, b))) steps, which is fast enough for enormous inputs.

Can I give it more than two numbers?

Yes. GCD and LCM both generalise to any list of integers via pairwise reduction. For three numbers, gcd(a, b, c) = gcd(gcd(a, b), c); the order doesn't matter because both operations are associative. The tool accepts comma, space, or semicolon-separated integers in any quantity. For four integers, the result is the GCD / LCM across all four simultaneously.