On the tree of the General Euclidean Algorithm

Vlasis Mantzoukas
Notes on Number Theory and Discrete Mathematics, ISSN 1310–5132
Volume 20, 2014, Number 3, Pages 64–84
Full paper (PDF, 143 Kb)

Details

Authors and affiliations

Vlasis Mantzoukas
Department of Mathematics,
University of Athens, Greece

Abstract

The General Euclidean Algorithm (GEA) is the natural generalization of the Euclidean Algorithm (EA) and equivalent to Semi Regular Continued Fractions (SRCF). In this paper, we consider the finite case with entries in GEA natural numbers. Consider the Euclidean Division. In GEA we want the divider to be bigger than the absolute value of the remainder. Thus, we take two divisions except for the case the remainder is zero. However, for our help, we consider the non Euclidean remainder without the negative sign so as not to take the absolute value of it for the next step of the algorithm as we need to have two positive integers. So, it occurs a binary tree except for the before last vertex of its path which gives one division as the remainder is zero. This paper presents mainly a criterion with which we can find all the shortest paths of this tree and not only the one that Valhen–Kronecker’s criterion [3] gives. In terms of SRCF, this criterion gives all the SRCF expansions of a rational number t with the same length as the Nearest Integer Continued Fraction (NICF) expansion of t. This criterion, as we shall see, is related to the golden ration. Afterwards, it is presented a theorem which connects the Fibonacci sequence with the difference between the longest and the shortest path of this tree, a theorem which connects the Fibonacci sequence with the longest path of this tree and a different proof of a theorem which occurs by [1] and [3] which connects the Pell numbers with the shortest path of the aforementioned tree. After that, it is proven a connection of this tree to the harmonic and the geometric mean and in particular two new criteria of finding a shortest path are constructed based on this two means. In the final chapter, it is an algorithm, which has an “opposite” property of the EA, property which has been proven in [2] and has to do with the number of steps Least Remainder Algorithm (LRA) needs to be finished in relation to EA and the signs of the remainders of LRA path.

Keywords

• Euclidean algorithm
• Euclidean tree
• Valhen–Kroneckers theorem

AMS Classification

• 11A05

References

1. Dupré, A. Sur le nombre de divisions à effectuer pour obtenir le plus grand commun diviseur entre deux nombres entiers. Journal de Mathématiques Pures et Appliquées, Vol. 11, 1846, 41–64.
2. Goodman, A. W., W. M. Zaring. Euclid’s Algorithm and the Least Remainder Algorithm. The American Math. Monthly, Vol. 59, 1952, 156–159.
3. Heaslet, J. V., M. A. Uspensky. Elementary Number Theory. Mc-Graw Hill, New York, 1939, 45–51.