Let \(a,b\in\mathbb{Z}\) and \(a\le b\). The algorithm \(\gcd(a,b)\) calculates correctly the greatest common divisor of \(a\) and \(b\) and requires \(\mathcal O(\log |b|)\) (worst case and average case) division operations, which corresponds to \(\mathcal O(\log^2 |b|)\) bit operations.

Algorithm: Greatest Common Divisor (Python)

def gcd(a, b): a = abs(a) b = abs(b) r = b while r > 0: r = a % b a = b b = r d=a return d


print(gcd(5159, 4823))

  1. will output
  2. will output

Proofs: 1

Proofs: 1 2
Propositions: 3

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




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