GCD & LCM: Euclid's Algorithm Explained

The greatest common divisor (GCD) of two integers is the largest number that divides both with no remainder; the least common multiple (LCM) is the smallest positive number both divide into. Euclid’s algorithm computes the GCD in O(log(min(a, b))) steps — one of the oldest and most elegant algorithms in computing — and the LCM follows from it in one line.

The key insight behind Euclid’s algorithm

The GCD of a and b is the same as the GCD of b and a % b. Replacing the larger number with the remainder shrinks the problem fast, and when the remainder hits 0, the other number is the answer. Example: gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) = 6.

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a; // a is now the GCD
}

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a; // a is now the GCD
}

function gcd(a, b) {
  while (b !== 0) {
    const r = a % b;
    a = b;
    b = r;
  }
  return a; // a is now the GCD
}

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a  # a is now the GCD

The recursive form

The same logic reads beautifully as a one-line recursion. The base case is b == 0.

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

function gcd(a, b) {
  return b === 0 ? a : gcd(b, a % b);
}

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

For beginners: Always pass non-negative values (or take abs first). For negative inputs the remainder’s sign differs across languages, which can flip the GCD’s sign — gcd should always be non-negative.

LCM from GCD

You never compute the LCM directly. Use the identity a * b = gcd(a, b) * lcm(a, b), rearranged to lcm = a / gcd(a, b) * b. Divide before you multiply to avoid overflow on the intermediate product.

long long lcm(int a, int b) {
    return (long long)a / gcd(a, b) * b; // divide first, then multiply
}

long lcm(int a, int b) {
    return (long) a / gcd(a, b) * b; // divide first, then multiply
}

function lcm(a, b) {
  return (a / gcd(a, b)) * b; // divide first to limit growth
}

def lcm(a, b):
    return a // gcd(a, b) * b  # divide first, then multiply

Pitfall: Writing a * b / gcd(a, b) can overflow at a * b even when the final LCM fits. a / gcd * b keeps the intermediate value small. In C++/Java cast to a 64-bit type; in JS use BigInt for very large inputs; Python is safe either way but the divide-first habit is still good.

Complexity

The logarithmic bound comes from a classic result: the remainder at least halves every two steps.

Built-in shortcuts

Most languages ship a GCD so you rarely hand-roll it in production — but interviewers still expect you to know Euclid’s algorithm.

#include <numeric>
int g = std::gcd(48, 18);  // 6  (C++17)
int l = std::lcm(48, 18);  // 144 (C++17)

import java.math.BigInteger;
int g = BigInteger.valueOf(48).gcd(BigInteger.valueOf(18)).intValue(); // 6
// No built-in primitive LCM — derive from gcd as shown above.

// No built-in GCD in JavaScript — use the Euclid function above.
const g = gcd(48, 18); // 6

import math
g = math.gcd(48, 18)   # 6
l = math.lcm(48, 18)   # 144 (Python 3.9+)

When you’ll use it

Reducing fractions, finding when two repeating cycles re-align, simplifying ratios in grid/geometry problems, and as a building block for modular arithmetic. Next: prime numbers and the Sieve of Eratosthenes.