Introduction to Bézout's identity
The GCD of two integers A, B is the largest positive integer that divides both of them leaving no remainder. Now because of Euclid's property that each integer N can be divided by another integer M as follows:
there exist pairs u,v such that we can write:
Since there is an infinite amount of those pairs, we'd like to find special ones. There are in fact exactly (A,B not being zero) two such pairs that satify
The goal of this challenge is to find the (ordered) pair of coefficients (u,v) that satify the above constraints and where u must be positive. This narrows down the output to a unique pair.
We may assume that the input is positive, also A will always be larger than B (A > B).
The output of our program/function must be the (ordered) pair specified in the challenge.
One must not use built-in extended Euclidean algorithms (e.g. in Mathematica one is allowed to use
GCD but not
ExtendedGCD - which would fail for 5,3 anyways).
The answer may be a full program (taking input via STDIN or similar and output via STDOUT) or a function (returning the pair).
Beside the pair (u,v) there shall not be any output, trailing newlines or spaces are allowed. (brackets or commas are fine)
This is code golf, all standard loopholes are forbidden and the program with the lowest byte count wins.
(A, B) -> (u, v) (42, 12) -> (1, -3) (4096, 84) -> (4, -195) (5, 3) -> (2, -3) (1155, 405) -> (20, -57) (37377, 5204) -> (4365, -31351) (7792, 7743) -> (7585, -7633) (38884, 2737) -> (1707, -24251) (6839, 746) -> (561, -5143) (41908, 7228) -> (1104, -6401) (27998, 6461) -> (3, -13) (23780, 177) -> (20, -2687) (11235813, 112358) -> (8643, -864301)