Sam

Oct 05 2020 at 15:14 GMT

With Euclid's algorithm, we can find the greatest common divisor (GCD) of two integers $a$ and $b$. It can be proven that the GCD is the smallest positive integer linear combination of $a$ and $b$. Thus, we can write the GCD as a linear combination of $a$ and $b$:

$\gcd(a, b) = sa + tb \ \ \ \text { (for some } s,t \text{)}$

The extended Euclidean algorithm allows to find not only the GCD, but also the values of the coefficients $s$ and $t$.

I would like some explanations of how this algorithm works.

Carl

Oct 05 2020 at 17:47 GMT

The idea of the extended Euclidean algorithm is to keep track of how each encountered remainder can be written as a linear combination of $a$ and $b$. This way, once we reach the last non-zero remainder, which corresponds to the GCD, we know how to express it as a linear combination of $a$ and $b$.

Let's find the GCD of 221 and 91 using the extended Euclidean algorithm.

$\gcd(221, 91) = \gcd(91, \text{rem}(221, 91))$

According to the Division theorem, we can write 221 as 91 times the quotient plus the remainder:

$221 = 2 \cdot91 + 39$

Thus, $\text{rem}(221, 91) = 39$.

We can express this first remainder (39) as a linear combination of 221 and 91 by rearranging the terms:

$39 = 221 + (-2)\cdot91$

Let's continue with the algorithm:

$\gcd(91, 39) = \gcd(39, \text{rem}(91, 39))$

By the Division theorem:

$91 = 2 \cdot 39 + 13$

So, $\text{rem}(91, 39) = 13$.

Let's express 13 as a linear combination of 221 and 91:

$\begin{aligned} 13 &= 91 - 2\cdot 39 \\ &= 91 - 2 \cdot (221 - 2 \cdot 91) \\ &= 91 - 2 \cdot 221 + 4 \cdot 91 \\ &= -2 \cdot 221 + 5 \cdot 91 \end{aligned}$

Let's continue:

$\gcd(39, 13) = \gcd(13, \text{rem}(39, 13))$

By the Division theorem:

$39 = 3 \cdot 13 + 0$

Thus, we reached a zero remainder: $\text{rem}(39, 13) = 0$.

$\gcd(13, 0) = 13$

Thus, the GCD of 221 and 91 is 13, and we know how to express 13 as a linear combination of 221 and 91:

$13 = -2 \cdot 221 + 5 \cdot 91$

That is, $s=-2$ and $t=5$ are two possible coefficients in a linear combination of 221 and 91 that makes up the GCD.

Let's now see how to implement a function `extendedGCD`

in C++ that computes both the GCD and the coefficients $s$ and $t$ using the extended Euclidean algorithm.

First we need a way to express the return value of such a function. It consists of 3 items:

- The GCD
- The coefficient $s$ in $sa+tb$
- The coefficient $t$ in $sa + tb$

One way to express this is using a `struct`

that has 3 fields. Since this struct represents the value of a linear combination along with the coefficients $s$ and $t$, let's call it `LinearCombination`

and define it as follows:

```
struct LinearCombination {
int value;
int s;
int t;
};
```

So, the GCD of the previous example would correspond to:

`LinearCombination gcd = {13, -2, 5};`

We now have a way to express the GCD and the coefficients, so the signature of the `extendedGCD`

function will be:

`LinearCombination extendedGCD(int a, int b);`

Let's think about how the `extendedGCD`

function would work.

We start with $x = a$ and $y = b$, which trivially are linear combinations of $a$ and $b$:

$\begin{aligned} a &= a + 0 \cdot b \\ b &= 0 \cdot a + b \end{aligned}$

We compute the remainder using the Division theorem:

$\begin{aligned} x &= qy + r \\ r &= x - qy \end{aligned}$

Since $r$ is equal to the difference between linear combinations of $a$ and $b$, $r$ is also a linear combination of $a$ and $b$.

Next, we recursively compute $\gcd(y,r)$. Thus, $y$ becomes the new $x$ and $r$ becomes the new $y$.

Since $x$ and $y$ are initially linear combinations of $a$ and $b$, and the remainder $r$ that we compute is also a linear combination of $a$ and $b$, it follows that $x$ and $y$ are always linear combinations of $a$ and $b$:

$\begin{aligned} x &= s_x a + t_x b \\ y &= s_y a + t_y b \end{aligned}$

Knowing this, we can determine how to compute the coefficients $s$ and $t$ for the remainder $r$:

$\begin{aligned} r &= x - qy \\ &= (s_x a + t_x b) - q(s_y a + t_y b) \\ &= s_x a + t_x b - qs_y a - qt_y b \\ &= (s_x - qs_y)a + (t_x - qt_y)b \end{aligned}$

Thus, the coefficients for the remainder $r$ are $s = s_x - qs_y$ and $t = t_x - qt_y$.

We keep doing this until we reach a zero-remainder, that is, until $y$ becomes 0. When that happens, we simply return $x$, which is the last non-zero remainder, and thus it corresponds to the GCD.

Let's look at the implementation:

```
struct LinearCombination {
int value; // the value of sa + tb
int s; // the coefficient s in sa + tb
int t; // the coefficient t in sa + tb
};
LinearCombination extendedGCDRec(LinearCombination x, LinearCombination y) {
if (y.value == 0) {
return x;
}
int q = x.value / y.value;
int s = x.s - q * y.s;
int t = x.t - q * y.t;
LinearCombination r = {x.value - q * y.value, s, t};
return extendedGCDRec(y, r);
}
LinearCombination extendedGCD(int a, int b) {
if (a == 0 && b == 0) {
return LinearCombination({-1, 0, 0});
}
if (a == 0) {
return LinearCombination({b, 0, 1});
}
LinearCombination x = {a, 1, 0};
LinearCombination y = {b, 0, 1};
return extendedGCDRec(x, y);
}
```

In `extendedGCD`

, we first check whether both `a`

and `b`

are zero. If that's the case, the GCD is undefined, so we return a linear combination with the sentinel value `-1`

to indicate that.

Then, we check whether `a`

is zero. If that's the case, the GCD is simply `b`

with `s = 0`

and `t = 1`

.

Otherwise, we express the initial values of `x`

and `y`

as a linear combinations of `a`

and `b`

, and call `extendedGCDRec`

, which is the recursive function that does all the work.

In `extendedGCDRec`

, we check if `y`

is zero. If that's the case, we found the GCD, which is `x`

.

Otherwise, we compute the remainder and its coefficients `s`

and `t`

.

Then, we call the function recursively with `y`

becoming the new `x`

and `r`

becoming the new `y`

.

We keep doing this until we reach a zero-remainder, in which case the condition `y == 0`

will be true and we return the last non-zero remainder `x`

.