Can you give a specific example?
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.
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
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
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.
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