On Euclid's algorithm and elementary number theory

DOI10.1016/J.SCICO.2010.05.006MaRDI QIDQ627201zbMATH OpenOpenAlexFDO

Authors João F. Ferreira, Roland C. Backhouse

Publication date 21 February 2011

Published in Science of Computer Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.05981

zbMATH Keywords

invariantrational numbergreatest common divisorStern-Brocot treeenumeration algorithmalgorithm derivationcalculational methodEisenstein arrayEisenstein-Stern tree (aka Calkin-Wilf tree)Euclid's algorithm

Mathematics Subject Classification ID

Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Number-theoretic algorithms; complexity (11Y16)

Abstract: Algorithms can be used to prove and to discover new theorems. This paper shows how algorithmic skills in general, and the notion of invariance in particular, can be used to derive many results from Euclid's algorithm. We illustrate how to use the algorithm as a verification interface (i.e., how to verify theorems) and as a construction interface (i.e., how to investigate and derive new theorems). The theorems that we verify are well-known and most of them are included in standard number theory books. The new results concern distributivity properties of the greatest common divisor and a new algorithm for efficiently enumerating the positive rationals in two different ways. One way is known and is due to Moshe Newman. The second is new and corresponds to a deforestation of the Stern-Brocot tree of rationals. We show that both enumerations stem from the same simple algorithm. In this way, we construct a Stern-Brocot enumeration algorithm with the same time and space complexity as Newman's algorithm. A short review of the original papers by Stern and Brocot is also included.

Recommendations

• The Euclidean algorithm in algebraic number fields
• On Euclidean algorithm
• Euclid's Algorithm and the Least-Remainder Algorithm
• The Euclidean algorithm for number fields and primitive roots
• On Euclid's Algorithm in Cyclic Fields
• scientific article; zbMATH DE number 4002217
• On Radix Representation and the Euclidean Algorithm

Cites work

• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 2001186 (Why is no real title available?)
• scientific article; zbMATH DE number 789390 (Why is no real title available?)
• scientific article; zbMATH DE number 3248033 (Why is no real title available?)
• scientific article; zbMATH DE number 2241930 (Why is no real title available?)
• FUNCTIONAL PEARL: Enumerating the rationals
• Guarded commands, nondeterminacy and formal derivation of programs
• On Euclid's algorithm and elementary number theory
• On the shape of mathematical arguments
• Recounting the Rationals
• Recounting the Rationals: Twice!
• The On-Line Encyclopedia of Integer Sequences

Cited in

(10)

• Complex mode-locking oscillations and Stern-Brocot derivation tree in a CSTR reaction with impulsive perturbations
• The analysis of mode-locking topology in an SIR epidemic dynamics model with impulsive vaccination control: infinite cascade of Stern-Brocot sum trees
• Recounting the Rationals: Twice!
• Cluster duality between Calkin-Wilf tree and Stern-Brocot tree
• Designing an algorithmic proof of the two-squares theorem
• A calculational approach to path-based properties of the Eisenstein-Stern and Stern-Brocot trees via matrix algebra
• On Euclid's algorithm and elementary number theory
• On Radix Representation and the Euclidean Algorithm
• Dancing elves and a flower’s view of euclid’s algorithm
• Euclid's algorithm as a computational tool in the mathematics of antiquity.

Describes a project that uses

Uses Software

• CalcCheck
• OEIS

This page was built for publication: On Euclid's algorithm and elementary number theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q627201)