More on the Euclidean Algorithm

--- tags: mth350 --- # More on the Euclidean Algorithm This document expands a little on **Investigation 1.2.6** in your textbook. ## What are algorithms, and what do we need to prove about them? The Euclidean Algorithm is an *algorithm*, that is, a computational process that --- like a computer program --- accepts input, then goes through some clearly-stated processing steps to produce an output. There are two things that we always want to know about any algorithm we use: 1. **Does the algorithm always stop?** We don't want algorithms to get stuck in infinite loops like you sometimes see on a computer! So whenever we are coming up with an algorithm, we have to provide a solid argument that there is a *stopping condition* that is *always met*. 2. **Does the algorithm always produce the correct results, whenever the input is valid?** Obviously we would also insist that any algorithm that claims to compute something, actually does the job correctly *every time*. A familiar example of an algorithm is long division. The inputs for long division are two natural numbers $a$ and $b$. The outputs are two natural numbers $q$ and $r$ such that $a = bq + r$ and $0 \leq r < b$. For example, if you "plug in" $a = 27$ and $b = 4$ into the long division algorithm, you end up getting the outputs $q = 6$ and $r = 3$. We know this is the correct output because * The condition that $a = bq + r$ is met, because $27 = (4)(6) + 3$; ad * The condition that $0 \leq r <b$ is met, because $0 \leq 3 < 4$. We have a theorem (1.2.5) that states that no matter what the inputs are (as long as they are not both zero), you will always get output that "works" --- the two outputs exist, they meet the conditions, and there are no other outputs possible that meet the conditions. That theorem is called the "Division Algorithm" but that's something of a misnomer, because the actual *algorithm* for division is not the result itself but the *steps of the process* for doing division. Those steps are expressed in the proof of Theorem 1.2.5 using the set $S = \{a - bs \, : \, s \in \mathbb{N}_0, a - bs \geq 0\}$ that we have worked so much with. When we proved Theorem 1.2.5, we had to prove: * The set $S$ had a smallest element --- which is really proving that *the algorithm has a stopping point that is always reached.* * The smallest element of $S$ is the number $r$ that we are supposed to output, and this gives us a way to compute $q$, and those two numbers satify all the required conditions --- which is really proving that *the algorithm always produces correct results*. :::warning :warning: **Providing a bunch of examples where an algorithm "works" is not a proof that it *always* "works".** Because maybe we only picked the easiest or most convenient examples; or maybe there's a wild example we didn't think of that breaks the algorithm. A mathematical proof is required if we want to show anything about "always". ::: ## The Euclidean Algorithm The **Euclidean Algorithm**, hinted at in Investigation 1.2.6 and which will be a big focus of a class meeting, is an algorithm that does the following: * The inputs of the Euclidean Algorithm are **any two natural numbers.** * There is one output of the Euclidean Algorithm: **the greatest common divisor (GCD) of the two numbers you put in.** So **the Euclidean Algorithm is a process for computing the GCD of two numbers.** And not just "a" way to compute it, it is still *the main algorithm* for doing so in modern computer programs because it is extremely efficient and fast. Here are the steps of the Euclidean Algorithm: 1. Start with the original inputs, and call them $a$ and $b$. If $a=b$, stop and output $\gcd(a,b) = a$. (Why?) Otherwise suppose $a$ is the larger of the two. 3. Divide $a$ by $b$, using the *Division Algorithm* to find natural numbers $q_0,r_0$ such that $a = bq_0 + r_0$ and $0 \leq r_0 < b$. If $r_0 = 0$, stop and output $\gcd(a,b) = b$. Otherwise keep going. 4. Divide $b$ by $r_0$, using the Division Algorithm to find natural numbers $q_1,r_1$ such that $b = r_0q_1 + r_1$ and $0 \leq r_1 < r_0$. If $r_1 = 0$, stop and output $\gcd(a,b) = r_0$. Otherwise keep going. 5. Divide $r_0$ by $r_1$, using the Division Algorithm to find natural numbers $q_2,r_2$ such that $r_0 = r_1q_2 + r_2$ and $0 \leq r_2 < r_1$. If $r_2 = 0$, stop and output $\gcd(a,b) = r_1$. Otherwise keep going. 6. Divide $r_1$ by $r_2$, using the Division Algorithm to find natural numbers $q_3,r_3$ such that $r_1 = r_2q_3 + r_3$ and $0 \leq r_3 < r_2$. If $r_3 = 0$, stop and output $\gcd(a,b) = r_2$. Otherwise keep going. 7. **Continue this process** of dividing $r_{i-1}$ by $r_i$ to get a quotient $q_{i+1}$ and a new remainder $r_{i+1}$ **until the new remainder $r_{i+1}$ is zero.** 8. When $r_{i+1} = 0$, stop and output $\gcd(a,b) = r_i$, where $r_i$ was the last *nonzero* remainder that you got. Later on, once we learn about *integer congruence*, we'll be able to write a computer program for the Euclidean Algorithm that only occupies four lines of code! ## Example of the Euclidean Algorithm at work Here's an example of how to use the Euclidean Algorithm to find $\gcd(160,100)$: <div style="padding:56.25% 0 0 0;position:relative;"><iframe src="https://player.vimeo.com/video/668244968?h=bef5c6257b&badge=0&autopause=0&player_id=0&app_id=58479" frameborder="0" allow="autoplay; fullscreen; picture-in-picture" allowfullscreen style="position:absolute;top:0;left:0;width:100%;height:100%;" title="Euclidean Algorithm example"></iframe></div><script src="https://player.vimeo.com/api/player.js"></script> <br> :::info Before doing anything else, run this algorithm yourself on paper or on a whiteboard, using a variety of pairs of natural numbers. Check your work on a computer or a calculator. Keep practicing until you can consistently get the correct answer by hand easily. ::: ## What we need to prove about the Euclidean Algorithm The Euclidean Algorithm is simple enough to *use*, but you probably have some major questions about *why it works*, including: * **How do we know that the stopping condition of a zero remainder will always happen?** Is it possible we could input two numbers to the algorithm that creates a never-ending sequence of division steps and the remainder never gets to zero? * **Why is the last nonzero remainder equal to the GCD of the two original numbers?** In other words, does the Euclidean Algorithm actually produce the right output? We have this sequence of remainders but it's not at all obvious what these have to do with $\gcd(a,b)$. This is what we will be focusing on in class and out-of-class wotk. **Here are problems you'll be exploring for Daily Prep:** :::success * **Euclidean Algorithm part 1:** Prove that the sequence $r_0, r_1, r_2, \dots$ produced in the steps of the Euclidean Algorithm will always eventually reach $0$. That is, in this sequence, there exists an $i$ such that $r_i = 0$. * **Investigation 1.2.5:** *(Phrased as a theorem)* Suppose $a,b,c \in \mathbb{Z}$ such that $a = bq + c$ for some $q \in \mathbb{Z}$, and $a$ and $b$ are not both zero. Prove that $\gcd(a,b) = \gcd(b,c)$. * **Euclidean Algorithm part 2:** Given the inputs $a$ and $b$ to the Euclidean Algorithm and the sequence of remainders $r_0, r_1, r_2, \dots$, prove that $\gcd(a,b) = \gcd(b, r_0)$, that $\gcd(b,r_0) = \gcd(r_0, r_1)$, and that for every $i$ we have $\gcd(r_i, r_{i+1}) = \gcd(r_{i+1}, r_{i+2})$ as long as the remainders are not all zero. (Hint: Investigation 1.2.5.) ::: Note: "Part 2" above together with a result from an earlier class meeting will prove that the last nonzero remainder in the chain of remainders in the algorithm, is the GCD of the original inputs. It's not totally obvious why, so please think about it.