Research ArticleOpen AccessGoogle Scholar indexed
Full Euclidean Algorithm by Means of a Steady Walk
Grupo de Investigación de Análisis Matemático, Instituto de Formación docente Salomé Ureña, Santo Domingo, D.N., República Dominicana
Grupo de Investigación de Análisis Matemático, Instituto de Formación docente Salomé Ureña, Santo Domingo, D.N., República Dominicana
Wake Forest University, Winstom-Salem, NC, USA
- 1 Grupo de Investigación de Análisis Matemático, Instituto de Formación docente Salomé Ureña, Santo Domingo, D.N., República Dominicana
- 2 Grupo de Investigación de Análisis Matemático, Instituto de Formación docente Salomé Ureña, Santo Domingo, D.N., República Dominicana
- 3 Wake Forest University, Winstom-Salem, NC, USA
Copy link · social · email
Abstract
Let x and y be two positive real numbers with x < y . Consider a traveler, on the interval [0, y /2], departing from 0 and taking steps of length equal to x . Every time a step reaches an endpoint of the interval, the traveler rebounds off the endpoint in order to complete the step length. We show that the footprints of the traveler are the output of a full Euclidean algorithm for x and y , whenever y / x is a rational number. In the case that y / x is irrational, the algorithm is, theoretically, not finite; however, it is a new tool for the study of its irrationality.
KeywordsExtended Euclidean AlgorithmGreatest Common DivisorIncommensurable NumbersSteady WalkDiophantine Equation
- Lehmer, D.H. (1938) Euclid’s Algorithm for Large Numbers. The American Mathematical Monthly, 45, 227-233. https://doi.org/10.1080/00029890.1938.11990797
- Durand, A. (1998) Efficient Ways to Implement Elliptic Curve Exponentiation on a Smart Card. International Conference on Smart Card Research and Advanced Applications, Springer, Berlin, 357-365. https://doi.org/10.1007/10721064_33
- Mordell, L.J. (1969) Diophantine Equations. Academic Press, London, New York.
- Childs, L.N. (2009) A Concrete Introduction to Higher Algebra. ch. The Chinese Remainder Theorem. Springer-Verlag, New York, 253-281. https://doi.org/10.1007/978-0-387-74725-5
- Khinchin, A.Y. (1997) Continued Fractions, Russian ed. Dover Publications, New York.
- Lamé, G. (1844) Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendus Acad. Sci., Paris.
- Heiberg, J.L. (2007) Euclid’s Elements. Richard Fitzpatrick, TX, USA.
- Nikolic, M. (1974) The Relation between Eudoxus’ Theory of Proportions and Dedekind’s Theory of Cuts. In: Cohen, R.S., Stachel, J.J. and Wartofsky, M.W., Eds., For Dirk Struik, Springer, Dordrecht, 225-243. https://doi.org/10.1007/978-94-010-2115-9_19
- Knuth, D.E. (2014) Art of Computer Programming, Volume 2: Seminumerical Algorithms. Addison-Wesley Professional, Boston.
- Ramachandran, P. (2006) Use of Extended Euclidean Algorithm in Solving a System of Linear Diophantine Equations with Bounded Variables. In: Hess, F., Pauli, S. and Pohst, M., Eds., Algorithmic Number Theory. ANTS 2006. Lecture Notes in Computer Science, Vol 4076. Springer, Berlin, Heidelberg, 182-192. https://doi.org/10.1007/11792086_14
- Rankin, S. (2013) The Euclidean Algorithm and the Linear Diophantine Equation ax + by = gcd (a,b). The American Mathematical Monthly, 120, 562-564. https://doi.org/10.4169/amer.math.monthly.120.06.562
- Iliev, A. and Kyurkchiev, N. (2018) The Faster Euclidean Algorithm. Collection of Scientific Works from Conference, Pamporovo, Bulgaria, 28-30.
- Niven, I. (1956) Irrational Numbers. (Carus Mathematical Monographs, Series Number 11). John Wiley and Sons, Inc., New York. https://doi.org/10.5948/9781614440116