拉梅定理

对于 , 令 和 为满足 的整数，使得应用于 和 的欧几里得算法正好需要 步除法，并且 在满足这些条件的情况下尽可能小。那么 且 , 其中 是一个 斐波那契数 (Knuth 1998, p. 343)。

此外，欧几里得算法的步数永远不会超过较小数位数的 5 倍。实际上，界限 5 可以进一步降低到 , 其中 是黄金比例。