Attributed to Euclid (c. 300 BCE), but likely known even earlier, this is the oldest surviving general algorithm — a procedure that has been executed by humans, scribes, and now silicon for over two thousand years. Its endurance is not an accident: it reveals something fundamental about the integers.

The core observation is simple yet profound: any common divisor of two numbers also divides their remainder. By repeatedly replacing the larger number with the remainder, we descend through ever‑smaller pairs until the greatest common divisor (gcd) appears as the last non‑zero remainder. There is no guessing, no factorization — just pure, relentless reduction.

This invariance is the hidden architecture beneath the surface of arithmetic. The algorithm does not just compute; it reveals a relationship that was always there.

The Euclidean algorithm has a secret double life. If we track the quotients and keep careful account, the same steps that yield the gcd also produce two integers — often called Bézout coefficients — that combine the original numbers to make the gcd:

This is the extended Euclidean algorithm. The coefficients x and y are not unique; they form a family, a kind of echo of the division steps. The existence of such integers is a theorem (Bézout's identity), but watching them emerge from the backward substitutions gives a tangible sense of how the integers intertwine.

• For coprime numbers (gcd = 1), this identity becomes a key to modular division.
• The signs of x and y alternate, a quiet rhythm in the arithmetic.

This is not a trick; it is a structural consequence of the fact that the integers form a principal ideal domain — but even without that language, one can feel the inevitability.

When gcd(a, n) = 1, the Bézout identity a·x + n·y = 1 reduces modulo n to a·x ≡ 1 (mod n). That x — taken modulo n — is the modular inverse of a. It is the number that undoes multiplication by a in the finite ring ℤ/nℤ.

The existence of inverses is what makes ℤ/pℤ (p prime) a field: every nonzero element has a partner that multiplies to 1. But the extended Euclidean algorithm does more than assert existence — it actually produces the inverse, step by step, from the same quotients used to find the gcd.

In the interactive tool above, you can see this happen. When gcd = 1, the displayed Bézout coefficients directly give the inverse of a modulo b (or b modulo a). The numbers speak to each other through the algorithm.

The Euclidean algorithm is not confined to ordinary integers. It works in any Euclidean domain — rings that have a notion of division with remainder, such as:

• Polynomials over a field (like ℚ[x] or 𝔽₂[x]) — here the algorithm finds greatest common divisors of polynomials and leads to inverses in finite fields 𝔽_{pⁿ}.
• Gaussian integers ℤ[i] — revealing gcds in the complex plane.
• Some rings of algebraic integers (though not all).

In each setting, the same pattern repeats: repeated remainder steps, back‑substitution, and — when the gcd is a unit — an inverse emerges. The algorithm is a kind of archetype, a pattern that manifests wherever a sensible notion of "size" allows remainders to shrink.

The example of 𝔽₄ (the field with 4 elements) from the residue fields module: the Euclidean algorithm for polynomials gives the inverses there. The same ancient steps echo in new contexts.

This universality is part of what makes the algorithm feel less like a tool and more like a natural phenomenon.

The algorithm terminates because the remainders are non‑negative and strictly decreasing — an infinite descent is impossible in the natural numbers. This relies on the well‑ordering principle: every non‑empty set of positive integers has a least element. It is a topological fact about the number line, a guarantee that the process cannot continue forever.

One can view the Euclidean algorithm as a proof by infinite descent: if a common divisor larger than the last remainder existed, it would have to divide an even smaller number, eventually reaching a contradiction. The algorithm is, in this sense, a constructive version of a proof by contradiction.

There is something meditative in watching the numbers shrink: 108, 30, 18, 12, 6, 0. Each step is forced, inevitable. The algorithm does not invent; it uncovers what was latent in the numbers themselves.