Euclidean algorithm

The Euclidean algorithm computes the greatest common divisor of two integers in a handful of divisions, and it is about two thousand three hundred years old. What is worth noticing about the problems below is that hardly any of them wanted a common divisor. The gcd appears as a coprimality test, as a normaliser, as a way to build the lcm, and occasionally as a count in its own right — four different jobs, one three-line loop.

The algorithm

Replace $(a, b)$ with $(b,\ a \bmod b)$ until the second term is zero; the first term is then the gcd.

while b:
    a, b = b, a % b

It terminates because the remainder strictly decreases, and it is correct because any divisor of $a$ and $b$ also divides $a - qb$, so the pair's set of common divisors is unchanged by the step. The speed is the surprising part: by Lamé's theorem the number of steps is $O(\log \min(a, b))$, and the worst case is exactly a pair of consecutive Fibonacci numbers — the inputs on which every quotient is 1 and the remainder shrinks as slowly as it possibly can. Even then, gcd(a, b) for 64-bit inputs is bounded by about ninety iterations. It is, for practical purposes, free.

The subtractive form Euclid actually wrote — repeatedly subtract the smaller from the larger — is the same algorithm with the division unrolled, and it is $O(a/b)$ in the bad case rather than $O(\log b)$. gcd(10**9, 1) is one modulo or a billion subtractions. Use the remainder.

Python has it built in as math.gcd, which since 3.9 is variadic and returns a non-negative result, plus math.lcm alongside it. C has neither, so every C solution here carries the same five-line helper near the top of the file:

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

When a Python solution in this stack is one expression and its C sibling opens with that function, this is the whole of the difference. The one variation is width: problem 257 takes the gcd of a product, $p(p-q)$, so its copy of the helper is the same loop over long long. Choosing the operand type to match the largest thing you will ever pass in is the only design decision the helper has.

The step's invariant, $\gcd(a, b) = \gcd(a, b - qa)$, is also worth keeping as an algebraic tool, separate from the loop. Problem 257's analysis leans on it: with $r = kq - p$ it rewrites $\gcd(p, r) = \gcd(p, k)$ and $\gcd(p - q, r) = \gcd(p - q, k - 1)$ — one Euclidean step each, done on paper — which shows that the gcd it divides by never exceeds $k(k-1)$. That bound is what caps the enumeration at $q = O(\sqrt{N})$. The runtime gcd computes a value; the same identity applied by hand proves how large that value can get.

The four jobs

A coprimality predicate. This is by far the most common use, and it usually appears inside a parametrisation. Euclid's formula generates every primitive Pythagorean triple exactly once from a pair $m > n > 0$ that is coprime and of opposite parity, so the enumeration is a double loop with a gcd guard at its centre — problem 75 writes it plainly:

for m in range(2, int((max_perimeter / 2) ** 0.5)):
    for n in range(m % 2 + 1, m, 2):
        if math.gcd(m, n) != 1:
            continue

Problems 39 and 139 use the same generator, and problems 141, 195 and 420 each enumerate over a coprime pair $(p, q)$ that parametrises their own family. The shared idea is that the gcd condition is what makes the parametrisation a bijection: drop it and you generate every triple once for each of its scalings, and the count is wrong in a way that is very hard to see. A second flavour of the same job is coprimality to a fixed modulus — problems 26 and 129 both filter on $\gcd(n, 10) = 1$, because the decimal expansion of $1/n$ only becomes purely periodic once $n$ shares no factor with the base.

A normaliser. Dividing both parts of something by their gcd puts it in canonical form: a fraction in lowest terms, a direction vector reduced to its primitive step, a ratio reduced to its representative. Problem 175 divides a numerator and denominator by their gcd for exactly this reason. Python's fractions.Fraction does it for you on every operation — which is why problems 33 and 71 use the gcd without ever naming it, and why their final answers can be read straight off .numerator or .denominator with no reduction step of their own.

