Divisibility, GCD & modular arithmetic

Euclid's algorithm, LCM, and arithmetic that stays inside a modulus. · 11 min read

GCD and Euclid's algorithm

The greatest common divisor gcd(a, b) is the largest integer dividing both. Euclid's algorithm uses one fact: every common divisor of a and b also divides a mod b. So gcd(a, b) = gcd(b, a mod b), shrinking the numbers until one hits 0.

Why Euclid is fast

gcd(a, b) = gcd(b, a mod b) — Common divisors are preserved by the remainder.
the remainder strictly shrinks — 0 ≤ a mod b < b.
it reaches gcd(x, 0) = x — Terminates in O(log min(a,b)) steps.

Result: O(log min(a, b))

long long gcd(long long a, long long b) {
    while (b) { a %= b; swap(a, b); }
    return a;
}
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;   // divide first to avoid overflow
}

Modular arithmetic

Many problems ask for an answer "modulo m" (often a large prime like 1e9 + 7) because exact values would be astronomically large. Addition and multiplication play nicely with the modulus:

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a · b) mod m = ((a mod m) · (b mod m)) mod m

Negative mod

In C++ and Java, (-7) % 3 is -1, not 2. When you need a non-negative residue, use ((x % m) + m) % m. Python's % already returns a non-negative result for positive m.

Practice: Greatest Common Divisor (Easy) — Euclid's algorithm: gcd(a, b) = gcd(b, a mod b).