最大公因数

最大公因数（英语：highest common factor，hcf）也称最大公约数（英语：greatest common divisor，gcd）是数学词汇，指能够整除多个非零整数的最大正整数。例如8和12的最大公因数为4。

整数序列${\displaystyle a}$的最大公因数可以记为${\displaystyle (a_{1},a_{2},\dots ,a_{n})}$或${\displaystyle \gcd(a_{1},a_{2},\dots ,a_{n})}$。

最大公因数的值至少为1，例如${\displaystyle \gcd(3,7)=1}$；最大则为该组整数中绝对值最小的绝对值，例如${\displaystyle \gcd(3,9)=3}$和${\displaystyle \gcd(-3,9)=3}$。

求两个整数最大公约数主要的方法：

• 列举法：分别列出两整数的所有约数，并找出最大的公约数。
• 素因数分解：分别列出两数的素因数分解式，并计算共同项的乘积。
• 短除法：两数除以其共同素因数，直到两数互素时，所有除数的乘积即为最大公约数。
• 欧几里得算法：${\displaystyle \gcd(a,b)=\gcd(b,a\,\mathrm {mod} \,b)}$

两个整数${\displaystyle a,b}$的最大公约数和最小公倍数（lcm）的关系为：

${\displaystyle \gcd(a,b)\operatorname {lcm} (a,b)=|ab|}$

两个整数的最大公约数可用于计算两数的最小公倍数，或分数化简成最简分数。

两个整数的最大公约数和最小公倍数中存在分配律：

${\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c))}$

${\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c))}$

在直角坐标中，两顶点为${\displaystyle (0,0),(a,b)}$的线段会通过${\displaystyle \gcd(a,b)+1}$个格子点。

概述

例子

54和24的最大公因数是多少？

数字54可以表示为几组不同正整数的乘积：

${\displaystyle 54=1\times 54=2\times 27=3\times 18=6\times 9}$

故54的正约数为${\displaystyle 1,2,3,6,9,18,27,54}$。

同样地，24可以表示为：

${\displaystyle 24=1\times 24=2\times 12=3\times 8=4\times 6}$

故24的正约数为${\displaystyle 1,2,3,4,6,8,12,24}$。

这两组数列中的共同元素即为54和24的公因数：

${\displaystyle 1,2,3,6}$

其中的最大数6即为54和24的最大公约数，记为：

${\displaystyle \gcd(54,24)=6}$

互素数

如果两数的最大公因数为1，那么这两个数互素。例如，9和28就是互素数。

几何角度的说明

24乘60的矩形被十个12乘12的正方形格子完全覆盖，即12为24和60的最大公因数。推而广之，如果c是a和b的最大公因数，那么a乘b的矩形就可以被若干个边长为c的正方形格子完全覆盖。

假设有一个大小为24乘60的矩形区域，这个区域可以按照不同的大小划分正方形网格：1乘1、2乘2、3乘3、4乘4、6乘6、12乘12。因此，12是24和60的最大公因数。大小为24乘60的矩形区域，可以按照12乘12的大小划分正方形网格，一边有两格（${\displaystyle {\frac {24}{12}}=2}$）、另一边有五格（${\displaystyle {\frac {60}{12}}=5}$）。

计算

素因数分解法

可以通过素因数分解来计算最大公因数。例如计算${\displaystyle \gcd(18,84)}$，可以先进行素因数分解 ${\displaystyle 18=2\times 3^{2}}$ 和 ${\displaystyle 84=2^{2}\times 3\times 7}$，因为其中表达式${\displaystyle 2\times 3}$的“重合”，所以${\displaystyle \gcd(18,84)=6}$。实践中，这种方法只在数字比较小时才可行，因为对较大数进行素因数分解通常会耗费大量的时间。

再举一个用文氏图表示的例子，计算48和180的最大公因数。首先对这两个数进行素因数分解：

${\displaystyle 48=2\times 2\times 2\times 2\times 3}$

${\displaystyle 180=2\times 2\times 3\times 3\times 5}$

它们之中的共同元素是两个2和一个3：

^[1]

最小公倍数${\displaystyle =2\times 2\times (2\times 2\times 3)\times 3\times 5=720}$

最大公因数${\displaystyle =2\times 2\times 3=12}$

辗转相除法

相比素因数分解法，辗转相除法的效率更高。

计算${\displaystyle \gcd(18,48)}$时，先将48除以18得到商2、余数12，然后再将18除以12得到商1、余数6，再将12除以6得到商2、余数0，即得到最大公因数6。我们只关心每次除法的余数是否为0，为0即表示得到答案。这一算法更正式的描述是这样的：

${\displaystyle \gcd(a,0)=a}$

${\displaystyle \gcd(a,b)=\gcd(b,a\,\mathrm {mod} \,b)}$

其中

${\displaystyle a\,\mathrm {mod} \,b=a-b\left\lfloor {a \over b}\right\rfloor }$

如果参数都大于0，那么该算法可以写成更简单的形式：

${\displaystyle \gcd(a,a)=a}$,

${\displaystyle \gcd(a,b)=\gcd(a-b,b)\quad }$ 如果 a > b

${\displaystyle \gcd(a,b)=\gcd(a,b-a)\quad }$ 如果 b > a

使用辗转相除法计算62和36的最大公因数2的演示动画。

性质

• 任意a和b的公因数都是${\displaystyle \gcd(a,b)}$的约数。
• ${\displaystyle \gcd }$函数满足交换律：${\displaystyle \gcd(a,b)=\gcd(b,a)}$。
• ${\displaystyle \gcd }$函数满足结合律：${\displaystyle \gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c)}$

程式代码

以下使用辗转相除法实现。

C#

private int GCD(int a, int b) {
	if(0 != b) while(0 != (a %= b) && 0 != (b %= a));
	return a + b;
}

C++

运行时计算实现：

template<typename T>
T GCD(T a, T b) {
	if(b) while((a %= b) && (b %= a));
	return a + b;
}

编译时计算实现：

#include <iostream>
#include <type_traits>

template<typename T, std::enable_if_t<std::is_integral<T>::value, T> a, std::enable_if_t<std::is_integral<T>::value, T> b>
struct HCF{
public:
    static const T value=HCF<T, (a>b? b: a), (a>b? a%b: b%a)>::value;
};
template<typename T, std::enable_if_t<std::is_integral<T>::value, T> a>
struct HCF<T, a, 0>{
public:
    static const T value=a;
};
int main(){
    std::wcout<<HCF<int, 12, 64>::value<<std::endl;//Output: 4
}

C

int GCD(int a, int b) {
	if (b) while((a %= b) && (b %= a));
	return a + b;
}

Java

private int GCD(int a, int b) {
    if (b==0) return a; 
	return GCD(b, a % b);
}

JavaScript

const GCD = (a, b) => b ? GCD(b, a % b) : a;

Python

GCD = lambda a, b: (a if b == 0 else GCD(b, a % b))

# or

def GCD(a, b):
    if b == 0:
        return a
    return GCD(b, a % b)

政治用法

参见：共识决策法和香港核心价值

最大公约数又指一社会中不同阵营勉强所达之共同利益。

参考文献

1. Gustavo Delfino, "Understanding the Least Common Multiple and Greatest Common Divisor", [[Wolfram Demonstrations Project]], Published: February 1, 2013.. [2018-06-11]. （原始内容存档于2020-09-22）.

外部链接

• 图解最大公约数求法 （页面存档备份，存于互联网档案馆）
• 包含GCD动态规划 （页面存档备份，存于互联网档案馆）

参见

• 公倍数
• 公约数
• 最小公倍数