Number Theory Essentials

The problem

You are building a recipe scaler. Someone enters that they used 750 grams of flour and 1000 grams of water, and you want to show the ratio in its simplest form. Printing 750:1000 looks amateurish — you want 3:4. To simplify a fraction you divide the top and bottom by the largest number that divides both. So the whole task comes down to one question: what is the biggest number that divides both 750 and 1000?

That number has a name — the greatest common divisor — and it shows up everywhere: laying tiles evenly, syncing two blinking lights, cryptography, reducing fractions. Get a fast way to compute it and a surprising amount of downstream code becomes easy.

A first attempt

The obvious move is to try every candidate. Count down from the smaller number and return the first value that divides both.

def gcd_slow(a, b):
    for d in range(min(a, b), 0, -1):
        if a % d == 0 and b % d == 0:
            return d
    return 1

This works, but it walks one integer at a time. For two numbers near a billion it can do close to a billion checks — that is O(min(a, b)) time. Fine for tiny inputs, far too slow when the numbers get large. There has to be a shortcut.

The insight

Here is the trick the Greeks found. Any number that divides both a and b also divides their difference, and more usefully, their remainder. So

gcd(a, b) = gcd(b, a mod b)

Each step replaces the pair with a much smaller pair, and it stops the instant the remainder hits zero — at which point the other number is the answer. This is Euclid's algorithm, and it collapses that billion-step search into a couple dozen steps.

How it works

The code

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a // gcd(a, b) * b

print(gcd(1000, 750))  # 250
print(lcm(4, 6))       # 12

function gcd(a: number, b: number): number {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a: number, b: number): number {
  return (a / gcd(a, b)) * b;
}

console.log(gcd(1000, 750)); // 250
console.log(lcm(4, 6));      // 12

static int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

static long lcm(int a, int b) {
    return (long) a / gcd(a, b) * b;
}

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

long lcm(int a, int b) {
    return (long) a / gcd(a, b) * b;
}

int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

long long lcm(int a, int b) {
    return (long long) a / gcd(a, b) * b;
}

Complexity

Euclid runs in logarithmic time because each two steps at least halve the smaller number — the same reason binary search is fast.

When to use it

Practice

Recap

• The GCD is the largest number dividing two integers; trial division is O(min(a, b)).
• Euclid's gcd(a, b) = gcd(b, a mod b) runs in O(log) time and gives LCM for free.
• These small facts underpin fractions, cycles, and much of the rest of number theory.