The same reduction answers a question that turns up whenever a parametrisation contains a division: for which $s$ is $ms/r$ an integer? Exactly when $s$ is a multiple of $r / \gcd(m, r)$, which is the denominator of $m/r$ in lowest terms. Problem 257 parametrises its triangles so that one side is $c = p(p-q)s / r$, and this one fact turns "which scalings are integral" into a single gcd per shape. The step it gives, $t = r / \gcd(p(p-q), r)$, multiplied by the perimeter per unit $s$, is the perimeter $L$ of the smallest member of each family.

The lcm. From $\gcd(a,b) \cdot \mathrm{lcm}(a,b) = ab$ comes the one identity worth memorising, including the placement of the division:

return a // gcd(a, b) * b

Divide first. a * b // gcd(a, b) is mathematically identical and forms an intermediate product that can be enormous — harmless in Python, an overflow in C. Problem 5 folds this across a range to get the smallest number divisible by everything in it, and problem 853 uses it to combine periods, which is the recurring reason to want an lcm at all: two cycles of lengths $a$ and $b$ realign after $\mathrm{lcm}(a, b)$ steps.

A quantity in its own right. The one that is easy to miss. The line segment from the origin to a lattice point $(x, y)$ passes through exactly $\gcd(x, y) - 1$ interior lattice points, and the primitive step along it is $(x/g,\ y/g)$. Problem 91 uses both facts at once — $m = \gcd(x, y)$ gives the primitive perpendicular direction, and the same $m$ scales how far that direction can be walked inside the grid:

