MAT 112 Integers and Modern Applications for the Uninitiated

We formulate an algorithm for computing greatest common divisors that follows the strategy we used in Example 4.15. As in the example we repeatedly apply Theorem 4.14 3. 4 to reduce the computation of \(\gcd(a,b)\) to the \(\gcd(a\fmod b, b)\text{.}\) This makes the numbers of which we compute the greatest common divisor smaller in every step, until the remainder \(a\fmod b\) is zero.

The algorithm is named after the Greek mathematician Euclid, who first described it in Book 7 of his Elements (around 300 BC) [5]. To make the representation of the algorithm easier, we only allow natural numbers (positive integers) as inputs.

In the video in Figure 4.16 we introduce the algorithm and use it to find greatest common divisors.

We formulate the Euclidean Algorithm in our algorithm format.

In the algorithm, \(r\) becomes smaller in each iteration of the loop. As \(r\) is a non-negative integer, it has to become zero eventually. Thus after finitely many steps the algorithm returns a result.

Next we repeat the previous example. Instead of explicitly writing down what happens in every step, we write down the value of each variable at the end of step 1. This notation is more suitable for the computation of greatest common divisors by hand.

In the interactive algorithm in Example 4.20 click your way through the steps of the Euclidean algorithm to see how the values in the variables change in each step.

In Checkpoint 4.21 work through the steps of the Euclidean algorithm to compute a greatest common divisor.

We now use the Euclidean Algorithm (Algorithm 4.17) to prove that consecutive natural numbers are coprime.

We illustrate the proof of the theorem with a numerical example.

In Checkpoint 4.24 compute greatest common divisors. For some of the problems you do not need the Euclidean algorithm, but can apply properties of greatest common divisors to speed up the computation.