Let $$a,b\in\mathbb{Z}$$ be positive integers $a,b\in\mathbb Z$ with $$a\le b$$. The algorithm $$\operatorname{gcdext}(a,b)$$ calculates correctly the greatest common divisor $d$ of $$a$$ and $$b$$ and integers $x,y\in\mathbb Z$ $x,y\in\mathbb Z$ such that $$d=ax+by.$$ It requires $$\mathcal O(\log |b|)$$ (worst case and average case) division operations, which corresponds to $$\mathcal O(\log^2 |b|)$$ bit operations.

# Algorithm: Extended Greatest Common Divisor (Python)

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 def gcdext(a, b): if a <= 0: raise TypeError("a <= 0") if b <= 0: raise TypeError("b <= 0") x = 0 y = 1 u = 1 v = 0 q = a // b r = a % b while r != 0: a = b b = r t = u u = x x = t - q * x t = v v = y y = t - q * y if b != 0: q = a // b r = a % b d = b return [d, x, y] # Usage print(gcdext(5159, 4823)) # will output # [7, -244, 261], because 7 = -244*5159 + 261*4823 

Proofs: 1

Proofs: 1
Propositions: 2 3

Thank you to the contributors under CC BY-SA 4.0!

Github:

### References

#### Bibliography

1. Hermann, D.: "Algorithmen Arbeitsbuch", Addison-Wesley Publishing Company, 1992
2. Blömer, J.: "Lecture Notes Algorithmen in der Zahlentheorie", Goethe University Frankfurt, 1997