min(x * m // y, m * (coordinate_limit - y) // x)
for x in range(1, coordinate_limit + 1)
for y in range(1, coordinate_limit)
for m in [math.gcd(x, y)]

Problem 504 needs the same count on all four sides of a quadrilateral, because Pick's theorem converts an area plus a boundary count into an interior lattice-point count, and the boundary count is a sum of gcds. Problem 182 counts RSA exponents whose number of unconcealed messages is minimal, and that number is a product of two gcd terms — here the gcd is not a filter or a normaliser but the actual value being tabulated.

Two more uses are worth knowing even though they fit none of the four. The first: the quotients the loop throws away are themselves data. The sequence $q_1, q_2, \dots$ produced by successive divisions is exactly the continued fraction expansion of $a/b$, and running the algorithm to collect them is how you convert a rational into that form. Problem 175 does precisely this — it reduces its fraction by the gcd and then keeps walking, emitting one run per Euclidean quotient, because the quotient sequence is the answer's structure rather than a by-product.

The second: the step itself can be a model of something else, with no gcd wanted at all. Problem 700 asks for the record lows of the orbit $x_n = na \bmod m$ for a modulus near $4.5 \times 10^{15}$, far too long to walk. The trick is to track two records: $L$, the smallest term so far, and $D$, the smallest distance below $m$ so far. Adding their indices adds their residues, so the next term that can beat either record is $L - D$. If $D < L$ that is a new low; otherwise $D - L$ is a new gap. That is Euclid's subtractive algorithm running on $(L, D)$, which is the geometry of the three-distance theorem in another form. It also sharpens the "use the remainder" advice above. The solution collapses runs of gap steps with a %, because nobody needs to see those intermediates, but it deliberately keeps the coin branch subtractive, because every intermediate there is a record it has to sum. When the steps themselves are the output, unrolling the division is correct and costs nothing extra. The loop also stops at the right place for free: the smallest positive value $na \bmod m$ can take is $\gcd(a, m)$ (Bézout), so the walk ends exactly when the "gap" becomes a multiple of the "low".

How to reason about it

  • Put the cheap test first. A gcd is a few divisions, which is cheap but not nothing when it sits inside a double loop over millions of pairs. Problem 139's parity check runs before its gcd precisely so that half the pairs never reach it, and the source says so. Ordering a filter chain by ascending cost is the most reliable easy win in this whole family of enumerations.
  • Tabulate when the same small pairs recur. Problem 504 needs $\gcd(i, j)$ for every pair up to a small bound and computes the full $O(m^2)$ table once, up front. When your operands are bounded and the query count exceeds the table size, precompute — and note that the table can itself be filled by a sieve rather than by $m^2$ calls, if that ever becomes the bottleneck.
  • Enumerate the primitives and scale. The deeper move behind the coprimality guard: instead of enumerating every object and deduplicating, enumerate one representative per equivalence class and multiply out the scalings. Problems 75 and 139 both generate each primitive triple once and then count its multiples in $O(1)$, turning an $O(L^2)$ search into an $O(L)$ one. Problem 257 uses both of the gcd's roles in that move: $\gcd(p, q) = 1$ picks one representative per shape, and the integrality gcd gives the shape's smallest perimeter $L$, so the shape contributes $\lfloor N / L \rfloor$ triangles with no further loop. When a gcd condition appears in a loop, this is usually the reason.
  • Know the edge cases. $\gcd(0, n) = n$ and $\gcd(0, 0) = 0$; the loop above already gives both. Python's math.gcd always returns a non-negative value, but a hand-written C version does not: C's % takes the sign of the dividend, so a negative operand yields a negative gcd unless you take the absolute value on entry. Problems that only ever pass positive counts will never notice, which is exactly why the C helper gets copied into the next problem unfixed.
  • If you need the coefficients, you need the other algorithm. The plain loop discards the information that answers "which combination of $a$ and $b$ gives the gcd". When the goal is a modular inverse or a linear Diophantine equation, reach for the extended Euclidean algorithm, which runs the same divisions and keeps the bookkeeping. When it is not, do not pay for it.
  • Do not hand-optimise it. The binary GCD replaces division with shifts and subtractions and was a real win on machines with slow dividers; on current hardware, against a compiler that knows the idiom, it is roughly a wash. math.gcd is implemented in C with a fast path for machine-word operands and will beat anything written in Python. Usually the gcd is not the bottleneck; the loop that calls it is.
  • When it is the bottleneck, vectorise the loop, not the gcd. Problem 257 is the exception. It makes two gcd calls for each of tens of millions of $(p, q)$ pairs, and those calls are the whole cost. Its Python solution builds one np.arange of candidate $p$ per $q$, masks it with np.gcd(p, q) == 1, and calls np.gcd again for the integrality term. The Euclidean loop then runs element-wise in compiled code, and the interpreter only steps through the $O(\sqrt{N})$ outer loop. The C port calls the scalar helper inside a plain double loop and is only about a quarter faster. Once the gcd is a ufunc, Python and C are running the same divisions.

Problems27 / 27

  • ● 0005 — Smallest Multiple
  • ● 0026 — Reciprocal Cycles
  • ● 0033 — Digit Cancelling Fractions
  • ● 0039 — Integer Right Triangles
  • ● 0071 — Ordered Fractions
  • ● 0075 — Singular Integer Right Triangles
  • ● 0091 — Right Triangles with Integer Coordinates
  • ● 0101 — Optimum Polynomial
  • ● 0127 — abc-hits
  • ● 0129 — Repunit Divisibility
  • ● 0130 — Composites with Prime Repunit Property
  • ● 0139 — Pythagorean Tiles
  • ● 0141 — Square Progressive Numbers
  • ● 0175 — Fractions and Sum of Powers of Two
  • ● 0180 — Golden Triplets
  • ● 0182 — RSA Encryption
  • ● 0183 — Maximum Product of Parts
  • ● 0195 — $60$-degree Triangle Inscribed Circles
  • ● 0257 — Angular Bisectors
  • ● 0420 — $2 \times 2$ Positive Integer Matrix
  • ● 0504 — Square on the Inside
  • ● 0605 — Pairwise Coin-Tossing Game
  • ● 0686 — Powers of Two
  • ● 0694 — Cube-full Divisors
  • ● 0700 — Eulercoin
  • ● 0764 — Asymmetric Diophantine Equation
  • ● 0853 — Pisano Periods 1