Page 290 - Discrete Mathematics and Its Applications

4.3 Primes and Greatest Common Divisors 269

ALGORITHM 1 The Euclidean Algorithm.

procedure gcd(a, b: positive integers)
x := a
y := b
while y = 0
r := x mod y
x := y
y := r
return x{gcd(a, b) is x}

In Algorithm 1, the initial values of x and y are a and b, respectively. At each stage of the
procedure, x is replaced by y, and y is replaced by x mod y, which is the remainder when x is
divided by y. This process is repeated as long as y = 0. The algorithm terminates when y = 0,
and the value of x at that point, the last nonzero remainder in the procedure, is the greatest
common divisor of a and b.
We will study the time complexity of the Euclidean algorithm in Section 5.3, where we
will show that the number of divisions required to find the greatest common divisor of a and b,
where a ≥ b,is O(log b).

gcds as Linear Combinations

An important result we will use throughout the remainder of this section is that the greatest
common divisor of two integers a and b can be expressed in the form

sa + tb,

where s and t are integers. In other words, gcd(a, b) can be expressed as a linear combination
with integer coefficients of a and b. For example, gcd(6, 14) = 2, and 2 = (−2) · 6 + 1 · 14.
We state this fact as Theorem 6.

THEOREM 6 BÉZOUT’S THEOREM If a and b are positive integers, then there exist integers s and t
such that gcd(a, b) = sa + tb.

ÉTIENNE BÉZOUT (1730–1783) Bézout was born in Nemours, France, where his father was a magistrate.
Reading the writings of the great mathematician Leonhard Euler enticed him to become a mathematician. In
1758 he was appointed to a position at the Académie des Sciences in Paris; in 1763 he was appointed examiner
of the Gardes de la Marine, where he was assigned the task of writing mathematics textbooks. This assignment
led to a four-volume textbook completed in 1767. Bézout is well known for his six-volume comprehensive
textbook on mathematics. His textbooks were extremely popular and were studied by many generations of
students hoping to enter the École Polytechnique, the famous engineering and science school. His books were
translated into English and used in North America, including at Harvard.
His most important original work was published in 1779 in the book Théorie générale des équations
algébriques, where he introduced important methods for solving simultaneous polynomial equations in many unknowns. The most
well-known result in this book is now called Bézout’s theorem, which in its general form tells us that the number of common points on
two plane algebraic curves equals the product of the degrees of these curves. Bézout is also credited with inventing the determinant
(which was called the Bézoutian by the great English mathematician James Joseph Sylvester). He was considered to be a kind person
with a warm heart, although he had a reserved and somber personality. He was happily married and a father.