Extended Eucledian Algorithm

The Extended Euclidean Algorithm is an essential algorithm in number theory. For given integers $a$ and $b$, the extended Euclidean algorithm not only calculate the greatest common divisor $d$ but also two additional integers $x$ and $y$ that satisfy the following equation.

$$ax + by =d= gcd(a, b)$$

 The existence of such integers is guaranteed by Bézout’s lemma. 

Here’s how it works:

Problem Statement: Given integers $a$ and $b$, find integers $x$ and $y$ such that $ax + by = gcd(a, b)$.

Algorithm Steps:

Start with the GCD of  $a$ and $b$.
Reverse the steps in the Euclidean algorithm to find $x$ and $y$.
Treat the numbers as variables and work our way backward to express the GCD as a linear combination of  $a$ and $b$

Example: 

Given $a = 11$ and $b = 3$.
We start with the GCD:

$$11=3.3 + 2$$

$$3=1.2+1$$

$$2=2.1+0$$

So GCD=gcd(11,3)=1

Now we can reverse the process. Repeatedly replace terms until we get the final result.We have to consider the coefficient of  $a$ and $b$ as variables.

$$1=3- 1.2$$

$$1=3-1.(11-3.3)$$

$$1= (-1) 11+(4).3$$

Thus $x=-1$ and $y=4$

The extended Euclidean algorithm is useful for solving modular equations, finding modular inverses, and cryptographic applications

Example:

Given $a = 30$ and $b = 20$, we want to find integers $x$ and $y$ such that:
$$ax + by = gcd(a, b)$$
Step 1: 

Apply the Euclidean Algorithm and Calculate the GCD of 30 and 20 using the Euclidean algorithm:

$$30 = 1 \cdot 20 + 10$$
$$20 = 2 \cdot 10 + 0$$
The GCD is 10.

Step 2: Work Backward to Find Bézout Coefficients

$$10 = 30 - 1 \cdot 20$$
Substitute the value of 20 from the previous row:

$$10 = 30 - 1 \cdot (30 - 1 \cdot 20)$$
Simplify:

$$10 = 2 \cdot 30 - 1 \cdot 20$$
Now we have the desired expression:

$$10 = 2 \cdot 30 - 1 \cdot 20$$

Result:The Bézout coefficients are $x = 2 $and $y = -1$.
The GCD of 30 and 20 can be expressed as:$10=30 \cdot 2 + 20 \cdot (-1) $

Therefore, in this example, the Extended Euclidean Algorithm gives us the Bézout coefficients and expresses the GCD as a linear combination of 30 and 20.

Note that this process is tedious when we have to perform large number of steps to compute GCD.A better mathematical approach can be used to find $x$ and $y$ as described below.

Now let us show how to extend the Euclidean algorithm to determine $(x,y,d)$ given $a$ and $b$.

We assumed that  $$r_i=ax_i+by_i$$

Therefore $x_i=x_{i-2}-q_ix_{i-1}$ and $y_i=y_{i-2}-q_iy_{i-1}$

Example:

let us use $a=1759$ and $b=550$

The results are shown in Table below.Thus, we have 

1759 × (–111) + 550 × 355 = –195249 + 195250 = 1.

Example:

Find gcd $d$ of $x=525$ and $y=231$ and express $d$ as $ax + by$ where $a$ and $b$ are integers.

 

gcd=21=(4)*525+(-9)*231

Find gcd $d$ of $a:299$ and $b:221$ and express $d$ as $ax +by$ where $x$ and $y$ are integers.

gcd=13=(3)*299+(-4)*221

Python code

def  extendedEuclid(a, b):

    if b == 0:

        return a, 1, 0

    

    gcd, x1, y1 = extendedEuclid(b, a % b)

    x = y1

    y = x1 - (a // b) * y1

    

    return gcd, x, y

gcd,x,y=extendedEuclid(4076,1024)

print(gcd,x,y)