Ties in Worst-Case Analysis of the Euclidean Algorithm

Abstract

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.