The set of common divisors stays the same. Replacing the larger relation with its remainder preserves exactly the common divisors while shrinking values.

Euclid repeatedly folds a large number by the smaller one. The fold changes the numbers but not which integers divide both.

What the function promises: Return the nonnegative gcd of two integers. gcd(0,0) is defined as zero.

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return 0 if a == 0 or b == 0 else abs((a // gcd(a,b)) * b)

assert gcd(48,18) == 6
assert gcd(-12,8) == 4
assert lcm(6,8) == 24

Work and storage: O(log min(|a|,|b|)) remainder steps and O(1) space.

When to recognize it: Replacing the larger relation with its remainder preserves exactly the common divisors while shrinking values.

Check before applying it: lcm multiplication can overflow in fixed-width languages; handle signs and zero explicitly.

Fold the binary gcd across values; stop early if it reaches one.