Originally Posted by

**tonio** You have to express backwards each residue r_n as a combination of the previous residue r_(n-1) and the quotient q_n.

Example: a = 120, b = 23. We begin the Euclidean algorithm

### 120 = 5*23 + 5 ==> q_1 = 23, r_1 = 5

### 23 = 4*5 + 3 ==> q_2 = 5 = r_1, r_2 = 3

### 5 = 1*3 + 2 ==> q_3 = 3 = r_2 , r_3 = 2

### 3 = 1*2 + 1 ==> q_4 = 2 = r_3 , r_4 = 1

2 = 2*1 ===> q_5 = 2 = r_4, r_5 = 0 ==> the last non-zero residue, namely 1, is the gcd of 120 and 23

Now we go backwards (begin with the one before the last row):

(i) 1 = 3 - 1*2 ==> last non zero residue (i.e., the gcd) r_4 expressed as lin. comb. of quotient q_4 and prior residue r_3

(ii) 2 = 5 - 1*3 ==> residue r_3 as l.c. of quotient q_3 and residue r_2, and now we plug into (i) and get: 1 = 3 - 1*(5 - 1*3) = 2*3 - 5

(iii) 3 = 23 - 4*5 ==> residue r_2 as l.c. of q_2 and r_1, plug in (ii) above:

1 = 2*(23 - 4*5) - 5 = 2*23 - 9*5

(iv) 5 = 120 - 5*23 ==> residue r_1 as l.c. of q_1 and r_0 = 23.

Plug into (iii) above and finally get:

1 = 2*23 - 9*(120 - 5*23) = 47*23 +(-9)*120 and voilá.

Tonio