It is often useful to have a solution with u > 0. Modify your program so that it returns a solution with u > 0 and u as small as possible. [Hint. If (u, v) is a solution, then so is (u + b/g, v a/g).]

Pairs to test:

(31313,143)

(1333337, 7331)

(8675309, 1337)

See the screenshot for the program.

def gcd_eea(a,b): u = 1 y = b x = 0 while (y != %): q = floor(g/y) t = int(mod(8,y)) S = u - q*x u = X g = y X = 5 y = t v = (g - a*u)/b return (g,u,v) def gcd_eea(a,b): u = 1 y = b x = 0 while (y != %): q = floor(g/y) t = int(mod(8,y)) S = u - q*x u = X g = y X = 5 y = t v = (g - a*u)/b return (g,u,v)