猫史档案馆

欧几里得算法最早记载在《几何原本》数论卷当中，在我国的《九章算术》中，也出现了类似记载。古希腊时期，几何在人们心中的地位远超代数，求最小公因数的问题被这样记载：

用所要求取最大公因数的两个数为矩形的边画出一个矩形，接着试着在这个矩形中去寻找一个正方形，（这里只考虑矩形和正方形的边数皆为正整数的情况）使得找到的正方形能够不留空隙的填满此矩形，显然，这种正方形不止一个，而我们的目标就是找出这种正方形中边长最大的那一个。那么，我们应该怎么找到这样一个正方形？

我们可以这样做：首先，以矩形的宽为除数，与矩形的长进行除法运算，然后取得余数，上一轮中的除数变为本轮中的被除数，以余数做除数，反复操作，直至某轮余数为0结束（因此欧几里得算法也被称为辗转相除法），当余数为0时，也就意味着矩形内部没有空隙。例如下图所示，求取6与20的最大公因数的过程（图可能稍丑，毕竟只是我用Windows画板画的）：

这个方法的理论基础是一条定理：被除数和除数的最大公约数等于除数和余数的最大公约数。证明见下图（证明来自百度知道，如果有更优秀的证法可以写在评论区）

注：求出最大公因数后也能快速地求出最小公倍数，因为最小公倍数=两数乘积÷最大公因数，证明如下：

设有a,b两数，c为两数的最大公因数。a×b÷c=a×b×1/c,(a×b×1/c)÷a=b/c，,(a×b×1/c)÷b=a/c,显然结果皆为整数。