common
divisor,简写为gcd;或highest
common
factor,简写为hcf),指某几个整数共有因子中最大的一个。能够整除一个整数的整数称为其的约数(如5是10约数);
能够被一个整数整除的整数称为其的倍数(如10是5的倍数);
如果一个数既是数A的约数,又是数B的约数,称为A,B的公约数,A,B的公约数
中最大的一个(可以包括AB自身)称为AB的最大公约数
定义
如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数。几个自然数公有的约数,叫做这几个自然数的公约数。公约数中最大的一个公约数,称为这几个自然数的最大公约数。
例:
在2、4、6中,2就是2,4,6的最大公约数。
早在公元前300年左右,欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。辗转相除法使用到的原理很聪明也很简单,假设用f(x,
y)表示x,y的最大公约数,取k
=
x/y,b
=
x%y,则x
=
ky
+
b,如果一个数能够同时整除x和y,则必能同时整除b和y;而能够同时整除b和y的数也必能同时整除x和y,即x和y的公约数与b和y的公约数是相同的,其最大公约数也是相同的,则有f(x,
y)=
f(y,
x%y)(y
>
0),如此便可把原问题转化为求两个更小数的最大公约数,直到其中一个数为0,剩下的另外一个数就是两者最大的公约数。
例如,12和30的公约数有:1、2、3、6,其中6就是12和30的最大公约数。
辗转相除法是古希腊求两个正整数的最大公约数的,也叫欧几里德算法,其方法是用较大的数除以较小的数,上面较小的除数和得出的余数构成新的一对数,继续做上面的除法,直到出现能够整除的两个数,其中较小的数(即除数)就是最大公约数。以求288和123的最大公约数为例,操作如下:288÷123=2余42
123÷42=2余39
42÷39=1余3
39÷3=13
所以3就是288和123的最大公约数。
性质
重要性质:gcd(a,b)=gcd(b,a)
(交换律)
gcd(-a,b)=gcd(a,b)
gcd(a,a)=|a|
gcd(a,0)=|a|
gcd(a,1)=1
gcd(a,b)=gcd(b,
a
mod
b)
gcd(a,b)=gcd(b,
a-b)
如果有附加的一个自然数m,
则:
gcd(ma,mb)=m
*
gcd(a,b)
(分配律)
gcd(a+mb
,b)=gcd(a,b)
如果m是a和b的最大公约数,
则:
gcd(a/m
,b/m)=gcd(a,b)/m
在乘法函数中有:
gcd(ab,m)=gcd(a,m)
*
gcd(b,m)
两个整数的最大公约数主要有两种寻找方法:
*
两数各分解质因数,然后取出同样有的质因数乘起来
*辗转相除法(扩展版)
和最小公倍数(lcm)的关系:
gcd(a,
b)
*
lcm(a,
b)
=
ab
a与b有最大公约数,
两个整数的最大公因子可用于计算两数的最小公倍数,或分数化简成最简分数。
两个整数的最大公因子和最小公倍数中存在分配律:
*
gcd(a,
lcm(b,
c))
=
lcm(gcd(a,
b),
gcd(a,
c))
*
lcm(a,
gcd(b,
c))
=
gcd(lcm(a,
b),
lcm(a,
c))
在坐标里,将点(0,
0)和(a,
b)连起来,通过整数坐标的点的数目(除了(0,
0)一点之外)就是gcd(a,
b)。
匿名回答于2024-05-19 16:33:32