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