Extended Euclid's Algorithm : If d divides a and b and d = a*x + b*y for integers x and y, then d = gcd(a,b) >>> extended_gcd(10, 6) (2, -1, 2) >>> extended_gcd(7, 5) (1, -2, 3)
(a: int, b: int)
| 72 | |
| 73 | |
| 74 | def extended_gcd(a: int, b: int) -> tuple[int, int, int]: |
| 75 | """ |
| 76 | Extended Euclid's Algorithm : If d divides a and b and d = a*x + b*y for integers |
| 77 | x and y, then d = gcd(a,b) |
| 78 | |
| 79 | >>> extended_gcd(10, 6) |
| 80 | (2, -1, 2) |
| 81 | |
| 82 | >>> extended_gcd(7, 5) |
| 83 | (1, -2, 3) |
| 84 | |
| 85 | """ |
| 86 | assert a >= 0 |
| 87 | assert b >= 0 |
| 88 | |
| 89 | if b == 0: |
| 90 | d, x, y = a, 1, 0 |
| 91 | else: |
| 92 | (d, p, q) = extended_gcd(b, a % b) |
| 93 | x = q |
| 94 | y = p - q * (a // b) |
| 95 | |
| 96 | assert a % d == 0 |
| 97 | assert b % d == 0 |
| 98 | assert d == a * x + b * y |
| 99 | |
| 100 | return (d, x, y) |
| 101 | |
| 102 | |
| 103 | if __name__ == "__main__": |