写一个算法的时候遇到了一个小问题，如何才能求出两个数字的最小公倍数。而最小公倍数又等于两数相乘除以最大公约数。于是这个问题被转换成了求最大公约数，那么如何求最大公约数呢， 欧几里得算法在几千年前就已经有了记载，在中国的《 九章算术 》也有记载叫做更相减损数，下面记录一下学习心得。

辗转相除法的核心是要证明如果一个数字可以整除某两个不相等的正整数，那么这两个正整数相减后的值，仍然可以被该数字整除。推导如下

设有两个正整数分别是a 和 b，且a > b，如果a % x  = 0, b % x = 0 求证 (a - b ) % x = 0
推导：
由于a和b均可被x整除，所以设定
a / x = k
b / x = j
则k,j 均为整数，且k > j。
有 (a - b) / x = (k - j)
因为 k,j 均为正整数，且k > j,所以k - j 为正整数，所以(a - b) / x 的值也是正整数，所以(a - b) % x = 0

接下来通过一个例子演示辗转相除法的过程，计算6834和4777的最大公约数。

有上面的证明的定理可知，
6834 和 4777 的最大公约数，也是 (6834 - 4777) 和 4777 的公约数, 因为他们的最大公约数一定可以被 4777,6834,(6834 - 4777) 其中之一整除。我们为了收敛这个算法取两个较小的值出来继续求最大公约数。
现在问题变成了 2057和4777的最大公约数，可以推导为求 (4777 - 2057), 2057 的最大公约数，即 2720和2057最大公约数。
重复以上步骤如下
663 (2720 - 2057), 2057
1394 (2057 - 663), 663
731 (1394 - 663), 663
68 (731 - 663), 663
595 (663 - 68), 68
527 (595 - 68), 68
459 (527 - 68), 68
391 (459 - 68), 68
323 (391 - 68), 68
255 (323 - 68), 68
187 (255 - 68), 68
119 (255 - 68), 68
51 (119 - 68), 68
17 (68, 51), 51
现在 17 和 51可以被整除了，51 和 17 的最大公约数就是17，因为能够被 6834和4777整除的最大公约数也能被51和17整除，所以51和17的最大公约数也是6834和4777的最大公约数。

此外通过上面的例子也可以发现，我们做了很多重复的步骤，比如减68，减了很多次，我们可以通过取模2057 % 68 直接得到 17。这就是辗转相除法的证明过程。
利用能够整除两个大数的数字也能整除两个大数的差的特性，一步步收敛，这里需要注意的是，要理解为什么收敛到最后的最大公约数也是两个开始的大数的最大公约数。