Abstract

The greatest common divisor (GCD) of two integers is the largest integer that divides both. Euclid’s algorithm finds it by replacing the pair $(a,b)$ with $(b,a\mathrm{mod}b)$ until the remainder is 0. It is one of the oldest algorithms still in use (around 300 BC) and takes $O(\log \min (a,b))$ steps.

Cue

• What is Euclid’s step? → $\gcd (a,b)=\gcd (b,a\mathrm{mod}b)$, stopping at $\gcd (a,0)=a$
• What is its time complexity? → $O(\log \min (a,b))$, with Fibonacci numbers as the worst case
• How do you get the LCM from the GCD? → $\text{lcm}(a,b)=a/\gcd (a,b)\cdot b$, dividing first to avoid overflow
• What does the extended algorithm add? → $x,y$ with $ax+by=\gcd (a,b)$, which gives modular inverses

Why Euclid’s step works

Any number that divides both $a$ and $b$ also divides $a-qb$ for any $q$, and in particular $a\mathrm{mod}b$. The reverse holds too. So $(a,b)$ and $(b,a\mathrm{mod}b)$ have exactly the same common divisors, and therefore the same greatest one. The remainder strictly shrinks, so the process must reach 0, and $\gcd (a,0)=a$.

Worked example

$\gcd (48,18)$:

$a$	$b$	$a\mathrm{mod}b$
48	18	12
18	12	6
12	6	0
6	0	done, the GCD is 6

Implementation (Java)

static long gcd(long a, long b) {
    a = Math.abs(a);
    b = Math.abs(b);
    while (b != 0) {
        long r = a % b;
        a = b;
        b = r;
    }
    return a;
}
 
// Recursive form, the same algorithm
static long gcdRec(long a, long b) {
    return b == 0 ? Math.abs(a) : gcdRec(b, a % b);
}
 
static long lcm(long a, long b) {
    if (a == 0 || b == 0) return 0;
    return Math.abs(a / gcd(a, b) * b);   // divide first so a * b can't overflow
}

The JDK has this built in for big numbers: BigInteger.valueOf(48).gcd(BigInteger.valueOf(18)).

Edge cases:

• $\gcd (a,0)=|a|$, and $\gcd (0,0)$ is defined as 0.
• Math.abs(Long.MIN_VALUE) is still negative, so inputs at the very bottom of the range need BigInteger.

Complexity

The remainder at least halves every two steps, so Euclid needs $O(\log \min (a,b))$ iterations. The worst case is two consecutive Fibonacci numbers, where every quotient is 1 (Lamé’s theorem). For example, $\gcd (89,55)$ takes 9 steps.

Extended Euclidean algorithm

The same steps, run backwards, also give integers $x$ and $y$ with $ax+by=\gcd (a,b)$ (Bézout’s identity):

// Returns {g, x, y} with a*x + b*y == g
static long[] extGcd(long a, long b) {
    if (b == 0) return new long[] {a, 1, 0};
    long[] r = extGcd(b, a % b);
    return new long[] {r[0], r[2], r[1] - (a / b) * r[2]};
}

When $\gcd (a,m)=1$, the $x$ it returns is the modular inverse of $a$ mod $m$. That’s how you divide in modular arithmetic. Wrap it with Math.floorMod(x, m) to make it non-negative (see Algos, Modulo).

Where it shows up

• Simplifying fractions: divide the numerator and denominator by their GCD.
• LCM problems: when cycles line up again, for example “when do all the buses next arrive together?” in Advent of Code.
• Array rotation: the juggling algorithm rotates an array of length $n$ by $k$ using $\gcd (n,k)$ cycles.
• Coprimality: $\gcd (a,b)=1$ means $a$ and $b$ share no factors, which is needed for modular inverses and RSA.
• Water-jug puzzles: you can measure exactly $c$ litres with jugs of $a$ and $b$ litres iff $\gcd (a,b)$ divides $c$.

Related

• Algos, Modulo: each Euclid step is a modulo
• Algorithms, Categories: math / number theory

---