(related to Algorithm: Extended Greatest Common Divisor (Python))

- By hypothesis, \(a,b\in\mathbb{Z}\) are positive integers.
- The existence of solutions of an LDE with two variables ensures the existence of a solution.
- In the algorithm, the greatest common divisor (python) algorithm has been extended by auxiliary variables $x,y,u,v$ are used for calculating the coefficients $a,b$ by backward substitution.
- The runtime is the same as in the original algorithm.∎

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