Algorithms / Gcd Number Theory

Least You Need to Know: GCD, Euclid's Algorithm, and Divisibility Invariants

Greatest-common-divisor questions are really about what divisibility information survives after replacing one number by a remainder. Euclid's algorithm, linear combinations, and the gcd/lcm identity are the interview patterns that matter most.

The least you need to know

Euclid's algorithm uses `gcd(a, b) = gcd(b, a mod b)` until the remainder is zero.
The gcd of two integers is unchanged if you replace one number by its remainder modulo the other.
If `d = gcd(a, b)`, then `d` divides every integer combination `ax + by`.
For positive integers, `gcd(a, b) * lcm(a, b) = a * b`.
Extended Euclid explains why modular inverses come from linear combinations.

Key notation

gcd(a, b) largest positive integer dividing both `a` and `b`

lcm(a, b) least positive common multiple

a = bq + r division with remainder `0 <= r < b`

Tiny worked example

To compute `gcd(84, 30)`, replace the pair by `(30, 24)`, then `(24, 6)`, then `(6, 0)`.
The last nonzero remainder is `6`, so the gcd is `6`.
Because the gcd is preserved at each remainder step, Euclid's algorithm is both correct and fast.

Common mistakes

Students often remember the remainder steps but forget the invariant that proves them safe.
The gcd is about common divisors, not about the arithmetic difference between the numbers.
The identity with lcm uses positive values; sign conventions can distract from the main pattern.

How to recognize this kind of problem

The prompt asks for the largest step size, chunk size, or equal partition that fits both values.
A modular inverse, Diophantine equation, or coprimality check often points back to gcd structure.
The input sizes are large enough that repeated subtraction is the wrong model.