DSA Number Theory

Euclidean Algorithm

You need the largest square tile that tiles a 48×18 floor with no cuts. That size is . Second person: you already know trial division works; the remainder loop finishes in tiny steps.

The engine is the . The also builds Bézout coefficients for inverses.

Algorithm journey

Input a, b ≥ 0

Swap so a ≥ b if you like.

Replace (a,b)←(b,a mod b)

Remainders strictly drop.

Stop at remainder 0

gcd is the other number.

Optional: back-sub x,y

xa+yb = gcd.

What actually happens

Naive idea: trial-divide down from min(a,b). Correct, but Θ(min(a,b)) checks hurt for big integers.

Better idea: each modulo shrinks the problem. Fibonacci worst cases still take O(log min(a,b)) divisions.

The improved design still fails if you forget non-negativity / sign conventions, or need gcd of many numbers without reducing pairwise carefully with zeros.

Invariant

Throughout the loop, gcd of the current pair equals gcd of the original pair. When the remainder hits 0, the nonzero partner is that gcd.

How to choose Euclidean tools

1. Only gcd? Binary/Euclidean built-ins are fine.

2. Modular inverse? Extended Euclid when modulus is not prime, or pow(a,m-2) when m is prime.

3. Many integers? Fold gcd left-to-right; gcd with 0 is the other value.

Quantitative check

gcd(48,18): 48=2·18+12; 18=1·12+6; 12=2·6+0 → 6. Worst-case neighbor Fibonacci inputs maximize steps; still logarithmic in the magnitude.

Euclidean Algorithm Visualizer

Number A

Number B

Step 1 of 0

🔑 The Core Principle

Key Insight

GCD(a, b) = GCD(b, a mod b)

The GCD of two numbers is the same as the GCD of the smaller number and the remainder when dividing the larger by the smaller. Keep applying this until the remainder is 0 - the last non-zero remainder is the GCD!

Example: GCD(48, 18)

GCD(48, 18) = GCD(18, 48 mod 18) = GCD(18, 12)

GCD(18, 12) = GCD(12, 18 mod 12) = GCD(12, 6)

GCD(12, 6) = GCD(6, 12 mod 6) = GCD(6, 0)

GCD(6, 0) = 6 ✓

Why the remainder preserves the GCD

Write a = qb + r, where r = a mod b. If d divides both a and b, then d divides a − qb = r. Conversely, if d divides b and r, then d divides qb + r = a. The pairs (a, b) and (b, r) therefore have exactly the same common divisors, proving gcd(a, b) = gcd(b, r) rather than only one direction of the claim.

Invariant

The set of common divisors never changes.

Progress

For b ≠ 0, 0 ≤ r < |b| after normalization.

Termination

A strictly decreasing nonnegative integer cannot decrease forever.

🔍 Did You Know? 2,300 Years Old!

The Euclidean Algorithm appears in Euclid's Elements (circa 300 BCE), making it one of the oldest algorithms still in common use! It predates modern computers by over 2,000 years. Euclid described it geometrically (subtracting lengths of line segments), but the principle is identical to our modern remainder-based version. It's a testament to timeless mathematical elegance!

📝 How It Works

Start with Two Numbers

Normalize two integers to nonnegative magnitudes. No initial ordering is required; the first remainder step handles it.

Divide and Take Remainder

Compute r = a mod b (remainder when a is divided by b).

Check if Remainder is Zero

If r = 0, then b is the GCD. Stop and return b.

Repeat with Smaller Numbers

If r ≠ 0, replace a with b and b with r. Go back to step 2. The numbers get smaller each iteration!

🎯 Key Insight: Why It Works

The algorithm works because of this mathematical property:

Any common divisor of a and b also divides (a mod b)

Proof sketch: If d divides both a and b, then a = d×k and b = d×m for some integers k, m. When we compute a mod b, we get a - q×b = d×k - q×d×m = d×(k - q×m), which is also divisible by d! So GCD(a, b) = GCD(b, a mod b). The numbers shrink until we hit 0, revealing the GCD.

💻 Implementation

Recursive Version (Elegant)

Python

python

