 |
[email protected] |
 |
3275638434 |
 |
 |
| Paper Publishing WeChat |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
A Note on the Euclidean Algorithm
Shiva Soleimany Dizicheh and Kiavash Bagheri
Full-Text PDF
XML 7754 Views
DOI:10.17265/2159-5291/2018.06.003
1. Department of Software Engineering, University of Isfahan, Isfahan 841568311, Iran 2. Department of Industrial Engineering, Islamic Azad University West Tehran Branch, Tehran 44220857, Iran
The problem of determining the number of steps needed to find the greatest common divisor of two positive integers by Euclidean algorithm has been investigated in elementary number theory for decades. Different upper bounds have been found for this problem. Here, we provide a sharp upper bound for a function which has a direct relation to the numbers whom the greatest common divisor we are trying to calculate. We mainly use some features of Fibonacci numbers as our tools.
Euclidean algorithm, fibonacci numbers.
Dizicheh, S. S, and Bagheri, K. 2018. "A Note on the Euclidean Algorithm." Journal of Mathematics and System Science 8 (2018) 175-6.
[1] Niven, I., Zuckerman, H. S., and Montgomery, H. L. 1991. An Introduction to the Theory of Numbers (5th Edition). New York: John Wiley & Sons, Inc.
[2] Weisstein, E. 1999. CRC Concise Encyclopedia of Mathematics by Computation of the Values Mathematics. Boca Raton, FL: CRC Press.