GCD / LCM Calculator

Using the GCD and LCM Calculator

1. Fill the First Number and Second Number inputs with any integers you want the GCD and LCM of. Negative signs and zero are both allowed; the tool normalises to absolute values before computing.
2. Press Calculate or hit Enter. The GCD and LCM appear side by side, along with the identity |a × b| = GCD(a, b) × LCM(a, b) filled in with your numbers so you can see the relationship.
3. Read the step log below the result. Every division in Euclid's algorithm is shown as a = bq + r, making the process inspectable for homework or teaching.
4. Re-run with different inputs as often as you want; nothing is stored between calculations.
5. Copy any line of the step log with a click, which is handy when pasting the derivation into a LaTeX document or chat message.

The Euclidean Algorithm in Code

The GCD routine implements Euclid's algorithm with the remainder variant: while the second operand is non-zero, replace (a, b) with (b, a mod b); the final value of a is the GCD. JavaScript's % operator returns a value with the sign of the dividend, so the absolute-value normalisation at the top of the function keeps the loop invariant clean. The LCM is then computed as |a * b| / gcd, with the division done before the multiplication where possible to avoid intermediate overflow, i.e. (a / gcd) * b.

Both routines run in the browser without any network call. The step log is built during the iteration by pushing each { a, b, q, r } tuple into an array, which is then rendered as a list. The overall cost is O(log min(a, b)) divisions, the worst case being a pair of consecutive Fibonacci numbers - a result proved by Gabriel Lamé in 1844 and considered the first complexity analysis in the history of the field.

Where GCD and LCM Show Up in Real Work

• Reducing a fraction to lowest terms by dividing numerator and denominator by their GCD.
• Finding a common denominator for fraction addition, which is just the LCM of the two denominators.
• Computing the period of two recurring events - a bus every 12 minutes and another every 18 minutes meet again every LCM(12, 18) = 36 minutes.
• Checking coprimality (GCD = 1) before applying the Chinese Remainder Theorem or choosing an RSA exponent.
• Reducing a gear ratio, a pulley ratio, or a music-theory interval to its canonical form.
• Working out how many tiles of size a by b fit into a larger rectangle without cutting - a GCD problem.

Boundary Cases

• GCD(a, 0) = |a| for any integer a, because every integer divides zero. The tool returns |a| cleanly rather than hitting an infinite loop.
• GCD(0, 0) is conventionally defined as 0, since no positive integer can be called "greatest". The tool follows this convention.
• LCM with a zero operand is 0, matching the convention that every non-zero number divides 0 so the "least common multiple" that is a multiple of 0 is just 0.
• Negative inputs are handled by taking absolute values up front. GCD and LCM are conventionally non-negative in the integers.
• Very large inputs up to Number.MAX_SAFE_INTEGER (2⁵³-1) work exactly. For larger magnitudes, switch to BigInt or a CAS.
• Coprime pairs produce GCD = 1 and LCM = |a * b|, which is the maximum possible LCM for a given product; this is a small but useful sanity check.

Background: Two Thousand Years of the Same Algorithm

Euclid stated the algorithm in Proposition VII.1 of the Elements (circa 300 BCE) using subtraction rather than the modulus operation: repeatedly replace the larger of (a, b) by the difference with the smaller until they are equal. The modulus-based variant used here is faster for operands of very different sizes but mathematically identical. Lamé's 1844 theorem bounds the number of iterations by five times the number of decimal digits of the smaller operand, which is why even ten-digit inputs need fewer than 50 steps. The extended Euclidean algorithm goes further and also returns integers x, y such that a·x + b·y = GCD(a, b); this Bézout coefficient form is what makes modular inverses and RSA key generation possible. This tool returns the GCD and LCM only, not the Bézout coefficients.

Alternatives and Tradeoffs

Python's math.gcd and math.lcm, JavaScript's own BigInt-based solutions, and command-line tools like bc or factor will all compute GCD and LCM faster for scripted use. For gigantic operands with hundreds of digits the binary GCD (Stein's algorithm) is worth knowing because it avoids divisions in favour of bit shifts and subtractions - historically useful on hardware with slow division. For symbolic or polynomial GCDs (useful in computer algebra) you want SymPy, Mathematica, or Maxima. The browser tool wins when you have two manageable integers and want the answer plus the derivation without opening a REPL. Show-your-work transcripts are its distinguishing feature.