def gcd_recursive(a: int, b: int) -> int:
    """Return a nonnegative gcd; by convention gcd(0, 0) == 0."""
    a, b = abs(a), abs(b)

    def visit(x: int, y: int) -> int:
        return x if y == 0 else visit(y, x % y)

    return visit(a, b)


if __name__ == "__main__":
    assert gcd_recursive(48, 18) == 6
    assert gcd_recursive(-48, 18) == 6
    assert gcd_recursive(0, 7) == 7
    assert gcd_recursive(0, 0) == 0
    print(gcd_recursive(123_456_789, 987_654_321))  # 9

Java

java

public class EuclideanRecursive {
    // Contract: nonnegative result, gcd(0, 0) = 0.
    // Long.MIN_VALUE is rejected because its magnitude is not a signed long.
    public static long gcdRecursive(long a, long b) {
        return visit(magnitude(a), magnitude(b));
    }

    private static long visit(long a, long b) {
        return b == 0L ? a : visit(b, a % b);
    }

    private static long magnitude(long value) {
        if (value == Long.MIN_VALUE) {
            throw new ArithmeticException("magnitude does not fit in long");
        }
        return Math.abs(value);
    }

    public static void main(String[] args) {
        assert gcdRecursive(48, 18) == 6;
        assert gcdRecursive(-48, 18) == 6;
        assert gcdRecursive(0, 7) == 7;
        assert gcdRecursive(0, 0) == 0;
        System.out.println(gcdRecursive(123_456_789L, 987_654_321L));
    }
}

Iterative Version (No Recursion)

Python

python

def gcd_iterative(a: int, b: int) -> int:
    """Remainder-based Euclid in O(1) auxiliary space."""
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a


def binary_gcd(a: int, b: int) -> int:
    """Stein's algorithm: shifts, subtraction, and comparisons only."""
    a, b = abs(a), abs(b)
    if a == 0:
        return b
    if b == 0:
        return a

    def trailing_zeros(value: int) -> int:
        return (value & -value).bit_length() - 1

    common_twos = min(trailing_zeros(a), trailing_zeros(b))
    a >>= trailing_zeros(a)
    while b:
        b >>= trailing_zeros(b)
        if a > b:
            a, b = b, a
        b -= a
    return a << common_twos


def euclid_trace(a: int, b: int) -> list[tuple[int, int, int]]:
    a, b = abs(a), abs(b)
    steps = []
    while b:
        remainder = a % b
        steps.append((a, b, remainder))
        a, b = b, remainder
    return steps


if __name__ == "__main__":
    assert gcd_iterative(-48, 18) == binary_gcd(-48, 18) == 6
    for left, right, remainder in euclid_trace(48, 18):
        print(f"{left} mod {right} = {remainder}")

Java

java

public class EuclideanIterative {
    public static long gcdIterative(long a, long b) {
        a = magnitude(a);
        b = magnitude(b);
        while (b != 0L) {
            long remainder = a % b;
            a = b;
            b = remainder;
        }
        return a;
    }

    public static long binaryGcd(long a, long b) {
        a = magnitude(a);
        b = magnitude(b);
        if (a == 0L) return b;
        if (b == 0L) return a;

        int commonTwos = Math.min(
                Long.numberOfTrailingZeros(a), Long.numberOfTrailingZeros(b));
        a >>= Long.numberOfTrailingZeros(a);
        while (b != 0L) {
            b >>= Long.numberOfTrailingZeros(b);
            if (a > b) {
                long temporary = a;
                a = b;
                b = temporary;
            }
            b -= a;
        }
        return a << commonTwos;
    }

    public static void printTrace(long a, long b) {
        a = magnitude(a);
        b = magnitude(b);
        while (b != 0L) {
            long remainder = a % b;
            System.out.println(a + " mod " + b + " = " + remainder);
            a = b;
            b = remainder;
        }
    }

    private static long magnitude(long value) {
        if (value == Long.MIN_VALUE) {
            throw new ArithmeticException("magnitude does not fit in long");
        }
        return Math.abs(value);
    }

    public static void main(String[] args) {
        assert gcdIterative(-48, 18) == 6;
        assert binaryGcd(-48, 18) == 6;
        printTrace(48, 18);
    }
}

