The Euclidean Algorithm

This corpus computes class numbers by counting reduced forms. It runs a Pell solution as load-bearing work in the Ramanujan 1/π material. It gives Volume XI an identity that is entirely the algebraic floor. All of that rests on one procedure.

Counted at commit cc9a045, before this page existed: Euclid appears in 36 files, Elements in 48, Euclidean in 24. Euclidean algorithm appears in none. gcd appears in six.

So the corpus invokes the man across seven books and never states the procedure. This is Book IV, whose test is whether a reader can do something after reading. Here is the doing.

Replace the pair (a, b) by (b, a mod b) and repeat until the second entry is zero. What is left is the greatest common divisor. It terminates because the remainder is a non-negative integer that strictly decreases, and a decreasing sequence of non-negative integers is finite.

Keep the quotients. Most presentations throw them away, and they are the whole of what follows.

The extended form returns more. Running the recursion backwards gives integers x and y with ax + by = gcd, so the algorithm hands back a certificate and not only an answer. That is why it is load-bearing rather than merely old. Every modular inverse in this corpus is one of those x values.

Take the quotient list from the run above and read it as a continued fraction. [2, 3, 7] means 2 + 1/(3 + 1/7), which is 1071/462 exactly. This is not an analogy. The divisions Euclid performs and the partial quotients of a/b are the same numbers, produced by the same steps, and the verification script checks it on two thousand random pairs.

One computation, two readings. The algorithm is a gcd routine if you keep the last remainder and a continued-fraction expansion if you keep the quotients.

Which input makes it slowest? Every step divides, so the cheapest possible step is a quotient of 1, which merely subtracts. A run where every quotient is 1 is the slowest run, and the numbers that produce it are the Fibonacci numbers.

An exhaustive search over every pair below 400 finds the worst case at a consecutive Fibonacci pair, and the cost is exactly the index. This is Lamé's theorem of 1844, the first serious complexity result in mathematics: the number of steps is at most five times the number of digits in the smaller input, and the bound is attained here.

So the slowest input to the oldest algorithm is φ, which is the second constant of this corpus's operator chain. The connection is Lamé's and not ours. It is worth stating anyway, because the ladder appears here as a worst case rather than as a growth law, and the corpus has met it only in the second role.

The algorithm also runs on an irrational, where it never terminates but becomes periodic. For √29 the expansion is [5; 2, 1, 1, 2, 10] with period five.

Truncating it gives convergents, and each convergent p/q can be tested against p² − 29q². The first four give 5, −5, 4, and then:

The fourth convergent solves the negative Pell equation. And running the ordinary integer algorithm on 70/13 returns [5, 2, 1, 1, 2], which is exactly one period of √29.

Because 29 ≡ 1 mod 4, the ring of integers is ℤ[(1+√29)/2] and the fundamental unit is ε = (5 + √29)/2, of norm −1. The convergent just found is ε³. Square it:

And 9801 = 99² is the denominator in Ramanujan's 1/π series, the number Chapter Rπ is named for and docs/math-placement-map.md places in Volume XI as a core candidate.

There is a last detail worth the run. Euclid on 70/13 returns one period of √29. Euclid on 9801/1820 returns [5, 2, 1, 1, 2, 10, 2, 1, 1, 2], which is two. The corpus's number is two turns of the same wheel.

Three things, in order of how much they buy.

Compute a modular inverse, which is the extended form and two lines of code. Expand any quadratic irrational and read off its unit, which is what Volume XI needs and does not yet have in Lean. And test a claimed fundamental unit: if the period of the continued fraction and the power of the unit disagree, one of them is wrong, and the algorithm says which.