How Do I Derive Values of x and y Using Extended Euclid's Algorithm?

[Bob19]

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

 

[shmoe]

You're very close. Use

13 = 403 - 10 * 3263 + 80 * 403

to write 13 as a linear combination of 403 and 3263. Then compare with your desired 403x + 3263y = 26 equation.

 

[Bob19]

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

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.

 

[Fermat]

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 ?