Extended Euclidean Algorithm

Python

python

def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
    """Return (g, x, y) with g >= 0 and a*x + b*y == g."""
    old_r, r = abs(a), abs(b)
    old_x, x = 1, 0
    old_y, y = 0, 1

    while r:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_x, x = x, old_x - quotient * x
        old_y, y = y, old_y - quotient * y

    if a < 0:
        old_x = -old_x
    if b < 0:
        old_y = -old_y
    return old_r, old_x, old_y


def mod_inverse(value: int, modulus: int) -> int:
    if modulus <= 1:
        raise ValueError("modulus must be greater than one")
    gcd, coefficient, _ = extended_gcd(value % modulus, modulus)
    if gcd != 1:
        raise ValueError("inverse does not exist")
    return coefficient % modulus


if __name__ == "__main__":
    g, x, y = extended_gcd(-48, 18)
    assert g == 6 and (-48) * x + 18 * y == g
    assert mod_inverse(3, 7) == 5
    print(g, x, y)

Java

java

import java.math.BigInteger;

public class ExtendedEuclidean {
    static final class Result {
        final BigInteger gcd;
        final BigInteger x;
        final BigInteger y;

        Result(BigInteger gcd, BigInteger x, BigInteger y) {
            this.gcd = gcd;
            this.x = x;
            this.y = y;
        }
    }

    public static Result extendedGcd(BigInteger a, BigInteger b) {
        BigInteger oldR = a.abs(), r = b.abs();
        BigInteger oldX = BigInteger.ONE, x = BigInteger.ZERO;
        BigInteger oldY = BigInteger.ZERO, y = BigInteger.ONE;

        while (!r.equals(BigInteger.ZERO)) {
            BigInteger quotient = oldR.divide(r);

            BigInteger nextR = oldR.subtract(quotient.multiply(r));
            oldR = r;
            r = nextR;

            BigInteger nextX = oldX.subtract(quotient.multiply(x));
            oldX = x;
            x = nextX;

            BigInteger nextY = oldY.subtract(quotient.multiply(y));
            oldY = y;
            y = nextY;
        }

        if (a.signum() < 0) oldX = oldX.negate();
        if (b.signum() < 0) oldY = oldY.negate();
        return new Result(oldR, oldX, oldY);
    }

    public static BigInteger modInverse(BigInteger value, BigInteger modulus) {
        if (modulus.compareTo(BigInteger.ONE) <= 0) {
            throw new IllegalArgumentException("modulus must be greater than one");
        }
        Result result = extendedGcd(value.mod(modulus), modulus);
        if (!result.gcd.equals(BigInteger.ONE)) {
            throw new ArithmeticException("inverse does not exist");
        }
        return result.x.mod(modulus);
    }

    public static void main(String[] args) {
        BigInteger a = BigInteger.valueOf(-48);
        BigInteger b = BigInteger.valueOf(18);
        Result result = extendedGcd(a, b);
        assert a.multiply(result.x).add(b.multiply(result.y)).equals(result.gcd);
        assert modInverse(BigInteger.valueOf(3), BigInteger.valueOf(7))
                .equals(BigInteger.valueOf(5));
        System.out.println(result.gcd + " " + result.x + " " + result.y);
    }
}

Contracts and algorithm variants

Case / variant	Contract and use
Zero	gcd(a, 0) = \|a\|; this page adopts the common programming convention gcd(0, 0) = 0.
Negative inputs	Normalize magnitudes and return a nonnegative gcd. Bézout coefficient signs must be mapped back to the original inputs.
Fixed-width Java	\|Long.MIN_VALUE\| is not representable as long. The long GCD examples reject it; the extended example uses BigInteger.
Binary GCD (Stein)	Removes common powers of two and uses shifts/subtraction. Useful where division is costly; asymptotic bit complexity needs a machine model.
Extended Euclid	Maintains r = a·x + b·y and returns Bézout coefficients. An inverse modulo m exists exactly when gcd(a, m) = 1.

⚡ Complexity Analysis

Time Complexity

✓
O(1 + log(1 + min(|a|, |b|)))
Every two remainder steps at least halve the larger positive operand
✓
Fibonacci inputs are worst-shaped
Consecutive Fibonacci numbers maximize the number of divisions; Lamé's theorem gives a linear bound in decimal digits

