The subtractive Euclidean algorithm and Fibonacci numbers (Q2746559)

Let \(m,n\) be positive integers with \(m>n\). Replacement of \((m,n)\) by \((m-n,n)\) or \((n,m-n)\) leads after \(K\) steps to \((1,0)\). Each pair is given by premultiplication of its successor by one of the matrices \(A\binom {1\;1}{0\;1}\) or \(B\binom {1\;1}{1\;0}\). Powers of \(B\) have Fibonacci numbers as elements. By considering the possible sequences of \(A\)'s and \(B\)'s, the author obtains the known result on the number of pairs of length \(K\), and also obtains the average size of \(m\) for given \(K\). To find the average size of \(K\) for given \(m\) is much harder, as was shown by \textit{D. E. Knuth} and \textit{A. C. Yao} [Proc. Natl. Acad. Sci. USA 72, 4720-4722 (1975; Zbl 0315.10005)].