1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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 ?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Extended euclid question ( )
  1. Euclid's Algorithm (Replies: 5)

  2. Euclid's formula (Replies: 3)

Loading...