Greatest Common Divisor: Algorithm and Proof

Finding the greatest common divisor of two integers is foundational to a variety of mathematical problems from operations with fractions to modern cryptography.One common algorithm taught in primary school involves finding the prime factorization of the two integers, which is sufficient for finding the greatest common divisor of two small integers.However, the prospect of trying to find the prime factorization of two large numbers is daunting.Instead of looking in our modern textbook for a better algorithm, let's go back to the source and discover simple, yet powerful, algorithms in the mathematics of ancient China and ancient Greece.We will discover that the two communities formulated similar algorithms for finding the greatest common divisor, yet they did so in completely different contexts.The first section of this project introduces the mutual subtraction algorithm in ancient China, tracing its development through different texts dating from ca. 200 BCE to 263 CE.The mutual subtraction algorithm was introduced in the context of reducing fractions, still the first place it is used in modern mathematics education.The second section explores the algorithm from the text of Euclid's Elements, written ca.300 BCE [Euclid, 2002].In the Elements, Euclid developed the basic tenets of geometry and number theory.The geometric inspiration carried over into the number theory, as numbers were represented as line segments with length a multiple of a unit.The algorithm for finding the greatest common divisor was discussed in the context of measuring line segments.In modern mathematics, the algorithm is essential to many areas of number theory and algebra, including RSA cryptography.Where have you encountered the greatest common divisor?The common subtraction algorithm is known as the Euclidean algorithm in Western mathematics.Along with the practical technique for finding the greatest common divisor, it is also often one of the first theorems students encounter in a proof-based course in number theory, discrete mathematics or abstract algebra.Students are expected to understand why the algorithm works, not simply know how to perform the calculations.The explanations for why the algorithm worked were very different in the ancient Chinese and Greek texts.This contrast in the ancient texts, and a comparison with a modern proof, is also a beautiful example of the history of mathematical proof.In this project we will explore the history of the Euclidean algorithm, both as a practical tool and as an example of the standard for proof at different times in different mathematical communities.