# Math Help - Greastest Common Divisor

1. ## Greastest Common Divisor

there is a theorem said if the greatest common divisor of a and b equal d then there exist x,y integers such that.

$ax+by = d$

My book say use Euclidean algorithm backward, how I can use Euclidean algorithm to prove it.

Thanks

2. Can you give a specific example?

3. Originally Posted by Amer
there is a theorem said if the greatest common divisor of a and b equal d then there exist x,y integers such that.

$ax+by = d$

My book say use Euclidean algorithm backward, how I can use Euclidean algorithm to prove it.

Thanks
If you use Euclidean Algorithm, then you have to do messy backsubstitution steps. It is more direct to use the Extended Euclidean Algorithm, see Extended Euclidean algorithm - Wikipedia, the free encyclopedia

4. Originally Posted by Amer
there is a theorem said if the greatest common divisor of a and b equal d then there exist x,y integers such that.

$ax+by = d$

My book say use Euclidean algorithm backward, how I can use Euclidean algorithm to prove it.

Thanks

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

5. 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
I know all that but what I want is the proof of this theorem not example, anyway thanks

6. Originally Posted by Amer
I know all that but what I want is the proof of this theorem not example, anyway thanks

This is what you wrote in your first messaage:

"there is a theorem said if the greatest common divisor of a and b equal d then there exist x,y integers such that.

My book say use Euclidean algorithm backward, how I can use Euclidean algorithm to prove it.