Extended GCD
MediumMathRecursion
Description
Given non-negative integers a and b (not both zero), return [g, x, y] where g = gcd(a, b) and a*x + b*y = g. Return the canonical pair produced by the recursive extended Euclidean algorithm.
Examples
Input:
a = 30, b = 12Output:
[6,1,-2]Explanation:
Bezout coefficients for 30 and 12 are 1 and -2, since 30*1 + 12*(-2) = 6 = gcd(30,12).
Input:
a = 7, b = 5Output:
[1,-2,3]Explanation:
For 7 and 5, coefficients (-2, 3) work: 7*(-2) + 5*3 = -14 + 15 = 1 = gcd(7,5).
Input:
a = 10, b = 0Output:
[10,1,0]Explanation:
When b is 0, gcd(a,0) = a with the canonical solution x = 1 and y = 0, giving [10, 1, 0].
Constraints
- •
0 ≤ a, b ≤ 10⁹ - •
Not both zero.