定理如下：
对任意非负整数a和任意正整数b, gcd(a,b） = gcd(b,a mod b)
首先证明 gcd(a,b) | gcd(b,a mod b)
设 gcd(a,b) = d
a mod b = a - b*k (k = a/b 向下取整的整数)
易得 d | a mod b 和 d | b 得出 d | gcd(b,a mod b) (d 为 最大公约数的一个因数)
接下来证明 gcd(b,a mod b) | gcd(a,b)
设 gcd(b, a mod b) = d 得 d | b, d | a mod b
a mod b = a - b*k 得 d | a
得出 d | gcd(a,b)
得证
GCD最大公约数递归定理的证明,布布扣,bubuko.com
原文：http://blog.csdn.net/mowayao/article/details/26944181