Extended Euclidean Algorithm

Problem

Return the triple [g, x, y] such that g is the greatest common divisor of a and b and a*x + b*y = g.

Use the recursive identity egcd(a, b) = egcd(b, a mod b) with base case egcd(a, 0) = [a, 1, 0], then back-substitute the coefficients. The coefficients returned by this implementation are deterministic.

Hint

After the recursive call returns coefficients for (b, a mod b), swap them and subtract the quotient times the second.

Test cases

case 1

in: [30,18]

expected: [6,-1,2]

case 2

in: [3,7]

expected: [1,-2,1]

case 3

in: [0,5]

expected: [5,0,1]

case 4

in: [0,0]

expected: [0,1,0]

case 5

in: [12,8]

expected: [4,1,-1]

Starter codePython

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

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