Question

什么是最小公约数？

Answer 1

最小公约数，也称最大公因数，是指两个或多个整数共有的约数中，最大的一个数。通常用符号gcd(a,b)表示。

最小公约数的求法可以采用欧几里得算法（辗转相除法）：将两个整数中较大的数除以较小的数，再用较小的数去除所得余数，继续用余数去除，直到余数为0为止。此时，最小公约数就是最后一次的除数。

例如，求出96和64的最小公约数，可以按照以下步骤进行：

• 用96除以64，余数为32；

• 用64除以32，余数为0；

• 因此，最小公约数为32。

最小公约数在数学和计算机科学中都有广泛的应用，例如化简分数、求最简整数比、计算最小公倍数等问题都需要用到最小公约数。