◀ ▲ ▶Branches / Theoretical-computer-science / Semi-numerical-algorithms / Proof

Proof

(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.
  ∎

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