最大公因数(英语:highest common factor,hcf)也称最大公约数(英语:greatest common divisor,gcd)是数学词汇,指能够整除多个非零整数的最大正整数。例如8和12的最大公因数为4。
整数序列
的最大公因数可以记为
或
。
最大公因数的值至少为1,例如
;最大则为该组整数中绝对值最小的绝对值,例如
和
。
求两个整数最大公约数主要的方法:
两个整数
的最大公约数和最小公倍数(lcm)的关系为:
![{\displaystyle \gcd(a,b)\operatorname {lcm} (a,b)=|ab|}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecc462228ff34b4f75ae28f4c42ca2c0e70d0ea7)
两个整数的最大公约数可用于计算两数的最小公倍数,或分数化简成最简分数。
两个整数的最大公约数和最小公倍数中存在分配律:
![{\displaystyle \gcd(a,\operatorname {lcm} (b,c))=\operatorname {lcm} (\gcd(a,b),\gcd(a,c))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/27cd22e7c6b308ab024b69fd0105be3d5ddd3bba)
![{\displaystyle \operatorname {lcm} (a,\gcd(b,c))=\gcd(\operatorname {lcm} (a,b),\operatorname {lcm} (a,c))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fb75682e70bc631268d12c42df478f4502d27641)
在直角坐标中,两顶点为
的线段会通过
个格子点。
概述
例子
54和24的最大公因数是多少?
数字54可以表示为几组不同正整数的乘积:
![{\displaystyle 54=1\times 54=2\times 27=3\times 18=6\times 9}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7050362bad3551aa7604857442eebde64bedf546)
故54的正约数为
。
同样地,24可以表示为:
![{\displaystyle 24=1\times 24=2\times 12=3\times 8=4\times 6}](https://wikimedia.org/api/rest_v1/media/math/render/svg/edfb682995c997a758ab395c92d501db3790b8d3)
故24的正约数为
。
这两组数列中的共同元素即为54和24的公因数:
![{\displaystyle 1,2,3,6}](https://wikimedia.org/api/rest_v1/media/math/render/svg/efa2ab3065cedf95711ea05a2fcae979cf365ba0)
其中的最大数6即为54和24的最大公约数,记为:
![{\displaystyle \gcd(54,24)=6}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b414ce7bb77272dd9775a601a1131539059adb8a)
互素数
如果两数的最大公因数为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的大小划分正方形网格,一边有两格(
)、另一边有五格(
)。
计算
素因数分解法
可以通过素因数分解来计算最大公因数。例如计算
,可以先进行素因数分解
和
,因为其中表达式
的“重合”,所以
。实践中,这种方法只在数字比较小时才可行,因为对较大数进行素因数分解通常会耗费大量的时间。
再举一个用文氏图表示的例子,计算48和180的最大公因数。首先对这两个数进行素因数分解:
![{\displaystyle 48=2\times 2\times 2\times 2\times 3}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddbe49051aa06d767cd8706176483764c59d2b3c)
![{\displaystyle 180=2\times 2\times 3\times 3\times 5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1fd136b3e4228ca19233bd8fcffdc9ccb3277517)
它们之中的共同元素是两个2和一个3:
[1]
- 最小公倍数
![{\displaystyle =2\times 2\times (2\times 2\times 3)\times 3\times 5=720}](https://wikimedia.org/api/rest_v1/media/math/render/svg/baecd4db346ff27999c1b02ea792852b10b64c26)
- 最大公因数
![{\displaystyle =2\times 2\times 3=12}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5668b3f86d78b84bfff47343aed44a9ae04daee3)
辗转相除法
相比素因数分解法,辗转相除法的效率更高。
计算
时,先将48除以18得到商2、余数12,然后再将18除以12得到商1、余数6,再将12除以6得到商2、余数0,即得到最大公因数6。我们只关心每次除法的余数是否为0,为0即表示得到答案。这一算法更正式的描述是这样的:
![{\displaystyle \gcd(a,0)=a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8f2e7dbf90c33d22cd4e0c8e1f1d088677b847d6)
![{\displaystyle \gcd(a,b)=\gcd(b,a\,\mathrm {mod} \,b)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50dcf31162a0922f36a606e0b0a95b2744039b0a)
其中
![{\displaystyle a\,\mathrm {mod} \,b=a-b\left\lfloor {a \over b}\right\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/538295524dc9f7fd979545c308690d11534d6320)
如果参数都大于0,那么该算法可以写成更简单的形式:
,
如果 a > b
如果 b > a
使用辗转相除法计算62和36的最大公因数2的演示动画。
性质
- 任意a和b的公因数都是
的约数。
函数满足交换律:
。
函数满足结合律:![{\displaystyle \gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/baa1dee1cbd17053fa3ed7b519f7c0e66c985212)
程式代码
以下使用辗转相除法实现。
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)
政治用法
最大公约数又指一社会中不同阵营勉强所达之共同利益。
参考文献
外部链接
参见