Euclid: the Algorithm and the Format

Right now, all over the world, computers are running an algorithm that was written down in a book from 300 BCE. The book has thirteen volumes but zero equations, and for twenty-three centuries nearly everything we have called rigorous in mathematics has been written in its shape. The book is the Elements. The author is Euclid. We don't know his face, but we have the book.

Ten assumptions#

The Elements opens with a construction. Given a segment, build an equilateral triangle on it: swing a circle from each endpoint through the other, connect the crossing point to both endpoints, and all three segments are radii of one circle or the other, so they have the same length. One proposition in, you can see the shape of his thinking. Start from what you are allowed, build, then let the picture force the conclusion.

What you are allowed is spelled out in advance. Definitions first: point, line, circle. Then five postulates about geometry: you can draw a line between any two points, extend any segment, draw a circle with any center and radius, all right angles are equal, and the fifth, longer than the other four put together, which says that if a line crossing two others makes interior angles on one side summing to less than two right angles, the two lines meet on that side. Hold on to that fifth one. Then five common notions, the logical rules any argument may use: things equal to the same thing are equal to each other, equals added to or subtracted from equals give equals, things that coincide are equal, and the whole is greater than the part.

Ten assumptions. Every theorem in thirteen books traces back to them. Almost: proposition one already needs a continuity principle Euclid never states to make the two circles meet, a gap Hilbert would have to plug when he rebuilt the axioms in 1899. No appeals to authority, no "it's obvious." The Greeks had been doing geometry for centuries before Euclid; what was new was the architecture. Euclid didn't invent the theorems. He invented the machinery for being sure about them. Rigor as a technology.

Book I builds with that machinery: side-angle-side congruence in proposition 4, then the pons asinorum in proposition 5, where two auxiliary lines and two uses of SAS prove the base angles of an isosceles triangle equal. Proposition 32 proves the angles of a triangle sum to 180 degrees by drawing a parallel through one vertex and comparing angles, a comparison that works only because of postulate five. That is a debt, and it gets called in later. The climax, proposition 47, is the Pythagorean theorem, proved by splitting the square on the hypotenuse into two rectangles and showing, twice by SAS, that each equals a leg square. The picture is the proof.

The algorithm#

Halfway through, Euclid turns from shapes to numbers. Book VII, proposition 2: a procedure that takes two whole numbers and returns their greatest common divisor. Euclid subtracts the smaller from the bigger, again and again; we batch the subtractions into a division. Run it on 252 and 105. Divide the bigger by the smaller and keep the remainder:

$$252=2·105+42$$

$$105=2·42+21$$

$$42=2·21+0$$

When the remainder hits zero, the last nonzero remainder is the answer: $\text{gcd}(252,105)=21$. Three divisions.

Why it works: any number dividing both $a$ and $b$ also divides their difference, hence divides $b$ and the remainder, and conversely. So the set of common divisors is exactly the same at every step. The numbers shrink, but what you are looking for doesn't change. And the shrinking has to stop, because positive integers have a floor.

Pause and try: run the algorithm on 1071 and 462.

$1071=2·462+147$, then $462=3·147+21$, then $147=7·21+0$. So $\text{gcd}(1071,462)=21$, in three divisions.

Euclid does not treat termination as obvious. Each division produces a remainder strictly smaller than the divisor, so the remainders strictly decrease. Could that go on forever? Then you would have infinitely many positive whole numbers, each smaller than the last. But the smallest positive whole number is one, and below one there are none at all. The sequence runs out of floor. This move now has a name, infinite descent, and it is equivalent to well-ordering and to mathematical induction. Elsewhere in Book VII, at proposition 31, Euclid makes the principle explicit, before any of those names exist.

