最大公因数的前世今生

luyuanhong

最大公因数的前世今生

作者 | 大小吴
来源 | 大小吴的数学课堂

1 什么是最大公因数

最大公因数（Greatest Common Divisor），也称最大公约数、最大公因子，指两个或多个整数共有因数中最大的一个。a,b 的最大公因数可记为 gcd(a,b) 或 (a,b) ，多个整数的最大公因数也有同样的记号。求最大公因数有多种方法，比如我们小学就学过的质因数分解法、短除法。


短除法求最大公因数

那么你是否有这样的疑问：追本溯源，最大公因数最早出现在哪里呢？

2 欧几里得与辗转相除法


欧几里得（约公元前330年—公元前275年）

实际上，最早系统研究最大公因数问题的是古希腊数学家欧几里得。只不过那时还没有系统的代数学，相对应地，几何学明显地从数学中分离出来，并在希腊科学中占统治地位，其威力之大，以致于纯算术的或代数的问题都被转译为几何语言。

而欧几里得在《几何原本》第Ⅶ卷中正是运用了线段及其长度解释了最大公因数问题，并凝练出了世界上最早的算法——辗转相除法（也称欧几里得算法），具体可见定义Ⅶ.12、命题Ⅶ.1和命题Ⅶ.2.

“定义Ⅶ.12：只能被作为公约的一个单位量所测尽（整除）的几个数称为互质数。”

“命题Ⅶ.1：设有不等两数，从大数中连续减去小数直到余数小于小数，再从小数中连续减去余数直到小于余数，这样一直下去，如果余数测不尽其前一个数，直到最后的余数为一个单位，那么该二数互质。”



现代数学语言已经不再沿用欧几里得在《几何原本》中的术语了，“测得”、“测尽”两个词已用“除”、“整除”代替。这一命题的证明已经运用了辗转相除法：开始于两个数，从较大的数中重复减去较小的数，只不过这里为了说明两数互质，它假定1是辗转相除法的最终结果。

“命题Ⅶ.2：给定两个不互质的数，可以（用辗转相除法）找到它们的最大公因数。”





欧几里得在《几何原本》中对辗转相除法的讨论一直可以延申到对无理量和不可公度量的分析中去（同样也是用几何作图的方法），十分有趣，之后我们会再另写一篇加以讨论。

辗转相除法用现代数学语言可以描述为

“设两数 a,b，则 gcd(a,b)=gcd(b,r)（不妨设 a＞b 且 r=a mod b，r 不为 0 ，mod 指求余运算，r 为 a 除以 b 的余数）”

即两个正整数的最大公约数等于其中较小的那个数和两数相除余数的最大公因数。

因此辗转相除法就是以除数和余数反复做除法运算，当余数为0时，取当前算式除数即为最大公因数。

3 《九章算术》与更相减损术

除了西方，其实在古老的东方，我国古代聪明的数学家们也早已揭示了最大公因数的秘密——运用更相减损术求最大公因数。


《九章算术》

提到更相减损术，就不得不提我国古代数学巨著《九章算术》。《九章算术》内容十分丰富，全书总结了战国、秦、汉时期的数学成就，成于公元一世纪左右，其作者已不可考。根据研究，西汉的张苍、耿寿昌曾经做过增补。最后成书最迟在东汉前期，但是其基本内容在西汉后期已经基本定型。

更相减损术是《九章算术》中一种求最大公因数的算法，它原本是为约分而设计的，但它同时也适用于求两个数的最大公因数。《九章算术》原文记载：

“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。”

这句古文的意思是：

（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。



可以发现，辗转相除法和更相减损术一个用除法，一个用减法，但细想其原理则是异曲同工的，其作为求最大公因数的算法，其结果也是殊途同归的。不管是东方还是西方，都蕴藏着灿烂辉煌的数学成就，凝结了人类智慧的结晶。

参考文献
[1]欧几里得.几何原本
[2]九章算术