The Euclidean Algorithm and the Extended Euclidean Algorithm

This is the last trick needed to understand the RSA method. The first algorithm is a quick(-ish) method to find the greatest common divisor between two numbers (a and b). The second algorithm also calculates values of x and y that satisfies the following equation:

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

The Euclidean Algorithm:

This is best explained using an example. What is the greatest common divisor between 120 and 16?

1. First calculate 120 mod 16 = 8.
   
2. Then replace 120 with 16, and 16 with the remainder of the last step, 8. 16 mod 8 = 0
   
3. The result of zero signals the end of the algorithm, and the last divisor (8) is the greatest common divisor of 120 and 16.
   

Here's a second example, gcd(150,23):

1. 150 mod 23 = 12
   
2. 23 mod 12 = 11
   
3. 12 mod 11 = 1
   
4. 11 mod 1 = 0
   

So the greatest common divisor is 1. In short, 150 and 23 are coprime to one another.

The Extended Euclidean Algorithm:

The Extended Euclidean Algorithm is, as its name suggests, an extension to this algorithm.
Each stage in the Euclidean Algorithm can be written as an iterative equation:

$r_i = ax_i + by_i$

and the remainders as:

$r_i = r_{i-2} – q_i \cdot r_i$

Or, in words, the remainder value two steps ago (120 on the first example) minus the last quotient (7) times the value one step ago (16).

$r_2 = 120 – 7 \cdot 16$

$r_2 = 8$.

Substituting:

$r_i = (ax_{i-2} + by_{i-2}) – q_{i – 1} \cdot (ax_{i – 1} + by_{i – 1} )$

Our initial values are:

$r_1 = a = a \times 1 + b \times 0$

$r_2 = b = b \times 0 + b \times 1$

$x_1 = 1, y_1 = 0$

$x_2 = 0, y_2 = 1$

And (using the formula for the remainders):

$x_i = x_{i– 2} – q_{i – 1} \cdot x_{i– 1 } $

$y_i = x_{i– 2} – q_{i – 1} \cdot y_{i – 1} $

q	r	x	y
	120	1	0
	16	0	1
7	(120*1 + 16*0) – 7*(120*0 + 16*1) =8	1 – 7*0 = 1	0 – 7*1 = -7
2	(120*0 + 16*1) – 2 *(120*1 + 16* -7) = 0

Taking the second last set of values, 120 * 1 + 16* – 7 = 8.