[数论] 辗转相除法的步数上限

zhcosin

辗转相除法是用来求两个（正）整数的最大公因数的，给定两个正整数$a$和$b$，设$a>b$，那么按带余除法，有$a=qb+r$，其中$q$和$r$都是整数并且$0 \leqslant r < b$，分别称为$a$除以$b$所得的商和余数，如果$r \neq 0$，则再拿$b$除以$r$得余数$r_1$，如果$r_1$仍然不为零，则继续拿$r$除以$r_1$得余数$r_2$，依次下去，由于每做一次除法，所得余数必定减少一，所以这个过程必定在有限步之内结束，即进行到某一步后必然有$r_n=0$，显然这个步数不会超过$b$，所以问题就来了，这个步数，能否表示成$a$和$b$的二元函数，或者能得出一个上限也可以。印象中看到过一个是$\log_2 b$的上限。

zhcosin

我想起来了，设$a>b$，有一连串等式
\begin{align*}
a & =  q_0b+r_1 \\
r & = q_1 r_1+r_2 \\
&\cdots \\
r_{k-1}&=q_k r_k + r_{k+1} \\
&\cdots \\
r_{n-2}&=q_{n-1}r_{n-1}+r_n
\end{align*}
最后一式中$r_n=0$，易知$r_i$依次递减，且相邻两个$r_i$至少相差1，所以
\[ r_{k-1}=q_k r_k + r_{k+1} \geqslant r_k + r_{k+1}  \]
联系到斐波那契数列，令$s_k=r_{n-k}$，则$s_0=r_n=0, s_1=r_{n-1} \geqslant 1,  s_2=r_{n-2} \geqslant 2$，且
\[ s_{n-k+1} \geqslant s_{n-k}+s_{n-k-1}   \]
即
\[ s_{k+1} \geqslant s_{k}+s_{k-1} \]
于是按照数学归纳法，易知$s_k \geqslant F_k(k \geqslant 1)$，这里$F_k$是第$k$个斐波那契数。

而$s_n=r_0=b$，所以$b \geqslant F_n$，所以得到结论：假如辗转相除法进行了$n$步除法后才得出余数为零，那么$\min\{a,b\} \geqslant F_n$.

又因为
\[ F_n = \frac{1}{\sqrt{5}} \left( (\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n \right) \]
所以
\[ F_n \sim \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n  \]
所以近似的得到
\[ n \leqslant \log_{\phi} (\sqrt{5}\min\{a,b\}) \]
其中$\phi=\frac{1+\sqrt{5}}{2}$.

zhcosin

话说关于这个步数$E(a,b)$，有没有更细致的结果？