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 euclid question ( )

  1. Oct 12, 2005 #1
    extended euclid question (URGENT!!!!)

    Hi
    Having the following linear combination of the two divisors a = 403 and b = 3263
    403x + 3263y = 26
    gcd(a,b) = 13
    Using the extended euclid I get
    3263 = 8*403 + 39 (1)
    403 = 10 * 39 + 13 (2)
    39 = 13 * 3
    therefore gcd(a,b) = 13
    Then using extended euclid to find x,y
    I rewrite (1) and (2)
    13 = 403 - 10 * 39 (z)
    39 = 3263 - 8*403 (t)
    According to ex.euclid I insert t into z and get the following:
    13 = 403 - 10 * 3263 + 80 * 403

    My question is how do I from this result derive x,y ???

    Sincerley and God bless You all.

    /Bob
     
  2. jcsd
  3. Oct 12, 2005 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    You're very close. Use
    to write 13 as a linear combination of 403 and 3263. Then compare with your desired 403x + 3263y = 26 equation.
     
  4. Oct 12, 2005 #3
    Thank You for Your answer,

    What do You mean ?

    13 = 403 - 10 * 3263 + 80 * 403 can be divided by 13, but how does this allow be to find x,y ??

    /Bob

     
    Last edited: Oct 12, 2005
  5. Oct 12, 2005 #4

    Fermat

    User Avatar
    Homework Helper

    your original eqn is,

    403x + 3263y = 26

    or,

    26 = 403x + 3263y

    and you have,

    13 = 403 - 10 * 3263 + 80 * 403 = 403*81 - 10*3263

    or,

    26 = 403*162 - 3263*20

    Looking at the bolded lines, can you now see what the solutions for x and y are ?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook