GCD and LCM

GCD and LCM are the two workhorses of number-theory interview questions. The whole trick is Euclid's algorithm — a 2,300-year-old loop that finds the greatest common divisor in a handful of steps, no factoring required. Once you have the GCD, the LCM falls out of a one-line identity.

The slow way first

The obvious idea: factor both numbers. Find every divisor of 36 and every divisor of 60, then take the largest one they share. That works, but factoring is slow — trial division costs about O(sqrt(n)) per number, and for large inputs it is far more work than we need.

The question to ask: can I shrink the problem without factoring? Euclid's insight is yes — gcd(a, b) equals gcd(b, a mod b). Any common divisor of a and b also divides their remainder, so we can keep replacing the pair with a smaller one and the GCD never changes.

The idea: replace the pair until one hits zero

Loop on (a, b). Each round, replace it with (b, a mod b) — the second number becomes the remainder of dividing the first by the second. The numbers shrink fast. When b finally reaches 0, the surviving a is the GCD. Then the LCM is just a * b // gcd, using the original values.

The key insight: we never factor anything. Each mod strictly shrinks the second number, so the loop ends in O(log min(a, b)) steps — astonishingly fast.

Walk through it

Step through the animation. The two cells hold the running pair (a, b). Each step computes the remainder (shown underneath) and slides in the new pair (b, a mod b). Watch the numbers fall: (36, 60) -> (60, 36) -> (36, 24) -> (24, 12) -> (12, 0). When b hits 0, a is 12 — that is the GCD. The final step uses the original 36 and 60 to compute lcm = 36 * 60 // 12 = 180.

Pseudocode

function gcd(a, b):
    while b is not 0:
        a, b = b, a mod b      # shrink the pair; GCD is preserved
    return a                    # b is 0, so a is the answer
 
function lcm(a, b):
    return a * b // gcd(a, b)   # uses the ORIGINAL a and b

The Python solution

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    return a * b // gcd(a, b)

• gcd(a, b) runs the loop: while b is non-zero, replace the pair with (b, a % b).
• The tuple assignment a, b = b, a % b happens simultaneously — Python evaluates the right side first, so a % b uses the old a, not the new one.
• When b becomes 0, the loop exits and a holds the GCD.
• lcm(a, b) uses the identity a * b // gcd(a, b). We multiply first, then integer-divide by the GCD.
• Dividing by the GCD before the LCM can also avoid overflow in fixed-width languages: a // gcd(a, b) * b. Python integers are unbounded, so either order is fine here.

Complexity

Euclid uses constant extra space and finishes in a logarithmic number of steps. That is why every standard library implements GCD this way, and why LCM is always derived from it rather than computed directly.

When this pattern shows up

Practice