|
| 1 | +<!--?title The Euclidean algorithm for finding GCD (greatest common divisor) --> |
| 2 | + |
| 3 | +# The Euclidean algorithm for finding GCD (greatest common divisor) |
| 4 | + |
| 5 | +Euclid's algorithm solves the following problem: Given two non-negative integers $a$ and $b$, we require the greater common divisor i.e. the largest number which is a divisor of $a$ and $b$ simultaneously. It's commonly denoted by $gcd$. |
| 6 | + |
| 7 | +$$ |
| 8 | +gcd(a, b) = \max_ {k = 1, \ldots \infty \ : \ k \mid a \ \& \ k \mid b} k |
| 9 | +$$ |
| 10 | + |
| 11 | +(here the symbol "$\mid$" denotes divisibility, i.e. “$k\mid a$” means “$k$ divides $a$”) |
| 12 | + |
| 13 | +When one of the numbers is zero, while the other is non zero, the greatest common divisor, by definition, is the second number. However, when both these numbers are zero, it is undefined(it can be an infinitely large number), but we can take it to be equal to zero. So we have a simple rule: if one of the numbers is zero, the other number is the gcd. |
| 14 | + |
| 15 | +The Euclidean algorithm, discussed below, solves the problem of finding the greatest common divisor of two numbers $a$ and $b$ in $O(\log min(a, b))$. |
| 16 | + |
| 17 | +The algorithm was first described in Euclid's “**Elements**” (circa 300 BC). However, it is possible that the algorithm has earlier origins. |
| 18 | + |
| 19 | +## Algorithm |
| 20 | + |
| 21 | +The algorithm is extremely simple and described by this formula: |
| 22 | + |
| 23 | +$$ gcd(a, b) = \cases{a,&if $b = 0$\cr gcd(b, a \mod b),&otherwise \cr}$$ |
| 24 | + |
| 25 | +## Implementation |
| 26 | + |
| 27 | +```cpp |
| 28 | +int gcd (int a, int b) { |
| 29 | + if (b == 0) |
| 30 | + return a; |
| 31 | + else |
| 32 | + return gcd (b, a % b); |
| 33 | +} |
| 34 | +``` |
| 35 | +
|
| 36 | +Using the ternary operator in C++, we can write a shorter implementation: |
| 37 | +
|
| 38 | +```cpp |
| 39 | +int gcd (int a, int b) { |
| 40 | + return b ? gcd (b, a % b) : a; |
| 41 | +} |
| 42 | +``` |
| 43 | + |
| 44 | +Finally, we present a non-recursive form of implementation of the algorithm: |
| 45 | + |
| 46 | +```cpp |
| 47 | +int gcd (int a, int b) { |
| 48 | + while (b) { |
| 49 | + a %= b; |
| 50 | + swap(a, b); |
| 51 | + } |
| 52 | + return a; |
| 53 | +} |
| 54 | +``` |
| 55 | +
|
| 56 | +## The Proof of correctness |
| 57 | +
|
| 58 | +First, observe that at each successive iteration of the Euclidean algorithm, it's second argument strictly decreases, therefore, since the arguments are always non-negative, the algorithm must terminate. |
| 59 | +
|
| 60 | +For the proof of correctness, we need to show $gcd(a, b) = gcd(b, a \mod b)$ for all $a \geq 0$, $b > 0$. |
| 61 | +
|
| 62 | +We will show that the quantity on the left side of the equation, divides the quantity on it's right. Obviously, this would mean that the left and right sides are equal and prove Euclid's algorithm. |
| 63 | +
|
| 64 | +Let $d = gcd(a, b)$. Then, by definition $d\mid a$ and $d\mid b$. |
| 65 | +
|
| 66 | +New writing the remainder on dividing $a$ by $b$: |
| 67 | +
|
| 68 | +$$ |
| 69 | +a \mod b = a - b \cdot \Bigl\lfloor\dfrac{a}{b}\Bigr\rfloor\qquad |
| 70 | +$$ |
| 71 | +
|
| 72 | +But then, it follows: |
| 73 | +
|
| 74 | +$$ |
| 75 | +d \mid (a \mod b) |
| 76 | +$$ |
| 77 | +
|
| 78 | +So, remembering the statement $d \mid b$, we obtain the system: |
| 79 | +
|
| 80 | +$$ |
| 81 | +\cases{d \mid b,\cr d \mid (a \mod b)\cr} |
| 82 | +$$ |
| 83 | +
|
| 84 | +We now use the fact that if for any three numbers $p$, $q$, and $r$, if $p\mid q$ and $p\mid r$ then $p\mid gcd(q, r)$, In our case, we get: |
| 85 | +
|
| 86 | +$$ |
| 87 | +d \mid gcd(b, a \mod b) |
| 88 | +$$ |
| 89 | +
|
| 90 | +Or, by substituting $d$ by it's definition($gcd(a, b)$) we get: |
| 91 | +
|
| 92 | +$$ |
| 93 | +gcd(a, b) \mid gcd(b, a \mod b) |
| 94 | +$$ |
| 95 | +
|
| 96 | +So, we have shown that the left side divides the right. The second half of the proof is similar. |
| 97 | +
|
| 98 | +## Time complexity |
| 99 | +
|
| 100 | +The running time of the algorithm is estimated by Lame's theorem, which establishes a surprising connection between the euclidean algorithm and the Fibonacci sequence: |
| 101 | +
|
| 102 | +If $a > b \geq 1$ and $b < F_n$ for some $n$, the euclidean algorithm performs no more than $n-2$ recursive calls. |
| 103 | +
|
| 104 | +Moreover, one can show that the upper bound of this theorem is optimal. When $a = F_n$ and $b = F_{n-1}$, $gcd(a, b)$ performs $n-2$ recursive calls. In other words, consecutive fibonacci numbers are the worst case input for Euclid's algorithm. |
| 105 | +
|
| 106 | +Given that Fibonacci numbers grow exponentially(as a constant with respect to $n$), we find that the Euclidean algorithm is performed in $O(\log min(a, b))$ |
| 107 | +
|
| 108 | +## LCM(Least common multiple) |
| 109 | +
|
| 110 | +Calculating least common multiple (least common multiplier or LCM) is reduced to calculating $gcd$ with the following simple statement: |
| 111 | +
|
| 112 | +$$ |
| 113 | +lcm(a, b) = \dfrac{a \cdot b}{gcd(a, b)} |
| 114 | +$$ |
| 115 | +
|
| 116 | +Thus, the calculation of the LCM can also be done using the euclidean algorithm with the same time complexity |
| 117 | +
|
| 118 | +```cpp |
| 119 | +int lcm (int a, int b) { |
| 120 | + return a / gcd (a, b) * b; |
| 121 | +} |
| 122 | +``` |
| 123 | +(here it is advantageous to first divide $gcd$ and then multiply by $b$, as it helps avoid overflow in some cases) |
| 124 | + |
| 125 | +## Literature |
| 126 | + |
| 127 | +- Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Algorithms: Construction and analysis [2005] |
| 128 | + |
| 129 | +## Practice Problems |
| 130 | + |
| 131 | +- [GCD and LCM[easy]](https://www.codechef.com/problems/FLOW016) |
0 commit comments