Skip to main content

Chapter 4 Greatest Common Divisors

In the following we introduce another important algorithm, namely the Euclidean Algorithm (Algorithm 4.3.2). This algorithm gives us a way to systematically determine the greatest common divisor of two natural numbers. Then, we show how to use the computations in the Euclidean Algorithm (Algorithm 4.3.2) to determine the integers whose existence is guaranteed by Bézout's identity (Theorem 4.4.1).