25 - Finding the Greatest Common Divisor

Summary

Introduction

One of the more important mathematical concepts students encounter is that of the greatest common divisor (gcd), the greatest positive integer that divides two integers. It can be used to solve indeterminate equations, compare ratios, construct continued fraction expansions, and in Sturm's method to determine the number of real roots of a polynomial. For a development of these applications, see [1]. Most of the significant applications of the gcd require that it be expressed as a linear combination of the two given integers. The gcd and its associated linear equation provide an efficient way to find inverses of elements in cyclic groups, to compute continued fractions, to solve linear Diophantine equations, and to decrypt and encrypt exponential ciphers. In order to calculate the gcd and determine the required linear combination, most textbooks present the ancient but effective Euclidean approach putting an algebraic strain on many students. A more innovative technique, Saunderson's algorithm, offers a much more efficient approach. The algorithm can be introduced in number theory, modern algebra, computer science, cryptology, and other courses that require a method to find the greatest common divisor of two integers and its associated linear combination.

Historical Background

Euclid's Elements, written around 300 B.C., consists of a deductive chain of 465 propositions in thirteen “books” or what we would refer to as chapters. The Elements serves as a synthesis of Greek mathematical knowledge and has made Euclid the most successful textbook author of all time. It is one of the most important texts in intellectual history. He was a great synthesizer for it is believed that relatively few of the geometric theorems in the book were his invention.