Extended euclidian algorithm problem (HELP )

[Mathman23]

Extended euclidian algorithm problem (HELP!)

Hi

I have this here example problem:

9x - 65y = 1

I'm suppose to use the extended euclidian algorithm, but it has given me such much trouble.

I get the regular euclidian algorithm, but not the extended one.

Therefore if there is some good soul out there who would be so kind to explain the extended algorithm using this example I would be much greatful :-)

Sincerley and God Bless

Fred

 

[HallsofIvy]

One difficulty I have is that I don't see a problem here! An equation is not a problem. What do you want to do with the equation? Since you mention the (extended) Euclidean algorithm, are you trying to find integer values of x and y that satisfy the equation?

I notice that 9 divides into 65 3 times with a remainder of 2 and that 2 divides into 9 4 times with a remainder of 1.

In other words 9- 4(2)= 1 and 2= 65- 7(9). Does that help?

 

[Mathman23]

Hi and thank you for your answer,

As I wrote in my earlier post I know how to use the standard euclidian algorithm and thereby finding the gcd(a,b).

Having this in my mind is there an recipe that I can follow then I need to find an x,y this satisfies:

ax + by = gcd(a,b)

I know its the extended euclidian algorithm which I need to use. Would You please explain to me step by step, how by using ex.euclid that I'm able to find x,y ?

Best Regards and God Bless

Fred

 

[ComputerGeek]

yes, you solve for the remainders and substitute the solution, collect the terms and solve for the next remainder, then substitute and collect terms, etc.

 

[Mathman23]

Can you please elaborate :-)

Lets say we have 7x - 50y = 1 = gcd(7,50)

How do I go about solving this equation using ex. euclid ?

/Fred

yes, you solve for the remainders and substitute the solution, collect the terms and solve for the next remainder, then substitute and collect terms, etc.