Space Complexity

✓
O(1) - Iterative
Constant space with loop
•
O(1 + log(1 + min(|a|, |b|))) - Recursive
Call stack depth

💡 Pro Tip: LCM from GCD

Once you have GCD, you can easily find LCM (Least Common Multiple):

LCM(a, b) = |(a / GCD(a, b)) × b|, with LCM(0, b) = 0

Python

python

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


def lcm(a: int, b: int) -> int:
    """Python integers grow as needed; divide first to limit intermediates."""
    if a == 0 or b == 0:
        return 0
    return abs((a // gcd(a, b)) * b)


if __name__ == "__main__":
    assert lcm(12, 18) == 36
    assert lcm(-15, 25) == 75
    assert lcm(0, 25) == 0

Java

java

public class LCM {
    public static long gcd(long a, long b) {
        a = magnitude(a);
        b = magnitude(b);
        while (b != 0L) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static long lcm(long a, long b) {
        if (a == 0L || b == 0L) return 0L;
        long product = Math.multiplyExact(a / gcd(a, b), b);
        if (product == Long.MIN_VALUE) {
            throw new ArithmeticException("LCM does not fit in signed long");
        }
        return Math.abs(product);
    }

    private static long magnitude(long value) {
        if (value == Long.MIN_VALUE) {
            throw new ArithmeticException("magnitude does not fit in long");
        }
        return Math.abs(value);
    }

    public static void main(String[] args) {
        assert lcm(12, 18) == 36;
        assert lcm(-15, 25) == 75;
        assert lcm(0, 25) == 0;
        System.out.println(lcm(12, 18));
    }
}

Why divide first? The identity is GCD × LCM = |a × b|, but evaluating a×b first can overflow a fixed-width integer even when the final LCM fits. Java's Math.multiplyExact makes overflow explicit.

✅ Pros & ❌ Cons

✅ Advantages

✓Logarithmic number of remainder steps
✓Simple to implement (just a few lines)
✓Works with arbitrary-precision integer types such as Python int and Java BigInteger
✓Has a precise, testable zero and sign contract
✓Extended version enables cryptography

❌ Disadvantages

✗Only works for integers (not real numbers)
✗Fixed-width magnitude, coefficient, and LCM arithmetic can overflow without guards
✗Big-integer division cost depends on operand bit length, not a unit-cost arithmetic model

💼 Real World Applications

🔐 Cryptography (RSA)

Extended Euclid computes inverses used in RSA key mathematics, the Chinese Remainder Theorem, and many modular protocols. A modern TLS connection may use other public-key systems, so this is a primitive, not the whole protocol.

Example: SSL/TLS certificates, secure messaging

🎵 Music Theory

Integer frequency ratios can be reduced with GCD: 440:660 becomes 2:3. Actual tuning and perception involve real-valued measurements and temperament, so the integer model must be stated.

Example: Tuning systems, chord analysis

📐 Computer Graphics

GCD reduces aspect ratios and lattice direction vectors, for example, displacement (12, 18) has primitive direction (2, 3). Line rasterizers need not literally call GCD, but discrete-geometry normalization often does.

Example: Image resizing, vector graphics

⏰ Scheduling

Finding when periodic events align uses GCD/LCM. If bus A comes every 12 minutes and bus B every 18 minutes, they align every LCM(12,18) = 36 minutes.

Example: Traffic lights, task scheduling

Short takeaway

Euclid’s algorithm computes gcd via the remainder property gcd(a,b)=gcd(b,a mod b). Extended Euclid returns Bézout coefficients for inverses and linear Diophantine equations.

Exercises

Trace gcd(1071, 462) step by step. How many divisions?
Why does every common divisor of a and b also divide a mod b?
Find x,y with 17x + 13y = 1 using extended Euclid (modular inverse of 17 mod 13).

Primary sources

Euclid, Elements, Book VII: the classical gcd algorithm.
Cormen et al., CLRS: Euclidean and extended Euclidean algorithms.
Knuth, TAOCP Vol. 2: seminumerical algorithms (gcd analysis).