欧几里德算法

在数学中,欧几里德-Euclid 算法 是计算两个数的最大公约数 (GCD) 的有效方法,两个数除以它们的最大数 除去 余数.

欧几里德算法 基于这样的原理: 两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（ 252 = 21 × 12 ； 105 = 21 × 5 ）；因为 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数.

通过反转步骤,GCD 可以表示为两个原始数字的总和,两数的最大公约数可以用两数的整数倍相加来表示，如 21 = 5 × 105 + (−2) × 252 。这个重要的结论叫做裴蜀定理。

Euclid 用于求出 两个起始长度的最大公约数 (GCD) 的方法BA和DC,两者都定义为常见"单位"长度的倍数. 长度DC更短, 它被用来"衡量"BA,但下一次只剩了EA, EA小于DC.现在测量 (两倍/次) 获得DC剩下较短的长度,剩下的FC比EA短. 然后FC继续测量 (三次) 长度EA. 因为没有剩余,所以过程结束,FC就是GCD-最大公约数.

在右边 Nicomachus的数字示例 起始数值变成了49和21,导致他们的GCD7 (源自Heath 1908: 300) .

一个24-by-60矩形上 覆盖了 十个12-by-12方形瓷砖,12是24和60的GCD. 更一般地说,一个a-by-b矩形可以用c边长的方形瓷砖覆盖,因为c是a和b的最大公约数.

欧几里得算法的基于减法的动画. 初始矩形具有尺寸a = 1071和b = 462. 正方形的大小是$462 \times 462$放在初始矩形里面,然后 上方留下一个$462 \times 147$长方形. 这个矩形平铺着$147 \times 147$矩形,直到又有$21 \times 147$矩形留下,然后平铺$21 \times 21$矩形,发现没有露出的区域. 那么最小的方形尺寸,21,是1071和462的GCD.

参考

Wikipedia