Euclid

Euclid

Euclid is associated with Alexandria around 300 BCE. Reliable personal information is scarce. Exact birth and death dates, a detailed education, and stories about his pupils should not be presented as securely documented biography. Some familiar accounts come from authors writing centuries later. MacTutor's discussion explains those evidentiary problems.

The surviving Elements is a mathematical text in thirteen books, covering more than plane geometry. Its subjects include proportion, arithmetic, incommensurable magnitudes, and solid geometry. Book I's twenty-three definitions are not the total number of definitions in the entire work. Nor are all thirteen books merely deductions from its five geometric postulates. The book-by-book contents make the structure visible.

For computer science, Euclid provides especially useful material for studying algorithmic invariants and the difference between a plausible construction and a fully justified one. These connections do not require calling him the inventor of all algorithms or formal reasoning.

A proof has dependencies

In Book I, Proposition 1, Euclid constructs an equilateral triangle on a given segment AB. Draw a circle centered at A through B, and another centered at B through A. Choose an intersection C. Since AC and AB are radii of the first circle, they are equal. Similarly BC = BA, so all three sides are equal.

The reasoning about equal lengths is clear. The existence of the required intersection is another matter: the opening postulates do not explicitly supply the needed circle-intersection principle. David Joyce's accompanying commentary identifies this gap. A picture can suggest an object without proving that the assumptions guarantee its existence. That is a productive way to read the text, rather than describing it as a completed modern formalization.

Worked mechanism: an invariant for greatest common divisors

Book VII, Proposition 2 finds a greatest common measure by reciprocal subtraction. The modern remainder algorithm below is an adaptation. Modern arithmetic also treats 1 as a number, whereas Euclid distinguishes the unit from a number, a multitude of units.

For nonnegative integers a and positive b, write a = qb + r, with 0 <= r < b. A positive integer d divides both a and b exactly when it divides both b and r:

• In one direction, r = a - qb, so divisibility is preserved by subtraction.
• In the other, a = qb + r, so it is preserved by addition.

Thus replacing (a,b) by (b,r) preserves the whole set of common divisors, not just a guessed answer.

For 252 and 198:

252 = 1*198 + 54
198 = 3*54  + 36
 54 = 1*36  + 18
 36 = 2*18  +  0

The answer is 18. At termination the pair is (18,0), whose positive common divisors are precisely the positive divisors of 18. The invariant transfers that result back to the original input.

Why must the process terminate? Every nonfinal remainder is a smaller nonnegative integer than the preceding positive divisor. There cannot be an infinite strictly descending sequence of such integers. This is a separate obligation from preservation of the answer.

A checkable certificate can be recovered by substitution:

18 = 54 - 36
   = 54 - (198 - 3*54)
   = 4*54 - 198
   = 4*252 - 5*198

Any common divisor of 252 and 198 therefore divides 18. Direct division confirms that 18 divides both inputs. Together these observations certify the result without requiring a verifier to trust every step of an implementation.

This distinction between computing an answer and checking a certificate appears throughout computer science. The connection here is mathematical; it does not mean ancient Greek notation implemented a modern proof assistant.

A finite list cannot contain every prime

Book IX, Proposition 20 proves that there are more primes than any assigned finite collection. In modern notation, take distinct primes p1,...,pk and form N = p1*...*pk + 1. A prime divisor of N cannot be in the list: otherwise it would divide both the product and N, and hence their difference 1.

The number N need not itself be prime. The argument needs a prime divisor of it. Confusing those two statements turns a correct proof into a false primality test. Euclid's formulation uses a least common multiple and a unit; the product formulation is a modern presentation of the same relevant divisibility argument.

Exercises

1. Compute gcd(391,299) using remainders. Recover integers u,v with 391u + 299v = gcd(391,299). Explain what your certificate proves.
2. Apply the prime construction to 2,3,5,7,11,13. Factor the result using 59 as a trial divisor. Explain why a composite answer leaves the proof intact.
3. In Proposition I.1, separate the existence claim from the equality proof. State an additional assumption that would justify the construction, and explain why the appearance of intersecting circles in a drawing is insufficient.

Compare your reasoning with the worked solutions

1. Computing and checking

391 = 299 + 92, 299 = 3*92 + 23, and 92 = 4*23. Hence the gcd is 23. Substitution gives 23 = 299 - 3*(391 - 299) = -3*391 + 4*299. Every common divisor must divide 23, and direct calculation gives 391 = 17*23 and 299 = 13*23. These two facts establish that 23 is the greatest common divisor.

2. A new divisor, not necessarily a prime output

The product is 30030, so N = 30031 = 59*509. Neither factor is in the input list. More generally, reduction modulo any listed prime gives remainder 1, regardless of whether N is prime. Thus the argument produces evidence that the original finite list omitted a prime; it does not promise that adding one to a prime product always yields a prime.

3. Auditing a construction

The proof assumes that the two specified circles have a common point distinct from A and B. An appropriate circle-intersection axiom or a theorem derived from a sufficiently explicit geometric foundation must establish that fact. Conditional on such a point, the radius equalities prove the triangle equilateral. A drawing is a particular representation, not a derivation of an existence statement from stated assumptions.

Sources and reading limits

• Euclid biography, University of St Andrews: uncertain life history and later accounts.
• Elements contents, David E. Joyce, Clark University: the structure of all thirteen books.
• I.1 and commentary, VII.2 and commentary, and IX.20 and commentary: accessible primary propositions with editorial explanations. The numbered examples and certificates above are original teaching material.