The Extended Euclidean Algorithm

The extended Euclidean Algorithm [Rosen, Section 3.6 and Exercise 3.7.48] can be written as follows. If you want to try to algorithm out, you can have a look at this page.

Let a and b be two positive integers. The Extended Euclidean Algorithm finds the greatest common divisor of a and b, gcd(a,b), and also expresses a and b as a linear combination with integer coefficients of the greatest common divisor, i.e., the algorithm finds gcd(a,b), and two integers s and t, such that

First write the following table:

Next, fill out the table by using the following four rules:

• r_i = r_i-2 mod r_i-1.
• q_i = r_i-1 div r_i. This is integer division, e.g., 7 div 3 = 2.
• s_i = s_i-2 - q_i-1 s_i-1.
• t_i = t_i-2 - q_i-1 t_i-1.

You continue to use the rules until you reach an r_n+1 with value zero. Then, the gcd of a and b is r_n, i.e.,

An example of this is the following:

That is: