On Euclid's algorithm and elementary number theory

DOI10.1016/J.SCICO.2010.05.006zbMATH Open1246.11187arXiv1506.05981OpenAlexW2145752266MaRDI QIDQ627201FDOQ627201

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

Publication date: 21 February 2011

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

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.

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

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

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)

Cites Work

• The On-Line Encyclopedia of Integer Sequences
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Guarded commands, nondeterminacy and formal derivation of programs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Recounting the Rationals
• FUNCTIONAL PEARL: Enumerating the rationals
• On the shape of mathematical arguments
• Recounting the Rationals: Twice!
• Title not available (Why is that?)
• On Euclid's algorithm and elementary number theory

Cited In (10)

• 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 Radix Representation and the Euclidean Algorithm
• On Euclid's algorithm and elementary number theory
• Complex mode-locking oscillations and Stern–Brocot derivation tree in a CSTR reaction with impulsive perturbations
• Dancing elves and a flower’s view of euclid’s algorithm
• Euclid's algorithm as a computational tool in the mathematics of antiquity.

Uses Software

• OEIS
• CalcCheck

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)