Chapter 4 Greatest Common Divisors
Determine whether an integer divides another integer.
Recognize the Euclidean algorithm.
Compute greatest common divisors.
Compute the cofactors from a special case of Bézout's identity.
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).