zbMATH — the first resource for mathematics

Generating the greatest common divisor, and limitations of primitive recursive algorithms. (English) Zbl 1019.03027
Summary: The greatest common divisor of two integers cannot be generated in a uniformly bounded number of steps from those integers using arithmetic operations. The proof uses an elementary model-theoretic construction that enables us to focus on “integers with transcendental ratio”. This unboundedness result is part of the solution of a problem posed by Y. Moschovakis on limitations of primitive recursive algorithms for computing the greatest common divisor function.

03C98 Applications of model theory
11A05 Multiplicative structure; Euclidean algorithm; greatest common divisors
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
03D15 Complexity of computation (including implicit computational complexity)
11Y16 Number-theoretic algorithms; complexity
Full Text: DOI