求最大公因数的方法,最大公因数的方法怎样求最快

作者 | 大小吴

来源 | 大小吴的数学课堂

“

今天大小吴来和大家聊一聊最大公因数的前世今生。

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

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

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

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

“

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

“

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