【趣题征解】任给两个正整数 m, n, 至多需要多少步辗转相除方能得到其最大公约数？

elim

【题】： 任给两个正整数 m, n, 至多需要多少步辗转相除方能得到其最大公约数？

luyuanhong

    任给一个正整数 k ，都可以在 Fibonacci 数列 {a(n)}={1,1,2,3,5,8,13,21,34,…} 中，

找到两个正整数 m=a(k+2) 和 n=a(k+1) ，使得需要 k 步辗转相除才能得到其最大公约数 1 。

    例如，令 k=7 ，则可以取 m=a(9)=34 ，n=a(8)=21 ，作如下辗转相除：

    34÷21=1……13 ，

    21÷13=1……8 ，

    13÷8=1……5 ，

    8÷5=1……3 ，

    5÷3=1……2 ，

    3÷2=1……1 ，

    1÷1=1 。

    经过 k=7 次辗转相除，求得 34 与 21 的最大公约数是 1 。

awei

【维基百科】假设用辗转相除法求自然数a和b（a > b > 0）的最大公约数需要N步，那么满足这一条件的a和b的最小值分别是斐波那契数FN+2和FN+1。[94]这可以用数学归纳法证明。[95]假设N = 1，b整除a，满足这一条件的a和b最小是b = 1、a = 2，正是F2和F3。现在假设这一规律对M ? 1有效。一个需要M步的算法的第一步是a = q0b + r0，第二步是b = q1r0 + r1。因为算法是递归的，它需要M ? 1 步才能算出 GCD(b, r0)，其中b和r0的最小值是 FM+1 和 FM。所以a的最小值是当 q0 = 1 的时候，此时 a = b + r0 = FM+1 + FM = FM+2。1844年，加百利·拉梅发现这个证明标志着计算复杂性理论的诞生。[96]这也是斐波那契数列的第一个实际应用。[94]

这个结果也证明了辗转相除法的运算步骤不会超过较小数十进制下的位数的五倍。………
维基百科很详细，希望对老师有所帮助。

elim

谢谢陆老师的解答，那么是不是可以说，下面的结果是最好估计？

elim

谢谢 awei. 两位老师的帖子很好。看来这个问题早已被关注并且有了相当彻底的研究。