A ticket assigns two batch sizes, 54 and 24, and asks for the largest pack that divides both. The intern subtracts the smaller from the larger until they match. That is Euclid. It is also slow when the numbers are far apart: 10^9 and 1 subtract a billion times. The remainder is the same algorithm with the inner loop collapsed.

gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = |a|. Extended Euclid also returns x, y with a x + b y = gcd. That identity is the modular inverse when the gcd is 1.

This post is remainder, then coefficients. Modular exponentiation is Binary Exponentiation. Catalog: Algorithms Roadmap. It is not a crypto lecture, not BigInteger.gcd internals, and not a reason to re-teach % in Java.

Subtract, then replace with mod

Euclid’s original picture: replace the larger by larger - smaller until one side is 0. Every common divisor of a and b still divides the pair after a subtraction, so the gcd is invariant. Remainder is repeated subtraction in one step: a = q b + r with 0 ≤ r < b, so gcd(a, b) = gcd(b, r).

static int gcd(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

gcd(54, 24): 54 = 2·24 + 6, 24 = 4·6 + 0, answer 6. gcd(0, 0) is conventionally 0 in this loop (a stays 0). Specs that forbid it should throw.

lcm(a, b) = |a / gcd · b| — divide before multiplying to cut overflow. Use long when the product may not fit in int.

Note: Java % follows the dividend’s sign. Taking abs first keeps the remainder non-negative for this loop. Math.floorMod is the other way to a non-negative remainder; pick one and stay consistent.

BigInteger.gcd is the JDK call for arbitrary size. This loop is what that call is on two ints.

Extended Euclid: Bézout

There exist integers x, y with a x + b y = gcd(a, b). Unwind the remainders:

6 = 54 - 2·24
(stop — gcd is 6)

In code, keep coefficients as you go:

record Egcd(int g, int x, int y) {}

static Egcd egcd(int a, int b) {
    if (b == 0) {
        return new Egcd(a, 1, 0);
    }
    Egcd r = egcd(b, a % b);
    // r.g = b * r.x + (a % b) * r.y
    // a % b = a - (a/b)*b
    return new Egcd(r.g, r.y, r.x - (a / b) * r.y);
}

Signs: this version matches Java / and % on non-negative a, b. Call egcd(Math.abs(a), Math.abs(b)) then flip x/y if you took abs.

Modular inverse of a modulo m: egcd(a, m) with g == 1, then x mod m. If g != 1, there is no inverse. BigInteger.modInverse is the JDK call; it throws if not invertible.

When not to use this loop

  • You already have BigInteger. Call gcd / modInverse. Do not paste extended Euclid into a money service.
  • You needed a prime factor. GCD is not factorization.
  • Floating point. 0.1 and 0.2 are not Euclid’s domain. Scale to integers.

Cheat sheet

Job:       largest positive integer dividing both; Bézout; inverse when g=1
Invariant: gcd(a,b) = gcd(b, a mod b); gcd(a,0)=|a|
LCM:       |a/gcd * b|  (divide first)
Inverse:   egcd(a,m).g==1 then x mod m
JDK:       BigInteger.gcd / modInverse; int loop when both fit
Not this:  factoring, floats, crypto primitives

Do:

  • Use remainder, not a billion subtractions.
  • Divide by gcd before multiplying for lcm.
  • Check g == 1 before calling a number an inverse.

Don’t:

  • Ignore Java’s signed remainder and then wonder why gcd went negative.
  • Treat gcd(0,0) as 1 without a spec.
  • Hand-roll BigInteger gcd in application code.

Wrap-up

Euclid is the remainder recurrence: replace (a, b) with (b, a mod b) until b is 0. Extended Euclid back-substitutes the same steps into a x + b y = g. Inverse exists only when g = 1.

The next numeric procedure is power by squaring: pow(base, exp) in logarithmic multiplies, not a loop of exp products.

Next optional step in the series Modular or integer power in log multiplies. Binary Exponentiation: pow(base, exp) in Logarithmic Multiplies