UIREADY.dev
GCD / LCMLoading saved progress…

GCD / LCM

The greatest common divisor (GCD) of two integers is the largest whole number that divides both of them with no remainder, and the least common multiple (LCM) is the smallest positive number that both of them divide into evenly. The GCD of 12 and 18 is 6; their LCM is 36. You will implement both, packaged on one object as gcdLcm = { gcd, lcm }, using Euclid's algorithm — a two-thousand-year-old method that finds the GCD by taking remainders. Each function is variadic: it accepts one or more numbers and folds the answer across all of them.

Signature

gcdLcm.gcd(...nums)   // one or more integers -> their greatest common divisor
gcdLcm.lcm(...nums)   // one or more integers -> their least common multiple

Once you have gcd, the LCM of two numbers follows from it: lcm(a, b) = |a * b| / gcd(a, b).

Examples

gcdLcm.gcd(12, 18);      // 6
gcdLcm.gcd(17, 5);       // 1   (coprime — no common factor but 1)
gcdLcm.gcd(-12, 18);     // 6   (uses absolute values)
gcdLcm.gcd(0, 5);        // 5   (gcd with 0 is the other number)
gcdLcm.gcd(12, 18, 24);  // 6   (reduced across all three)
gcdLcm.lcm(4, 6);        // 12
gcdLcm.lcm(3, 5);        // 15  (coprime — LCM is the product)
gcdLcm.lcm(0, 5);        // 0   (any 0 makes the LCM 0)
gcdLcm.lcm(2, 3, 4);     // 12  (reduced across all three)

Notes

  • Euclid's algorithm — gcd(a, b) = gcd(b, a % b), repeated until the second number is 0; the first number is then the answer. Use this rather than testing every candidate divisor.
  • Absolute values — the GCD and LCM are defined on magnitudes, so negative inputs are treated by their absolute value: gcd(-12, 18) is 6, and lcm(-4, 6) is 12.
  • Zero — gcd(0, x) is |x|, and gcd(0, 0) is 0. Any 0 passed to lcm makes the whole result 0.
  • Avoid overflow — compute the LCM as |a| / gcd * |b| (divide before you multiply), not |a * b| / gcd, so the intermediate product stays small.
  • Variadic — both functions take at least one argument and reduce across all of them; a single argument returns its own absolute value.
  • No libraries — implement the arithmetic yourself.

FAQ

Why use the modulo version of Euclid's algorithm instead of repeated subtraction?
Both find the same answer, but subtracting the smaller number from the larger one takes one step per multiple — gcd(1, 1000000) would subtract a million times. The modulo form gcd(a, b) = gcd(b, a % b) jumps straight to the remainder, so it finishes in a handful of steps even for huge inputs, and it never loops forever on a zero the way naive subtraction can.
Why compute the LCM as |a| / gcd * |b| rather than |a * b| / gcd?
They are mathematically equal, but a * b is formed first in the second version and can overflow past the safe-integer range for large inputs, corrupting the result. Dividing first — |a| / gcd is always a whole number because the gcd divides a — keeps every intermediate value small, so the final multiply stays accurate.
How do gcd and lcm extend from two numbers to a whole list?
Both are associative: gcd(a, b, c) equals gcd(gcd(a, b), c), and the same holds for lcm. So you fold the two-number version across the arguments with reduce — starting the gcd fold from 0 and the lcm fold from 1, which are the identity values that also make a single argument return its absolute value.
Loading editor…