GCD & LCM Calculator — Greatest Common Divisor & Least Common Multiple with Step-by-Step Euclidean Algorithm & Prime Factorization

01 · INSTRUMENT

Two answers, one machine

This gcd and lcm calculator answers before you finish typing — Euclid's divisions scroll out beneath the screen, prime factorizations assemble beneath them, and every claim is cross-checked before it reaches your eyes. No equals button; the proof is live.

SWS · NT-01 · EUCLID

FIRST

SECOND

THIRD · OPT

TWO INTEGERS MINIMUM · THIRD OPTIONAL · SPACES & COMMAS STRIPPED · EACH NUMBER ≤ 10¹²

TRY

THE WORK LIVE

FIELD NOTESNT-01

Euclid, c. 300 BC. The algorithm above is Proposition 2 of Book VII of the Elements — repeated division with remainder, running unchanged for 2,300 years.
The identity. gcd(a, b) × lcm(a, b) = a × b — two numbers only. For three, g × ℓ ≤ a·b·c, with equality exactly when the numbers are pairwise coprime.
Coprime shortcut. gcd = 1 means the lcm is the plain product: 8 × 9 = 72, no factoring needed.
Why it matters. GCD reduces fractions, LCM builds common denominators — and RSA cryptography finds its private keys with the extended Euclidean algorithm.
Exactness. An integer-and-BigInt core, no floating point until display. The 10¹² cap per number keeps factorization instant on every keystroke.

EXACT INTEGER CORE· EUCLID ON DISPLAY· BIGINT-SAFE PRODUCTS· NOTHING LEAVES THE PAGE

02 · MANUAL

How to use it

Sixty seconds from open to answer. The machine is deliberately plain — three boxes, three modes — but every panel underneath it is doing real mathematics, and nothing is hidden.

STEP 01 / MODE

Pick your mode

GCD hunts the greatest common divisor, LCM the least common multiple, and BOTH returns the two side by side — with the identity gcd × lcm = a × b checked on screen.

gcd | lcm | both

STEP 02 / INPUT

Enter your integers

Two numbers are required; the third box is optional and folds the result to a triple. Thousand-commas and stray spaces are stripped as you type, and the arithmetic stays exact end to end.

" 1,000,000 " → 1000000

STEP 03 / LIVE

Watch it solve live

There is no equals button. The screen re-solves on every keystroke, and the work panel beneath rewrites Euclid's algorithm line by line — every quotient, every remainder.

180 = 3 × 48 + 36

STEP 04 / READ

Read the rows

The big line is the answer. The rows beneath carry the prime factorization of each input, the shared primes behind the gcd, the highest powers behind the lcm, and a coprime verdict.

common → 2² · 3 = 12

STEP 05 / VERIFY

Trust, then verify

Nothing is asserted without a check: the lcm is recomputed through the formula a·b ÷ g as a second opinion, and BOTH mode multiplies out the identity in front of you.

12 × 720 = 8,640 ✓

STEP 06 / EXPLORE

Use the example chips

One tap loads a worked scenario — a textbook pair, a three-number fold, a coprime near-miss like 8 and 9, or a gear-style pair like 360 and 84.

tap → 48, 180 loads

gcd-lcm/ worked example — 48, 180 BOTH MODE

$ studywithstem gcd-lcm 48 180

├─ euclid · gcd(48, 180)BOOK VII

│ 180 = 3 × 48 + 36DIVIDE

│ 48 = 1 × 36 + 12DIVIDE

│ 36 = 3 × 12 + 0HALT

├─ gcd = 12RESULT

├─ factorsPRIMES

│ 48 = 2⁴ · 3—

│ 180 = 2² · 3² · 5—

├─ lcm = 2⁴ · 3² · 5 = 720RESULT

└─ 12 × 720 = 8,640 = 48 × 180VERIFIED ✓

exit 0 · exact arithmetic · nothing left the page

03 · QUESTIONS

Questions, answered

The nine questions every gcd–lcm hunt eventually arrives at — answered the way the tool works: exactly.

Q·01 How do I find the greatest common divisor (GCD)?

Divide the larger number by the smaller, replace the larger with the remainder, and repeat until the remainder is zero — the last non-zero value is the answer. For 48 and 180: 180 = 3×48 + 36, then 48 = 1×36 + 12, then 36 = 3×12 + 0, so gcd(48, 180) = 12. The same quantity is often called the highest common factor (HCF). The GCD tab writes every line of this as you type.

Q·02 How do I find the least common multiple (LCM)?

Two equivalent routes. Factor each number into primes and take the highest power of every prime that appears: 48 = 2⁴·3 and 180 = 2²·3²·5, so lcm = 2⁴·3²·5 = 720. Or use the formula lcm = a·b ÷ gcd = 8,640 ÷ 12 = 720. The tool shows both routes and cross-checks them.

Q·03 What is Euclid's algorithm, and why does it work?

It is Book VII of Euclid's Elements (c. 300 BC) — the oldest algorithm still in everyday use. It works because any common divisor of a and b also divides the remainder a − qb, so gcd(a, b) = gcd(b, a mod b); the pair keeps shrinking until the remainder hits zero. In the worst case it needs only about five times the number of digits of the smaller number (Lamé's theorem, via Fibonacci).

Q·04 What is the relationship between GCD and LCM?

For two positive integers, gcd(a, b) × lcm(a, b) = a × b — always: 12 × 720 = 8,640 = 48 × 180. For three or more numbers this becomes an inequality, g × ℓ ≤ a·b·c, with equality exactly when the numbers are pairwise coprime. The BOTH tab checks this in front of you.

Q·05 How do I compute the GCD or LCM of three numbers?

Fold the operation: gcd(a, b, c) = gcd(gcd(a, b), c), and likewise for the lcm. For 12, 18 and 24: gcd(12, 18) = 6 then gcd(6, 24) = 6; lcm(12, 18) = 36 then lcm(36, 24) = 72. The third box on the calculator is optional — leave it empty for two-number work.

Q·06 What does coprime (relatively prime) mean?

Two numbers are coprime when their GCD is 1 — they share no prime factor. 8 and 9 are coprime even though neither is prime. Coprime numbers have the pleasant property that their LCM is simply their product: lcm(8, 9) = 72.

Q·07 Where are GCD and LCM actually used?

Wherever fractions live: you divide by the GCD to reduce 180/48 to 15/4, and you build an LCM denominator to add 5/12 + 7/18 = 25/36. Beyond school: gear-tooth counts, when two repeating events coincide (buses, laps, calendars), polyrhythms in music, and RSA cryptography, whose private keys are found with the extended Euclidean algorithm.

Q·08 Can I use zero, negative numbers, or decimals?

Zero: gcd(a, 0) = a, because every integer divides 0, and lcm(a, 0) = 0; the calculator accepts zeros and states the rule on screen. Negatives: gcd is defined through absolute values, so enter magnitudes — this tool asks for non-negative integers. Decimals are not valid here; clear them by scaling — 1.5 and 2.25 become 150 and 225 by multiplying by 100, and the gcd scales by the same 100.

Q·09 Is it free, and does my input leave the page?

Completely free — no sign-up, no locked features. Every division, factorization and check runs locally in your browser; nothing is recorded or transmitted, and the page keeps working offline once it has loaded.

The GCD & LCM Calculator