http://baike.baidu.com/link?url=KbAEB1lCT9U_Qneknt20kmKTZoOq0Jg09IGBl_HZozyG3hzG7f5wknhYczShF9-VvfrU3ojcWi4mDWO1ebo6Aq
【欧几里德算法证明】其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a mod b) (a>b 且a mod b 不为0)
证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a,d|b，而r = a - kb，因此d|r
因此d也是（b,a mod b）的公约数
因此（a,b）和（b,a mod b）的公约数是一样的，其最大公约数也必然相等，得证
或：证明：
第一步：令c=gcd(a,b），则设a=mc，b=nc
第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步：根据第二步结果可知c也是r的因数
第四步：可以断定m-kn与n互素【否则，可设m-kn=xd，n=yd，（d>1），则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)dc，b=nc=ycd，故a与b最大公约数≥cd，而非c，与前面结论矛盾】
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r），得证
以上两种方法实质一样的。
推荐阅读
- Python、java、go实现＂strStr()＂的几种方法
- Python、java、go实现＂搜索插入位置＂的几种方法
- Data|判断四个点是否可以构成矩形（优雅的解法！！！）
- Data|数据结构与算法笔记: 贪心策略之BST&BBST, Hashtable+Dictionary+Map, Priority Queue~Heap, Minium Spanning Tree
- Data|[转载] 线性表的数组实现