辗转相除法的证明

我们用辗转相除法的递归形式：

    int f(int m,int n)

    {

    int r=m%n;

    if(r==0) return n;

    else return f(n,r);

    }

证明算法逻辑的正确性和有穷性，最终算法得到证明。

逻辑正确性涉及到两处return语句。

    第一处return语句的正确性证明见图：右栏1~8排

    第二处return语句的正确性证明见图：右栏剩余部分

算法的有穷性证明见左栏。(证明的前提是存在 x∈[1,min{m,n}]∩N 是m,n的最大公因数，而输入的m,n是自然数保证了这一前提)

PS：根据证明我们可以发现：对于算法来说，m，n的大小相对关系不影响算法（即传入参数时可以有m<n）

算法证明很简单，但是复杂度的推导具有挑战性。