Extended GCD Canonical Coefficients

Problem

Return [g, x, y] where g is gcd(a, b), a * x + b * y = g, and x is the smallest non-negative solution modulo b / g.

Run the iterative extended Euclidean algorithm and reduce the a-coefficient into [0, b / g). Return [0, 0, 0] when both inputs are zero and [g, 1, 0] when b is zero.

Hint

Bezout coefficients are unique only up to multiples of b / g, so normalize into the canonical range.

Test cases

case 1

in: [30,18]

expected: [6,2,-3]

case 2

in: [3,7]

expected: [1,5,-2]

case 3

in: [7,3]

expected: [1,1,-2]

case 4

in: [0,5]

expected: [5,0,1]

case 5

in: [12,8]

expected: [4,1,-1]

Starter codePython

def extended_gcd_canonical(a, b):
    # Your code here
    pass

5 test cases · run your code against them in the editor