Euclidean Algorithm

Section 4.3 Euclidean Algorithm

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.

🔗

Figure 4.16. Euclidean Algorithm by Matt Farmer and Stephen Steward

🔗

We formulate the Euclidean Algorithm in our algorithm format.

🔗

Algorithm 4.17. Euclidean Algorithm.

Input: 🔗: Two natural numbers \(a\) and \(b\) with \(a>b\)
🔗
Output: 🔗: The greatest common divisor \(\gcd(a,b)\) of \(a\) and \(b\)
🔗

repeat
🔗
1. let \(r:={a}\fmod {b}\)
  🔗
  
  🔗
2. let \(a:=b\)
  🔗
  
  🔗
3. let \(b:=r\)
  🔗
  
  🔗
🔗
until \(r=0\)
🔗

🔗
return \(a\)
🔗

🔗

🔗

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.

🔗

Example 4.18. Greatest common divisor of \(612\) and \(56\).

We compute the greatest common divisor of \(612\) and \(56\) with Algorithm 4.17.

🔗

Input: \(a:=612\) and \(b:=56\)

🔗

1. let \(r:=612\fmod 56=52\)
  🔗
  
  🔗
2. let \(a:=56\)
  🔗
  
  🔗
3. let \(b:=52\)
  🔗
  
  🔗
🔗
As \(r=52\) the statement \(r=0\) is false. So we continue Item 1 with:
🔗

🔗

1. let \(r:56\fmod 52=4\)
  🔗
  
  🔗
2. let \(a:=52\)
  🔗
  
  🔗
3. let \(b:=4\)
  🔗
  
  🔗
🔗
🔗
As \(r=4\) the statement \(r=0\) is false. So we continue Item 1 with:
🔗

🔗

1. let \(r:=52\fmod 4=0\)
  🔗
  
  🔗
2. let \(a:=4\)
  🔗
  
  🔗
3. let \(b:=0\)
  🔗
  
  🔗
🔗
🔗
As \(r=0\) the statement \(r=0\) is false. So we continue Item 1 with:
🔗

🔗
We return the value of \(a\) which is \(4\text{.}\)
🔗

🔗

🔗

Output: \(4\)

🔗

We have found that the greatest common divisor of \(612\) and \(56\) is \(4\text{.}\)

🔗

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.

🔗

Example 4.19. Greatest common divisor of \(612\) and \(56\) compact.

We compute the greatest common divisor of \(612\) and \(56\) with Algorithm 4.17. In the table we give the values of the variables at the end of step 1 in each iteration of the loop.

🔗

step	\(r\)	\(a\)	\(b\)

Input		\(612\)	\(56\)

(1)	\(612\fmod 56=52\)	\(56\)	\(52\)
(1)	\(56\fmod 52=4\)	\(52\)	\(4\)
(1)	\(52\fmod 4=0\)	\(4\)	\(0\)
Output		4

🔗

Thus the output is \(\gcd(612,56)=4\text{.}\)

🔗

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.

🔗

Example 4.20. Euclidean algorithm interactive.

🔗

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

🔗

Checkpoint 4.21. Euclidean Algorithm.

Follow these step to compute the greatest common divisor of \(a:=72\) and \(b:=67\text{:}\)

🔗

let \(r:=a \bmod b =\) and let \(a:=b =\) and let \(b:=r =\)

🔗

let \(r:=a \bmod b =\) and let \(a:=b =\) and let \(b:=r =\)

🔗

let \(r:=a \bmod b =\) and let \(a:=b =\) and let \(b:=r =\)

🔗

let \(r:=a \bmod b =\) and let \(a:=b =\) and let \(b:=r =\)

🔗

The greatest common divisor of 72 and 67 is \(a=\)

🔗

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

🔗

Theorem 4.22.

Let \(n\) be a natural number. Then \(\gcd(n,n+1)=1\text{.}\)

🔗

Proof.

Let \(n\) be a natural number. We compute \(\gcd(n+1,n)\) using the Euclidean Algorithm. with Algorithm 4.17. In the table we give the values of the variables after step (1) in each iteration of the loop.

🔗

step	\(r\)	\(a\)	\(b\)
Input		\(n+1\)	\(n\)
(1)	\((n+1)\fmod n=1\)	\(n\)	\(1\)
(1)	\(n\fmod 1=0\)	\(1\)	\(0\)
Output		1

🔗

Thus, \(\gcd(n+1,n) = 1\text{,}\) and we conclude that \(n+1\) and \(n\) are coprime.

🔗

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

🔗

Example 4.23. \(238\) and \(237\) are coprime.

We compute the greatest common divisor of \(238\) and \(237\) with Algorithm 4.17. In the table we give the values of the variables after step (1) in each iteration of the loop.

🔗

step	\(r\)	\(a\)	\(b\)
Input		\(238\)	\(237\)
(1)	\(238\fmod 237=1\)	\(237\)	\(1\)
(1)	\(237\fmod 1=0\)	\(1\)	\(0\)
Output		\(1\)

🔗

Thus the output is \(\gcd(238,237)=1\text{.}\)

🔗

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.

🔗