GCD & LCM Calculator

What This Calculator Really Does

The greatest common divisor (GCD) is the largest number that divides two integers exactly; the least common multiple (LCM) is the smallest number they both divide into. This calculator runs the Euclidean algorithm for the GCD — showing each remainder step — and applies the identity GCD × LCM = a × b for the LCM.

The Euclidean algorithm is one of the oldest efficient procedures in mathematics, and it is still the right one: instead of factoring, it replaces the pair (a, b) with (b, a mod b) until the remainder hits zero. Three or four steps solve numbers whose prime factorization would take a page.

Everything runs locally in your browser: no numbers stored, nothing tracked, offline after the first visit.

The Method, Explained Plainly

Euclidean algorithm: repeatedly replace (a, b) with (b, a mod b) until b = 0; the last nonzero a is the GCD.

LCM identity: LCM(a, b) = (a × b) ÷ GCD(a, b)

• Why it works — every common divisor of a and b also divides a mod b, so the GCD is preserved by each replacement step.
• Why the identity holds — a × b counts the shared prime factors (GCD) twice and the unshared ones once; dividing by GCD leaves exactly the LCM.

For more than two numbers, fold pairwise: gcd(gcd(a, b), c), lcm(lcm(a, b), c).

How to Use It — In Order

1. Enter two positive integers — order does not matter; the algorithm is symmetric in effect.
2. Read the GCD — with the full remainder chain shown for verification.
3. Read the LCM — computed via the identity, no factoring needed.
4. Add more numbers — for several, the tool folds pairwise; check the running GCD only shrinks and the LCM only grows.
5. Use it on fractions — GCD reduces a fraction to lowest terms; LCM is the common denominator for adding them.
6. Sanity-check — the GCD must divide both inputs exactly; a quick division confirms it.

Worked Example, Verified by Hand

GCD(48, 180) by the Euclidean algorithm:

1. 180 mod 48 = 36 (48 × 3 = 144, remainder 36).
2. 48 mod 36 = 12.
3. 36 mod 12 = 0 → stop. Last nonzero value: GCD = 12.
4. LCM = 48 × 180 ÷ 12 = 8,640 ÷ 12 = 720.

Checks: 12 divides both (48 ÷ 12 = 4; 180 ÷ 12 = 15) ✓. 720 is a multiple of both (720 ÷ 48 = 15; 720 ÷ 180 = 4) ✓. Fraction reduction in action: 48/180 = 4/15 after dividing by the GCD.

Common Mistakes to Avoid

• Factoring instead of using the algorithm — the Euclidean method is faster and never needs prime factorizations.
• Stopping one step early — the GCD is the last nonzero remainder, not the zero one.
• Applying LCM = a × b without dividing by the GCD — that product is a common multiple, rarely the least one.
• Non-integers or negatives — GCD/LCM are defined for positive integers; reduce fractions first, take absolute values for signs.
• Pairwise folding mistakes on three-plus numbers — gcd(gcd(a,b),c) is the order; batching all at once is not the algorithm.

Limitations

• Positive integers only — fractions, decimals and polynomials need adapted algorithms.
• JavaScript precision caps inputs near 2⁵³; beyond that, use big-integer tooling.
• Does not output the prime factorization — the prime-factorization tool covers that view.

Expected Accuracy

Integer-exact arithmetic — modulo and multiplication carry no rounding. Results are exact up to the precision limit of the platform's integers.

Privacy — Your Data Never Leaves This Device

Everything is computed locally: no inputs stored or sent, no tracking — the tool works offline too.

Related Tools & Guides

Natural next steps from GCD & LCM:

• All Utilities Calculators
• Ratio Simplifier — GCD applied to ratios
• Fraction Calculator — GCD reduces, LCM adds
• Prime Factorization — the alternative route to both
• Percentage Calculator

Sources & Standards

The Euclidean algorithm appears in Euclid's Elements (Book VII) and is unchanged in modern number theory.

• Wolfram MathWorld — Euclidean Algorithm (reference)

Bottom Line

Remainders down to zero give the GCD; one multiplication and division gives the LCM. Two thousand years old and still the fastest way.

Frequently Asked Questions