Euclid's Algorithm for the Greatest Common Divisor

Introduction

More than two millennia ago Euclid (circa 300 BCE) described a method for computing the "greatest common measure" of two "numbers", and today we name our modern iterative algorithm for calculating the greatest common divisor of two numbers after him. Here we introduce and provide for instructors a student project based on Euclid's original source, designed for a course in introductory discrete mathematics or computer science.

The similarities and differences between our modern algorithms and what Euclid presented and proved are extremely fertile ground for initial student learning about algorithms and proofs. For instance, as shown below, Euclid adopted a highly geometric description of his numbers as lengths.

Our project Euclid's Algorithm for the Greatest Common Divisor is ready for students, and the Latex source is also available for instructors who may wish to modify the project for students. The comprehensive "Notes to the Instructor" presented next are also appended to the project itself. 

Our primary source project module for students is part of a larger collection published in Convergence, and an entire introductory discrete mathematics or computer science course can be taught from various combinations selected from these projects. For more projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science.

Notes to the Instructor

This project is for students in an introductory computer science or discrete mathematics course. It is based on Euclid's original source for the Euclidean algorithm calculating the greatest common divisor of two numbers.

The project has few formal prerequisites. Euclid did use proof by contradiction, and many instructors choose this project to follow after a unit on logic and proof techniques, although it could also be used to introduce proof by contradiction. Additionally, some optional final exercises use finite mathematical induction to prove formally the correctness of Euclid's algorithm for calculating the greatest common divisor. A few other optional exercises rely on some computer programming. The project can be completed in two to three class weeks.

This project offers several features different from a textbook treatment of the Euclidean algorithm.

First, students will think deeply while interpreting Euclid's description of the algorithm, challenged to convert his verbal and quite geometric description into modern formulation and implementation. This will involve reconciling multiple possible interpretations, including highlighting the distinction between repeated subtraction and division with remainder. Algebra as practiced today did not exist in Euclid's time, and the exercises develop an algebraic enactment of Euclid's algorithm.

Second, in the latter part of the project, optional exercises lead students to make a careful modern proof of the mathematical correctness of the iterative algorithm, going beyond Euclid's own argument for why it produces the greatest common divisor.

Euclid's presentation also naturally sets the stage, if desired, to extend the project by comparing and contrasting with a modern day recursive, as opposed to iterative, formulation of the algorithm, as it is often presented to computer science students. And the highly contrasting proofs of correctness in these two very different settings can be explored.

The project can be used to provide a first introduction to the notion of "computation method" or "algorithm" and to explore concepts like iteration and the efficacy of mathematical induction as a method of proof, thereby covering a number of typical course topics. The project can even be used to introduce induction.

With this project students can develop their skill at creating proofs in a highly authentic and motivated context, but just as importantly they can experience the evolution of what is accepted as a valid proof or a well-described algorithm. Students will learn that the method presented by Euclid to compute the greatest common divisor and the proof of its correctness that he provided would not be formally accepted today. Students will also experience, however, that Euclid was somehow able to convey the ideas behind his method and proof in such a way that they can reform Euclid's writing into a modern algorithm and proof of correctness. In this way, the project provides students not only with a strong sense of connection to the past, but also serious practice with subtle issues about the nature of adequate mathematical formulation and proof today.

Students can work productively in groups on this project, with group or individual writeups. They will need substantial guidance with the optional exercises near the end of the project, which formalize the algorithm in wholly modern terms and prove correctness using finite induction. In any case, the instructor should always work through all details before assigning any student work.

The issue of "unit" versus "number" will provide grist for substantial class discussion and careful attention to detail in interpreting Euclid's analysis of his algorithm. It seems clear that by "unit" Euclid meant what we today call the number "one", but that to him it was not a number. Why this was the case for Euclid, and how it played out in his writings, is rich material for critical consideration when studying Euclid.

The heart of Euclid's description of his algorithm actually has multiple possible interpretations, and can produce different implementations. Instructors should prepare well on this matter before discussions with students. In particular, did Euclid intend iterations of repeated subtraction of smaller from larger, or did he intend iterations of the division algorithm?

Download the project Euclid's Algorithm for the Greatest Common Divisor.

Download the modifiable Latex source file for the project.

Again, this primary source project module for students is part of a larger collection of historical projects for learning discrete mathematics and computer science published in Convergence. An entire introductory discrete mathematics or computer science course can be taught from various combinations selected from these projects. For more projects, see Primary Historical Sources in the Classroom: Discrete Mathematics and Computer Science.

Acknowledgment

The development of curricular materials for discrete mathematics has been partially supported by the National Science Foundation's Course, Curriculum and Laboratory Improvement Program under grants DUE-0717752 and DUE-0715392 for which the authors are most appreciative. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.