Section 007) Extended Euclidean algorithm

Introduction

The Extended Euclidean algorithm is an extension to the Euclidean algorithm and computes, in addition to the greatest  common divisor of integers a and b, also the coefficients of Bezout's identity  which are integers x and y such that

ax + by = gcd(a,b).

The gcd of and b is mentioned in https://kali-mathlessions.blogspot.com/2016/09/section-002-gcd.html


In case of Euclidean algorithm we are interested in only the remainder and not the quotients. Because we are interested in only the value of gcd(a,b) and not the quotients a and b, But in  Extended Euclidean algorithm as we are interested in a and b so we need to keep the quotients and these quotients are used to compute the a and b. This is illustrated as below for the same example for which we had computed the gcd in the gcd chapter.

In both cases we proceed by succession of divisions.

Outline of solution

We provide the outline of the solution here

Llet $r_0 = a$ and $r_1=b$ and we have values computed upto $r_n$ then we compute
$r_{n+1} = r_{n-1} - m_{n+1}  * r_n\cdots(1)$ and
We repeat the steps until we get  $r_{n+1} = 0$
Then $r_n$ is the gcd
Then we repeat using (1) and replacing $r_i$  by combination of $r_{i-1}$ and $r_{i-2}$ for i for i going From n down to 3. and thus we get the result

We wind it by providing an example

Problem 1 

Compute a ,b for GCD(1001,104)

Solution 1

 We have

1001 = 104*9 + 65 so $65 = 1001 - 104 *9 \cdots (1)$ 

104 = 65*1 + 39 so $39 = 104 -65 \cdots (2)$ 
 65 = 39*1 + 26  so $26 = 65 - 39 \cdots (3)$ 
 39 = 26*1 + 13 so  so $13 = 39 - 26 \cdots (4)$ 
 26 = 13*2 + 0

As the remainder is zero so we have the GCD 13.

Now $13 = 39-26$  (using (4))

$= 39 - (65-39)$ (using (3))

$= 2 * 39 - 65$

$= 2 * (104-65) - 65 $ (using (2))

$= 2 * 104 - 3 * 65$

$= 2 * 104 - 3 * (1001 - 104 *9)$ using (1)

$= 29 * 104 - 3 * 1001$

$= 1001 * (-3) + 104 * 29 $   (to put in form of ax + by)

So we get $GCD(1001,104)=13= -3 * 1001 + 29 * 1001$

So  we have for a = 1001 and b = 104 the value of gcd(a,b) = 13, x = -3 and y = 29