### Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 297-324 |

Number of pages | 28 |

Journal | Foundations of Computational Mathematics |

Volume | 3 |

Issue number | 3 |

DOIs | |

State | Published - Dec 1 2003 |

### Fingerprint

### ASJC Scopus subject areas

- Analysis
- Computational Mathematics
- Computational Theory and Mathematics
- Applied Mathematics

### Cite this

**Generating the greatest common divisor, and limitations of primitive recursive algorithms.** / van den Dries, Lou.

Research output: Contribution to journal › Article

}

TY - JOUR

T1 - Generating the greatest common divisor, and limitations of primitive recursive algorithms

AU - van den Dries, Lou

PY - 2003/12/1

Y1 - 2003/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=21144456492&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21144456492&partnerID=8YFLogxK

U2 - 10.1007/s10208-002-0061-y

DO - 10.1007/s10208-002-0061-y

M3 - Article

AN - SCOPUS:21144456492

VL - 3

SP - 297

EP - 324

JO - Foundations of Computational Mathematics

JF - Foundations of Computational Mathematics

SN - 1615-3375

IS - 3

ER -