## 10.2 Computing the Greatest Common Divisor [Theorem 10.6](LiB0081.html#1022) gives us a straightforward way to compute the greatest common divisor of two such integers. We simply find the unique factorizations for the two integers, determine which primes they have in common, and determine the greatest common divisor to be a product whose terms are these common primes, where the power of each prime in the product is the smaller of its orders in the two integers. [Example 10.13](LiB0081.html#1023) illustrated this. Another example follows: Example 10.16****We have ****  So  The problem with the previous technique is that it is not easy to find the unique factorization of an integer. You would have had some difficulty factoring the integers in the previous example if we had not given you the factorization. Now imagine the difficulty if the integers had 25 digits instead of 7. Indeed, noone has ever found a polynomial-time algorithm for determining the factorization of an integer. Next we show a more efficient way to compute the greatest common divisor. ### 10.2.1 Euclid's Algorithm [Theorem 10.1](LiB0081.html#1002) gives us a straightforward method for determining the greatest common divisor of two integers. Example 10.9 illustrates the method. Namely, to find the gcd(*n, m*) we recursively apply the equality in the theorem until *m* = 0, and then we return *n*. This method is called *Euclid's algorithm* because it was developed by Euclid around 300 B.C. The algorithm follows: Algorithm 10.1 **Euclid's Algorithm******Problem: Compute the greatest common divisor of a positive integer and a nonnegative integer. **** Inputs: a positive integer *n* and a nonnegative integer *m*. Outputs: the greatest common divisor of *n* and *m*. ``` int gcd (int n, int m) { if (m == 0) return n else return gcd (m, n mod m); // The C++ code would be n % m. } ``` Example 10.17****We find the greatest common divisor of the numbers in [Example 10.16](#ch10ex25) using [Algorithm 10.1](#ch10ex26). **** gcd(7,276,500,3,185,325) =gcd(3,185,325, 905,850) =gcd(90,5850, 767, 775) =gcd(467,775, 438, 075) =gcd(438,075, 29, 700) =gcd(29,700, 22,275) =gcd(22,275, 7,425) =gcd(7,425, 0) =7,425 It seemed pretty easy for us to compute the greatest common divisor using Euclid's algorithm. Let's analyze Algorithm 10.1 to see just how easy it is. First we need a lemma and a theorem. Lemma 10.1****If *n* > *m* ≥ 1 and the call gcd(*n, m*) (in [Algorithm 10.1](#ch10ex26)) results in *k* recursive calls where *k* ≥ 1, then ****  where *f k* is the *k*th number in the Fibonacci sequence. Proof: The proof is by induction. Induction base: Suppose the call gcd(*n, m*) results in 1 recursive call. Since *m* ≥ 1  Since *n* > *m*, we have *n* ≥ 2, which means  Induction hypothesis: Assume the lemma is true if *k* – 1 recursive calls are made. Induction step: Show the lemma is true if *k* ≥ 2 recursive calls are made. We need to show  The first recursive call is gcd(*m, n* mod *m*). Since there are *k* recursive calls in all, this call must require *k* – 1 recursive calls. Since *k* ≥ 2, there is at least one more recursive call, which means *n* mod *m* ≥ 1. Therefore, since *m* > *n* mod *m*, the conditions of the induction hypothesis are satisfied, which means  So we've arrived at one of the inequalities we needed to show. Towards showing the other, we have  where *q* is the quotient of dividing *n* by *m*. Since *n* > *m*, *q* ≥ 1. Inequality 10.2 and Equality 10.3 therefore imply  This completes the proof. Theorem 10.8****(**Lamé**) For every integer *k* ≥ 1 if *n* > *m* ≥ 1 and *m* *fk*, the *k*th number in the Fibonacci sequence, then the call gcd(*n, m*) (in [Algorithm 10.1](#ch10ex26)) results in less than *k* recursive calls. **** Proof: The proof follows immediately from the previous lemma. Next we analyze [Algorithm 10.1](#ch10ex26). Recall from [Section 9.2](LiB0075.html#887) that in numeric algorithms, the number(s) that is the input is not the input size. Rather the input size is the number of characters it takes to write the input. If we use binary encoding, the input size is the number of bits it takes to encode the number(s), which is about equal to the lg of the number(s). ****Analysis of Algorithm 10.1 Worst-Case Time Complexity (Euclid's Algorithm) Basic operation: one bit manipulation in the computation of a remainder. Input size: the number of bits *s* it takes to encode *n* and the number of bits *t* it takes to encode *m*. That is,  Without loss of generality, we will analyze the case where 1 ≤ *m* < *n*. That is, if *m* = *n*, there will be no recursive calls, while if *m* < *n*, the first recursive call will be gcd(*m, n*), which means the first argument is larger. We will not determine the exact time complexity. Rather we will first show the number of recursive calls *Calls*(*s, t*) is Θ(*t*), and then we will find a bound for the worst-case time complexity. First we show *Calls*(*s, t*) is in *O* (*t*). Assuming *m* ≥ 2, let *ff* be the number in the Fibonacci sequence such that  In Example B.9 in Section B.2.1 we show that  Either *k* – 1 is odd or *k* – 2 is odd. Without loss of generality, assume *k* – 1 is odd. Owing to Equality 10.5 and Inequality 10.4, we have  Owing to Equality 10.4, [Theorem 10.8](#ch10ex29) implies  Inequalities 10.6 and 10.7 imply that  It is left as an execise to show that the call gcd(*f**k* +1, *fk*) requires exactly *k* – 1 recursive calls. We conclude that  where *W calls*(*s, t*) is the worst-case number of recursive calls for input size *s, t*. For each recursive call, we compute one remainder. It is left as an exercise to show that, if we use the standard long division algorithm (as discussed in [Section 2.6](LiB0020.html#207)) to compute the remainder, the worst case number of bit manipulations needed to compute *r* = *n* mod *m* for *m* < *n* is bounded above by  where *q* is the quotient of dividing *n* by *m*, and *c* is a constant. We will show if *r* > 0, then, for the input size sufficiently larger, the worst case number of bit manipulations needed to compute *r* is bounded above by  To that end, since *q* = (*n* – *r*) /*m* and 1 ≤ *r* < *m*,  This last inequality along with Relation 10.9 establishes Bound 10.10. Owing to this bound, the total number of bit manipulations needed to compute all remainders in all recursive calls is bounded above by  Relation 10.8 implies the number of recursive calls is bounded above by *dt*, where *d* is a constant greater than 0. This means the number of terms in Bound 10.11 is bounded above by *dt*. Therefore, since *n* > *m* > *r* > *m* mod *r* > … (where the dots denote the remaining terms in Bound 10.11), we conclude from Bound 10.11 that  **** ### 10.2.2 An Extension to Euclid's Algorithm [Theorem 10.1](LiB0081.html#1002) entails that there are integers *i* and *j* such that  Knowledge of these integers will be important to our algorithm for solving modular linear equations in the next section. Next we modify [Algorithm 10.1](#ch10ex26) to also produce these integers. In this version we make gcd a variable because so doing makes the proof of the correctness of the algorithm more transparent. Algorithm 10.2 Euclid's Algorithm 2****Problem: Compute the greatest common divisor of a positive integer and a nonnegative integer. **** Inputs: a positive integer *n* and a nonnegative integer *m*. Outputs: the greatest common divisor *gcd* of *n* and *m*, and integers *i* and *j* such that *gcd*=*in* + *jm*. ``` void Euclid (int n, int m, int& gcd, int& i, int& j) { if (m == 0) { gcd = n; i = 1; j = 0; } else { int i', j', gcd'; Euclid (m, n mod m, gcd', i', j'); // The C++ code would be n% m gcd = gcd’; i = j’; j = i'–[n/m] j'; } } ``` [Algorithm 10.2](#ch10ex30) clearly has the same time complexity as [Algorithm 10.1](#ch10ex26). So we need only prove it is correct. Before doing this, we show an example of applying it. Example 10.18****[Table 10.1](#ch10table01) illustrates the flow of [Algorithm 10.2](#ch10ex30) when the top-level call is ****  The values returned at the top level are *gcd* = 6, *i* = –2, and *j* = 3. Next we prove [Algorithm 10.2](#ch10ex30) is correct. Table 10.1: The values determined by [Algorithm 10.2](#ch10ex30) when *n* = 42 and *m* = 30. The top-level call is labeled 0; the three recursive calls are labeled 1–3. The arrows show the order in which the values are determined.Call *n* *m* *gcd* *i* *j* ↓ ↓ 0 42 30 6 –2 3 1 30 12 6 1 –2 2 12 6 6 0 1 3 6 0 6 1 0 → → ↑ ↑ ↑ Theorem 10.9****The values of *i* and *j* returned by [Algorithm 10.2](#ch10ex30) are integers such that ****  Proof: The proof is by induction. Induction base: In the last recursive call *m* = 0, which means the gcd(*n*, *m*) = *n*. Since the values of *i* and *j* are assigned values 1 and 0, respectively, in that call, we have that  Induction hypothesis: Assume in the *k*th recursive call the values determined for *i* and *j* are such that  Then the values returned by that call for *i’* and *j’* \[to the (*k* – 1)st recursive call\] are values such that  Induction step: We have for the (*k* – 1)st call that *in* + *mj* = *j’n* + (*i’* – \[*n*/*m*\] *j’*) *m* =*i’m* + *j’* (*n* – \[*n*/*m*\] *m*) =*i’m* + *j’n* mod *m* =gcd(*m*, *n* mod *m*) = gcd(*n*, *m*). The second to the last equality is due to the induction hypothesis, and the last equality is owing to [Theorem 10.3](LiB0081.html#1010). Notice that the value [Algorithm 10.2](#ch10ex30) returns for *j* in the final recursive call can be any integer. We choose 0 for simplicity. Choosing a different integer yields a different (*i*, *j*) pair with the gcd(*n*, *m*) = *in* + *jm*.