# Extended euclidian algorithm problem (HELP )

1. Oct 12, 2005

### 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

2. Oct 12, 2005

### HallsofIvy

Staff Emeritus
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?

Last edited: Oct 12, 2005
3. Oct 12, 2005

### Mathman23

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

4. Oct 12, 2005

### 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.

5. Oct 12, 2005