# Greastest Common Divisor

• Oct 8th 2009, 06:16 AM
Amer
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.

I tried to solve it many times but always I fail, please help.

Thanks
• Oct 8th 2009, 01:32 PM
ezong
Can you give a specific example?
• Oct 8th 2009, 01:46 PM
kobulingam
Quote:

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.

I tried to solve it many times but always I fail, please help.

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
• Oct 8th 2009, 03:58 PM
tonio
Quote:

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.

I tried to solve it many times but always I fail, please help.

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
• Oct 9th 2009, 12:25 AM
Amer
Quote:

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
• Oct 9th 2009, 01:24 AM
tonio
Quote:

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.

http://www.mathhelpforum.com/math-he...198bc558-1.gif

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

I tried to solve it many times but always I fail, please help.

Thanks "

The above says nothing about proving anything, and you even tell us that you don't know how to do it.
This is what I showed you: how to do it, by means of an example, because this is what you asked.
The proof why it works is a straightforward, and pretty easy, induction on the number of steps required to reach the gcd. Since you "know all that" it must be crystal clear how to work out the induction

Tonio