# Extended Euclidean Algorithm

By **Sudheer S**

## Introduction

In this series of articles about number theory and cryptography, we have discussed

- The Euclidean algorithm to compute the GCD for two integers
`a`

and`b`

- The Bezout’s Identity: ax + bc = GCD(a,b)

This article will introduce the reader to the Extended Euclidean algorithm to compute the coefficients of the Bezout’s Identity.

Bézout’s identity states that for any two integers `a`

and `b`

, their greatest common divisor (GCD) can be expressed as:

## GCD(a,b)=ax+by

where `x`

and `y`

are integers known as the coefficients of Bézout’s identity.

The math. TBD.

## Division Algorithm

The division algorithm states that for any two integers `a`

and `b`

(with `b`

non-zero), there exist unique integers `q`

(the quotient) and `r`

(the remainder) such that:

**a=b×q+r**

where:

`a`

is the dividend`b`

is the divisor`q`

is the quotient,`r`

is the remainder, which satisfies 0≤r<∣b|

We can rearrange it to solve for the remainder `r`

:

**r=a−b×q**

This equation tells us that the remainder is what’s left after subtracting the product of the divisor and the quotient from the dividend.

Here’s an implementation of the Euclidean algorithm using the equation `r=a-bxq`

.

```
def gcd_iterative(a, b):
# Initial values
old_r, r = a, b # r represents the remainder
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r
# the expression r = old_r - quotient * r equates to the mathematical expression: r = a - b*q
# old_r amouunts to a and r amounts to b
return old_r
# Example usage:
a = 252
b = 198
gcd = gcd_iterative(a, b)
print(f"GCD of {a} and {b} is {gcd}")
```

In the loop, `old_r`

represents `a`

of the mathemtical equation `r = a - b*q`

. And `r`

represents `b`

. This is the essence of the Euclidean algorithm to compute the GCD.

This program is slightly different than our first version. In this version, we do not use the modulo operator. We explicitly determine the
integer quotient using the expression `old_r // r`

. We will soon make use of the quotient to compute the coefficenets of the Bezout’s identity.

Like I said in the previos post, the best way to thoroughly understand the program is to evaluate the steps using a pen and paper.

## Proof Of The Euclidean Algorithm

As 0 ≤ r_{i+1} < |r_{i}|,
the sequence of the r_{i} is a decreasing sequence of nonnegative integers (from i = 2 on). Thus it must stop with some r_{k+1} = 0.

This proves that the algorithm stops eventually.

Here, the loop index is 0 before the loop starts. At this point, r_{i} = r_{0} = a.
With each loop iteration, the remainder r decreases. With each iteration, the remainder is getting smaller and smaller.

This is denoted by;

r_{i+1} < |r_{i}|

eventually, r becomes 0.

The mathematial notation:

0 ≤ r_{i+1} < |r_{i}|

As r_{i+1} = r_{i-1} - r_{i}q_{i} (By definition of the algorithm)
the greatest common divisor is the same for (r_{i-1}, r_{i}) and (r_{i}, r_{i+1})

The greaterst common divisor of the input a = r_{0}, b = r_{1} is the same as r_{k},r_{k+1}. When the algorithm r_{k+1}=0.
Hence, r_{k} is the greatest common divisor of `a`

and `b`

.

## The Extended Euclidean Algorithm

Building on the Euclidan algorithm, let’s implement the extended Euclidean algorithm to compute the coefficients of the Bezout’s identity.

```
def extended_gcd_iterative(a, b):
print(f"The start of the function a = {a} and b = {b}")
# Initial values
old_r, r = a, b # r represents the remainder
old_x, x = 1, 0 # Coefficients for a
old_y, y = 0, 1 # Coefficients for b
while r != 0:
quotient = old_r // r
old_r, r = r, old_r - quotient * r # the same as in the Eucildean algorithm
old_x, x = x, old_x - quotient * x
# x: This represents the current coefficient for a in the linear combination.
# old_x: This represents the previous coefficient for a from the last iteration.
old_y, y = y, old_y - quotient * y
# old_r is the GCD, and old_x and old_y are the coefficients
return old_r, old_x, old_y
# Example usage:
a = 252
b = 198
gcd, x, y = extended_gcd_iterative(a, b)
print(f"GCD of {a} and {b} is {gcd}")
print(f"Coefficients of Bézout's Identity: x = {x}, y = {y}")
print(f"Bézout's Identity: {gcd} = {x} * {a} + {y} * {b}")
```

