Lamé定理

概述

Lamé定理（Lamé’s Theorem）：用欧几里得算法求 $\gcd (a,b)$（$a>b>0$）时，所需的除法次数不超过 $b$ 的十进制位数的 5 倍。更精确地说，不超过 ${\log }_{\varphi }(b\sqrt{5})$ 次，其中 $\varphi =(1+\sqrt{5})/2$ 是黄金比例。

定理陈述

形式化陈述

定理（Lamé, 1844）：设 $a>b>0$ 为正整数，用欧几里得算法计算 $\gcd (a,b)$ 时所需的除法步数为 $k$，则： $k\le 5\cdot \text{number of decimal digits of }b$

等价地，设 $F_n$ 为第 $n$ 个Fibonacci数，若 $k$ 步除法完成计算，则 $a\ge F_{k+2}$ 且 $b\ge F_{k+1}$。

Fibonacci数列回顾

$F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}(n\ge 2)$

前几项：$0,1,1,2,3,5,8,13,21,34,55,89,144,\dots$

证明概要

证明思路

证明的核心是：欧几里得算法的最坏情况出现在输入为连续Fibonacci数时。

第一步：引理——Fibonacci数的下界

引理：对 $n\ge 3$，有 $F_n>{\varphi }^{n-2}$，其中 $\varphi =\frac{1+\sqrt{5}}{2}\approx 1.618$。

证明（数学归纳法）：

• 基础：$F_3=2>\varphi =1.618$，$F_4=3>{\varphi }^2=2.618$，成立
• 归纳：设 $F_k>{\varphi }^{k-2}$ 对所有 $k\le n$ 成立。则 $F_{n+1}=F_n+F_{n-1}>{\varphi }^{n-2}+{\varphi }^{n-3}={\varphi }^{n-3}(\varphi +1)={\varphi }^{n-3}\cdot {\varphi }^2={\varphi }^{n-1}$ （利用了 ${\varphi }^2=\varphi +1$）

第二步：最坏情况引理

引理：若欧几里得算法在 $k$ 步内完成 $\gcd (a,b)$ 的计算（$a>b$），则 $b\ge F_{k+1}$。

证明（强归纳法）：

• $k=1$：一步完成意味着 $b\mid a$，故 $b\ge 1=F_2$
• 设结论对 $k-1$ 步成立。第 $k$ 步算法计算 $a=qb+r$（$0\le r<b$），然后对 $(b,r)$ 继续执行。由于总共 $k$ 步，对 $(b,r)$ 需要 $k-1$ 步，由归纳假设 $r\ge F_k$。又 $b>r$，所以 $b\ge r+1\ge F_k+F_{k-1}=F_{k+1}$

第三步：推导上界

由 $b\ge F_{k+1}>{\varphi }^{k-1}$，取对数得： $k-1<{\log }_{\varphi }b$ $k<{\log }_{\varphi }b+1=\frac{\ln b}{\ln \varphi }+1$

由于 $\ln \varphi \approx 0.4812$，$\frac{1}{\ln \varphi }\approx 2.078$，故： $k<2.078\cdot \ln b+1$

第四步：转化为十进制位数

设 $b$ 有 $d$ 个十进制位，则 $10^{d-1}\le b<10^d$，故 $\ln b<d\ln 10\approx 2.303d$。

代入得： $k<2.078\times 2.303d+1\approx 4.785d+1<5d$

因此 $k\le 5d$，即除法次数不超过 $b$ 的十进制位数的 5 倍。

参考文献

• Lamé, G. (1844). Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. C. R. Acad. Sci. Paris, 19, 867-870.
• 证明详解: LibreTexts - Lamé’s Theorem
• OEIS条目: Euclidean Algorithm - OEIS Wiki

关键推论

• 推论1：欧几里得算法的时间复杂度为 $O(\log b)$，即输入规模的多项式级别，是非常高效的算法
• 推论2：最坏情况出现在 $a=F_{n+2}$、$b=F_{n+1}$ 时，此时恰好需要 $n$ 步除法
• 推论3：对扩展欧几里得算法，步数上界同样适用
• 推论4：$b$ 的二进制位数 $d^{\prime }=\lfloor {\log }_{2}b\rfloor +1$，则 $k=O(d^{\prime })$，算法复杂度为 $O((\log b{)}^2)$（假设每步除法为 $O(\log b)$）

应用场景

• 算法复杂度分析：Lamé定理是分析欧几里得算法效率的基础，保证其在密码学应用中的实用性
• RSA密码系统：RSA中需要计算模逆元，依赖扩展欧几里得算法，Lamé定理保证其效率
• 教学示例：Lamé定理是展示Fibonacci数列在算法分析中应用的经典案例
• 连分数理论：欧几里得算法与连分数展开直接对应，Lamé定理也给出连分数展开长度的上界

参见

• 欧几里得算法
• 最大公约数
• Fibonacci数
• 整除
• 递推关系