Integers and Modern Applications for the Uninitiated

We turn the strategy from Example 4.2.7 into an algorithm for finding greatest common divisors. As in the example, we repeatedly apply Theorem 4.2.6 3. 4 to replace the computation of \(\gcd(a,b)\) with \(\gcd(a\fmod b, b)\text{.}\) At each step, the numbers become smaller. We stop when the remainder \(a\fmod b\) is zero.

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

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

We now write 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. So 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.3.5, click each step of the Euclidean algorithm to see how the variable values change.

Now we use the Euclidean Algorithm (Algorithm 4.3.2) to prove that consecutive natural numbers are coprime.

We use a numerical example to show the proof of the theorem.