### Output Of The Program

```
GCD of 252 and 198 is 18
Coefficients of Bézout's Identity: x = 4, y = -5
Bézout's Identity: 18 = 4 * 252 + -5 * 198
```

### Setting Initial Values:

**old_x and x**:

**old_x = 1**: This represents the initial coefficient for `a`

when we start the algorithm.

**x = 0**: This is the initial coefficient for `b`

.

When the algorithm starts, we haven’t yet performed any operation. The equation `a=1×a+0×b`

clearly holds, which corresponds to old_x = 1 and x = 0.

**old_y and y**:

**old_y = 0**: This represents the initial coefficient for `a`

when we start the algorithm.

**y = 1**: This is the initial coefficient for `b`

.

Similarly, `b=0×a+1×b`

is true initially, which corresponds to `old_y`

= 0 and y = 1.

### Role of x and old_x:

**x**: This represents the current coefficient for`a`

in the linear combination.**old_x**: This represents the previous coefficient for`a`

from the last iteration.

During the execution of the algorithm, we need to update these coefficients to reflect the new linear combination that results from the Euclidean step.

When you apply the division step in the Euclidean algorithm: remainder = old_r − quotient × r

you are essentially saying that the new remainder is a linear combination of `a`

and `b`

, but this combination involves different coefficients than before. To maintain the relationship GCD(a,b)=ax+by throughout the iterations, the coefficients must be updated accordingly.

#### Updating The Coefficient `x`

:

The formula `old_x, x = x, old_x - quotient * x`

updates the coefficient `x`

as follows:

Shift the Current Coefficient:

`old_x`

is set to `x`

.

This effectively shifts the current coefficient for `a`

into the position of the “old” coefficient, preparing it for the next iteration.

Compute the new Coefficient:

`x`

is updated to `old_x - quotient * x`

.

`old_x`

represents the coefficient of `a`

before this iteration.
quotient is the quotient obtained from dividing the current pair of remainders.
`x`

represents the coefficient of `a`

in the current iteration.
The term `quotient * x`

adjusts the coefficient by the number of times the divisor (represented by `r`

) fits into the dividend (represented by `oldr_r`

).
Subtracting this product from `old_x`

gives the correct coefficient for the remainder after the current step.

## Proof Of The Extended Euclidean Algorithm

Continuing from the proof of the Euclidean algorithm, we have:

r_{i+1} = r_{i-1} - r_{i} * q_{i}

Divide the old remainder by the current remainder. This gives us the quotient. Plug the values into the division algorithm equation. We get r_{i+1} = r_{i-1} - r_{i} * q_{i}.

From the Bezout’s identity we have: r = ax + by.

Therefore, r_{i} = ax_{i} + by_{i} and
r_{i-1} = ax_{i-1} + by_{i-1} and
r_{i+1} = ax_{i+1} + by_{i+1} and so on.

Substituting these values in to the equation r_{i+1} = r_{i-1} - r_{i} * q_{i}

= ax_{i-1} + by_{i-1} - (ax_{i}+ by_{i}) * q_{i}

= ax_{i-1} + by_{i-1} - ax_{i}q_{i} - by_{i}q_{i}

= (ax_{i-1} - ax_{i}q_{i}) + (by_{i-1} - by_{i}q_{i})

= ax_{i+1} + by_{i+1}

Therefore x_{k} and t_{k} are the Bezout cofficients. Notice that r_{k+1} = 0. r_{k} is the the GCD, ie the last non zero remainder.

## The Computational Complexity

The computational complexity of the extended Euclidean algorithm is the same as the Euclidean algorithm, ie, `O(log(min(a,b)))`

. We are just performing a couple of extra lines of computation within the same loop. The overhead of calculating the coefficients `x`

and `y`

is minimal. For an explanation of the time complexity of the Euclidean algorithm
please read the prevous article in the series.