Lamé定理#

• 如果欧几里得算法需要$k$步才能计算出一对整数的最大公约数，那么这对整数中较小的那个数必然大于或等于第$k$个斐波那契数$Fib(k)$.
• 数学表达式为：
  如果使用欧几里得算法求$GCD(a,b)$且 $a > b$,需要$k$步完成，则： $$b \geq Fib(k) \approx \frac {\phi^k}{\sqrt{5}}$$ 最坏的情况下是去求左右相邻的斐波那契数的最大公约数。