集合角度理解欧几里得算法, 很直观
r=a mod b
d是a,b的任意一个公因数，d也是b，r的任意公因数。也就是a,b的任意一个公因数也必然是b,r的任意一个公因数，a,b的公因数集等于b,r的公因数集。那么这两个集合里的最大值肯定也是相等的。
举个例子来说，我们求gcd（12，18）
12，18的公因数有：1，2，3，6。
由算法gcd（a，b）=gcd(b,a%b)有gcd（12，18）=gcd(18,12%18)=gcd(18,12)
18,12的公因数有：1，2，3，6。
接着往下算，gcd（18，12）=gcd(12,18%12)=gcd(12,6)
12,6的公因数有：1，2，3，6。
再往下，gcd（12，6）=gcd(6,12%6)=gcd(6,0)
0,6的公因数有：1，2，3，6。
最后，就由gcd（0，n)=n得gcd（0，6）=6
你看，第1，3，5，7他们的公因数集都是相等的，自然的，集合里的最大值也是相等的。
证明如果a=bq+r，那么d是a和b的公因数，当且仅当d是b和r的公因数。
1)设d是a和b的公因数，则d|a且d|b，于是d|(a−bq)。也就是说d|r,因为r=a−bq –> d是b,r的公因数。
这里解释一下d|（a-bq)：因为d|a，d|b,所以有a=dx,b=dy;把d代入a-bq有dx-dyq=d(x-yq).所以d|（a-bq)
2)设d是b和r的公因数，则d|r且d|b。于是，d|（bq+r）.所以d|a –> 所以d是a,b的公因数。
综上，a,b的所有公因数和b,r的所有公因数是一样的。那么，d是a，b的最大公因数，当且仅当d是b和r的最大公因数。
最后，就由gcd（0，c) = c, 得出最大公约数c
