公约数是什么意思(求最大公约数最快方法)

大家好，我是讯享网，大家多多关注。

来源|大小吴的数学课堂

“

今天大吴和小吴就和大家聊聊有最大公约数的前世。

1 什么是最大公因数

最大公约数，又称最大公约数、最大公约数，是指两个或两个以上整数的最大公约数。的最大公因数可以记为或，多个整数的最大公因数符号相同。求最大公因式的方法有很多，比如质因数分解，短除法，这些我们小学都学过。

2 欧几里得与辗转相除法

欧几里德在《几何原本》第ⅶ卷中用线段及其长度解释了最大公因式问题，凝练出了世界上最早的算法——逆序除法(也叫欧几里德算法)，可见于定义ⅶ.12、命题ⅶ.1、命题ⅶ.2。

“

定义七. 12:只能作为约定单位量来度量(整除)的几个数称为互质数。

“

命题ⅶ.1:有两个不相等的数。从大数中连续减去小数，直到余数小于小数，然后从小数中连续减去余数，直到小于余数。这样下去。如果余数直到最后一个余数是一个单位才能度量前一个数，那么这两个数就是质数。

验证:和互质，即只有一个单位可以测量和。

证明:如果sum不是素数，那么总有一些数来度量它们并使它们(在这里)。

订单:已测量，剩余少于。订单:已测量，剩余少于。订单:测量的剩余单位数量。

因为考完了，考完了，所以:考完了。

因为是测试出来的，所以测试出来的是残值。

同样，残值也是可以衡量的。

最终可以测出单位量，这是不可能的，因为。

所以:和谐只能作为公约的单位量来衡量，即:和谐互质(定义VII.12)。

现代数学语言在《几何原本》中不再使用欧几里得的术语。“测量”和“被测量”这两个词已经被“划分”和“可分”所取代。这个命题的证明曾经使用过辗转相除法:从两个数开始，用较大的数反复减去较小的数，但这里为了说明两个数的相互性质，假设1是辗转相除法的最终结果。

“

命题七. 2:给定两个互不质数，你可以找到它们的最大公因数(通过辗转相除)。

这里需要分类讨论:

①如果可以度量，那一定是sum的最大公因式。

②如果无法测量，那么:用余数来测量；如果无法测量，就用后面的余数来测量前面的余数，直到后面的余数测量到前面的余数。

这个最后的余数不是一个单位，否则就是互质，与假设相矛盾。所以:某个数可以度量它之前的数的余数。

在这里，类似于命题ⅶ.1的操作，度量，度量，并设定最终度量。同样可以推导出和是可以同时度量的，这是和的一个公因数。

下面进一步说明一定是最大的。

如果它不是总和的最大公因数，那么某个大于的数必须同时度量总和。

然后，因为它度量所有，它度量所有，它度量所有，所以它度量所有的残值。同样，它度量所有的残值，但这是不可能的，因为较大的数不能度量较小的数，这是矛盾的。

所以不存在大于测量和的数，也就是和的最大公因式。

在这个命题中，再次用相除法求两个非质数的最大公因数，大数反复减数，直到余数小于小数。例如，要求首先从104中反复减去40，直到余数(24)小于40，即从40中反复减去24得到余数16，即从24中反复减去16得到余数8，即最后停止，因为8能被16整除。于是我们发现这个过程也可以用图形来解释:例如，如果图形是边长为40和104的矩形，finding就等价于这个。

欧几里得在《几何原本》中对相的轮流划分的讨论，总是可以推广到对无理数和不可公度量的分析(也是用几何作图的方法)，很有意思。之后再写文章讨论。

在现代数学语言中，相位划分可以描述为

“

设置两个数字，然后

（不妨设 且，不为0，指求余运算，为除以的余数）

也就是说，两个正整数的最大公约数等于较小的数和两个数的除法余数的最大公约数。

所以移相除法就是反复除除数和余数。余数为0时，当前公式的除数为最大公因式。

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

除了西方，其实在古老的东方，中国古代聪明的数学家们就已经揭示了最大公因式的秘密——利用多相损技术寻找最大公因式。

相位减法是九章算术中求最大公因式的算法。它最初是为近似除法而设计的，但也适用于求两个数的最大公因式。《九章算术》最初记载:

“

可以对半分，不可以对半分，设定分母，孩子的数量，才能以少减多，甚至更多的互相减损。让我们以相等的数量预约。

这篇古文的意思是:

(如果需要近似分数，那么)如果能减半，就减半(就是用2近似分数)。如果不能减半，那就把分母和分子比较，把小数从大数中减去，互相相减，直到相减等于差，用这个相等的数来近似分数。

例如，通过使用更多相位递减技术找到104和40的最大公因数。

由于104和40是偶数，所以取其一半得到52和20。

由于52和20是偶数，继续取一半得到26和10。

由于26和10是偶数，重复上述操作得到13和5。

因为13和5不是偶数，所以将数字减少一个大的数以得到

当最后的减法和差都是1时，减法停止。

因此，104和40的最大公因数等于1乘以在第一、第二和第三步中丢弃的三个2，即

可以发现，作为一种求最大公因式的算法，两种方法的结果是一样的，但是仔细考虑，一种用除法，一种用减法。无论东方还是西方，都有辉煌的数学成就，凝结着人类智慧的结晶。

参考文献[1]欧几里德。几何元素[2]九章算术。