GCD and LCM Calculator with Step-by-Step Work
Find the greatest common divisor and least common multiple of two or more numbers, with the Euclidean algorithm steps shown for full transparency.
How this calculator finds GCD and LCM using an algorithm older than most numeral systems
The greatest common divisor and least common multiple sound like grade school topics, but the method this tool uses to find them, the Euclidean algorithm, was written down by Euclid around 300 BC and is still considered one of the oldest algorithms in continuous use today. It needs no factoring, no prime lists, and no guessing. It just repeatedly divides and keeps the remainder until nothing is left to divide.
The tool works entirely in your browser and uses JavaScript’s BigInt type for the arithmetic, which means it stays exact even for numbers far larger than JavaScript’s normal floating point limit would handle safely. Nothing you enter leaves your device.
The Euclidean algorithm, step by step
The tool shows this exact trace on screen when you enter two numbers, one line per division step, so you can follow the algorithm collapsing toward the answer instead of just reading a final number.
| Step | Division performed | Remainder |
|---|---|---|
| 1 | 180 ÷ 48 = 3 | 36 |
| 2 | 48 ÷ 36 = 1 | 12 |
| 3 | 36 ÷ 12 = 3 | 0 (stop) |
Extending to more than two numbers
GCD and LCM are technically pairwise operations, but the algorithm extends cleanly to a whole list. For three or more numbers, the tool folds the list left to right: GCD(a, b, c) is computed as GCD(GCD(a, b), c), and the same pattern applies to LCM. This works because GCD and LCM are both associative operations, the grouping does not change the final answer, only the order the calculation is written out in.
Exact BigInt arithmetic
Standard JavaScript numbers lose precision above 2 to the power 53. This tool uses BigInt throughout, so GCD and LCM stay exact even for numbers with a dozen or more digits.
Sign handling
Negative inputs are converted to their absolute value before the algorithm runs, since GCD and LCM are conventionally defined over positive integers regardless of the sign of the inputs.
- Euclidean algorithm covers the full history and proof of correctness, dating back to Euclid’s Elements.
- Least common multiple explains the relationship between LCM and GCD used in step 4 above.
- Wolfram MathWorld: Euclidean Algorithm has a more formal treatment with complexity analysis.
Problems these two solve
Reducing a fraction to lowest terms, finding a common denominator when adding fractions by hand, scheduling recurring events that need to align, like two machines that cycle every 18 and 24 minutes and you want to know when they next line up, splitting a design or grid layout into equal tiles without leftover space, and cryptography courses where the Euclidean algorithm is the starting point for the extended version used in RSA key generation. Any time two repeating cycles or two quantities need a common measure, GCD and LCM are the tools for the job.
FAQ: GCD and LCM Calculator
The GCD (greatest common divisor) is the largest number that divides evenly into all your numbers, useful for simplifying fractions, while the LCM (least common multiple) is the smallest number that all your numbers divide into evenly, useful for finding a common denominator or figuring out when repeating events align. They answer opposite kinds of questions: ‘what’s the biggest shared factor’ versus ‘what’s the smallest shared multiple.’
It repeatedly replaces the larger of two numbers with the remainder of dividing it by the smaller one, shrinking the pair each time, until the remainder reaches zero. The last non-zero remainder before hitting zero is the GCD, this works because any number that divides both original numbers must also divide their difference (and therefore their remainder), so the GCD is preserved at every step.
This identity holds because the product of two numbers can always be split into their shared factors (counted once, contributing to the GCD) and their remaining unique factors (which combine with the GCD to form the LCM). Rearranging the identity gives the formula this tool uses: LCM(a,b) = (a × b) ÷ GCD(a,b), which is far faster than listing out multiples until you find a match.
Apply the same two-number operation repeatedly: first find GCD(a, b), then find the GCD of that result with c, and so on down your list, the same logic applies to LCM. This works because both GCD and LCM are associative operations, meaning the order you combine numbers in doesn’t change the final answer.
Dividing both the numerator and denominator of a fraction by their GCD produces the simplest possible equivalent fraction, for example, 48/180 simplifies to 4/15 by dividing both by their GCD of 12. Any fraction can be fully simplified in exactly one division step once you know the GCD, rather than repeatedly dividing by small trial factors.
By convention, GCD and LCM are typically defined using the absolute (positive) values of the numbers involved, since divisibility and multiples work the same regardless of sign, this tool follows that convention and treats -12 the same as 12 for these calculations. Zero is excluded entirely, since every number divides into zero, making its GCD and LCM mathematically undefined in the usual sense.
From the blog
Number theory, lightly
Base systems, primes and the statistics people get wrong.
