Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Extended euclidian algorithm problem (HELP )

  1. Oct 12, 2005 #1
    Extended euclidian algorithm problem (HELP!!!)


    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

  2. jcsd
  3. Oct 12, 2005 #2


    User Avatar
    Science Advisor

    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 by a moderator: Oct 12, 2005
  4. Oct 12, 2005 #3
    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

  5. Oct 12, 2005 #4
    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.
  6. Oct 12, 2005 #5
    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 ?


Share this great discussion with others via Reddit, Google+, Twitter, or Facebook