Ties in Worst-Case Analysis of the Euclidean Algorithm

Brian Hopkins, Aram Tangboonduangjit


We determine all pairs of positive integers below a given bound that require the most division steps in the Euclidean algorithm.  Also, we find asymptotic probabilities for a unique maximal pair or an even number of them.  Our primary tools are continuant polynomials and the Zeckendorf representation using Fibonacci numbers.


Euclidean algorithm; continuant polynomials; Fibonacci numbers

Full Text:


ISSN: 1331-0623 (Print), 1848-8013 (Online)