# Extended euclid question ( )

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

Related Calculus and Beyond Homework Help News on Phys.org
shmoe
Homework Helper
You're very close. Use
Bob19 said:
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.

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

shmoe said:
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.

Last edited:
Fermat
Homework Helper

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 ?