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.

\$\displaystyle ax+by = d \$

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

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.

\$\displaystyle 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
• 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.

\$\displaystyle 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
• 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.