Bézout's Identity

Haskell, 51 bytes

a#b=[(u,-v)|v<-[1..],u<-[1..v],gcd a b==u*a-v*b]!!0

Usage example: 27998 # 6461 -> (3,-13).

This is a brute force approach which finds all combinations of u and v that are valid solutions ordered by u and picks the first one. This takes some time to run for large |v|.


Python 3, 101 106 bytes

Edit: Added some improvements and corrections suggested by Bruce_Forte.

An answer that uses the extended Euclidean algorithm. It's a bit clunky in places though, and I hope to golf it some more. I could convert to Python 2 to save a byte on integer division (//) but I'm not sure how Python 2's % modulus operator works with a negative second argument, as that is crucial for getting the output right.

def e(a,b):
 r=b;x=a;s=z=0;t=y=1
 while r:q=x/r;x,r=r,x%r;y,s=s,y-q*s;z,t=t,z-q*t
 return y%(b/x),z%(-a/x)

Ungolfed:

def e(a, b):
    r = b
    x = a    # becomes gcd(a, b)
    s = 0
    y = 1    # the coefficient of a
    t = 1
    z = 0    # the coefficient of b
    while r:
        q = x / r
        x, r = r, x % r
        y, s = s, y - q * s
        z, t = t, z - q * t
    return y % (b / x), z % (-a / x) # modulus in this way so that y is positive and z is negative