欧几里得算法证明

        欧几里得算法，也叫做辗转相除法，gcd(a, b) = gcd (b, a%b)，即a和b最大公约数等于b和a%b的最大公约数。相信大家都会用，但是很多人不知道为什么，我也看了很多文章，写的都不太相同，这里我说说我自己的证明过程：
        这里的证明我分为两步求证：
        1.求证：a和b的公约数等于b和a%b的公约数；
        2.求证：b和a%b的公约数是最大公约数。
        
        求证1：a和b公约数等于b和a%b的公约数
        为了方便大家看，我先把下面用到的变量注一下：
            n：公约数        m：a%b            k、k'、k''：都是常数
        （先不看，跟着我的思路走，过程中忘了哪个变量是干什么的再回来看一下）
        这里设一个n，n是a和b的一个公约数，所以有 
                    a/n = k' , b/n = k'' (k'和k''都是常量)     --------------①
        这里既然证明a和b最大公约数等于b和a%b的最大公约数，那么这里你还需要有这三个数，a和b是已知的，那么这里我们设m = a % b    (m ≠ 0 ，若m=0，b一定是a和b的最大公约数)，那么
                    a = kb + m  (k是一个常量)   --------------------------②
        ②变形得：
                    m = a - kb   -----------------------------------------------③
        ③等式两边同时除以n得：
                    m/n = a/n - k(b/n)    -------------------------------------④
        ①④结合，得：
                    m/n = k' - kk''  --------------------------------------------⑤
        看⑤式中，k、k'、k''都是常数，所以m/n是一个常数，所以n也是m的约数，所以说n是a、b、m三个的公约数，那么可以得到n也是b和a%b的公约数。
        看到这我们已经得出了结论一：a和b公约数等于b和a%b的公约数。
        
        下面只需证明结论一中的公约数是他们的最大公约数即可：
        求证2：公约数是最大公约数
        首先，根据结论一，我们可以找出多组数据，使得他们都有一个共同的约数n
        例如：(a, b)        (b, a%b)        (a%b, b%(a%b))    ...       他们每组都有一个公约数n
        如此一直向下，这里我们可以设（A， B）的公约数为n，每组数据都用（A， B）来更新
        （每次A都变为原来的B，B变成原来的A%B）
        因为A%B总是小于B，如果一直更新下去，A%B总有变成0的时候，也就是A % B = 0
        设当前组合为(A，B)，且满足条件(A % B = 0)，这时我们可以得到组合(A，B)的最大公约数为B
        现在我们将上面那一行数据延伸：(a, b)        (b, a%b)        (a%b, b%(a%b))    ...    (kA + B, A)    (A, B)        
        上面这一组数据都有一个公约数n，那么我们只需证明(A, B)的最大公约数与(kA + B, A)的最大公约数相等
        现在已知B是(A, B)的最大公约数，又已知(kA + B, A)    (A, B)有相同的约数n
        我们此时假设(A, B)的这个约数n就是最大公约数B，那么只需证明B也是(kA + B, A)的最大公约数即可得出结论这里的公约数n是最大公约数。
        那么也就是求证：B是(kA + B, A)的最大公约数
                已知A % B = 0得：
                            A =  k'B   ----------------------------------⑥
                结合⑥得：
                            kA + B = (kk'+1)B   ---------------------⑦
                根据⑥⑦我们可以得出(kA + B, A)的公约数为：B以及B的约数
                所以(kA + B, A)的最大公约数为B
        得出结论：a和b最大公约数等于b和a%b的最大公约数，也就是欧几里得算法gcd(a, b) = gcd (b, a%b)。