The other great proof in the number books is Book IX, proposition 20: there are infinitely many primes. Suppose the primes were a finite list $p_1,p_2,\dots ,p_n$. Multiply them all and add one: $q=p_1{p}_2\cdots p_n+1$. Then $q$ has a smallest divisor greater than one, which must be prime, and it is not on the list, because dividing $q$ by any listed prime leaves remainder one. The list was supposed to be complete. Contradiction: no finite list of primes is ever complete. That proof has been in continuous use for twenty-three centuries.

The first crack#

In Book X, Euclid runs the same procedure on line segments: lay the shorter against the longer, mark off copies, take the remainder, swap, repeat. If it stops, the final segment is the common measure of the two lengths, a gcd done with a ruler.

But segments have no floor, so nothing forces termination, and sometimes it never comes. Proposition X.2 shows that if the procedure never stops, the two lengths have no common measure at all: they are incommensurable. That is exactly what happens to the side and diagonal of a square. Lay the side against the diagonal and the leftover piece is the side of a new, smaller square with the same side-to-diagonal ratio, one to $\sqrt{2}$. Run it again: a smaller square, and another, forever. So $\sqrt{2}$ is no ratio of whole numbers. One reconstruction has the Greek discovery of irrationality happen exactly here: not with algebra, but because this algorithm refused to stop.

The second crack#

The other crack is the fifth postulate. Four postulates are short and quiet; the fifth feels like something that ought to be a theorem. For two thousand years mathematicians tried to prove it from the other four: Proclus, ibn al-Haytham, Khayyam, Wallis, Saccheri, Lambert, Legendre. Every one failed or smuggled in an assumption equivalent to the thing being proved.

In the 1820s and 30s, Gauss, Lobachevsky, and Bolyai independently saw why. The fifth postulate isn't a theorem. It's a choice. Assume instead that many parallels pass through a point off a line and you get hyperbolic geometry, consistent, negatively curved like a saddle, with triangle angle sums below 180 degrees. Assume no parallels exist and, loosening one more of Euclid's assumptions, you get elliptic geometry, the sphere, where lines are great circles and triangles sum to more than 180. Riemann generalized all of it to curved spaces of any dimension, and a century after Gauss, Einstein wrote general relativity in Riemann's language: gravity is what happens when mass bends the geometry of spacetime. The crack in the foundation turned out to be a door into physics.

Both cracks came from the same move: the method, applied to its own foundations, showed where the foundations ran out. Once it handed us a new kind of number, once a new kind of space. Rigor is a technology for finding limits, and limits sometimes turn into doors.

Still here#

The Elements never stopped being read: copied by hand for a thousand years, translated into Arabic in Baghdad, back into Latin in Toledo, then into every European language. Newton learned from it; Spinoza wrote his Ethics in Euclidean style; Lincoln read it by candlelight to learn how to make an argument. And Book VII, proposition 2 never went away either. TLS handshakes, RSA keys, elliptic curve signatures: the modular inverses inside key generation and curve arithmetic descend from Euclid's algorithm. In code it is three lines:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

There are variants with better constants at everyday sizes and better asymptotics at cryptographic ones, but the idea at the center is still Euclid's, essentially unimproved.

The bigger inheritance is the format itself: axioms at the top, propositions below, each proved from what came before. Hilbert used it to rebuild geometry in 1899. Bourbaki used it to rewrite mathematics in the twentieth century. Open a proof assistant today, Lean, Coq, Isabelle, and you are looking at a machine-checkable version of the same form, every claim traceable to the starting assumptions. A mathematician from Alexandria invented the shape of a rigorous argument, and every mathematician since has been writing inside it.

If you remember three things#

1. The Elements derives thirteen books of theorems from ten explicit assumptions; the new invention was not the geometry but the architecture, rigor as a technology.
2. The gcd algorithm of Book VII works because common divisors are preserved at every step and positive integers have a floor; run on segments, where there is no floor, its non-termination proves $\sqrt{2}$ irrational.
3. The method exposed its own limits twice, and each limit became a door: a new kind of number from the algorithm that wouldn't stop, and a new kind of space, eventually Einstein's, from the postulate that wouldn't be proved.