最大公约数和最小公倍数

一、定义

1.最大公约数:最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。

2.最小公倍数:两个或多个整数公有的倍数叫做它们的公倍数,其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数a,b的最小公倍数记为[a,b],同样的,a,b,c的最小公倍数记为[a,b,c],多个整数的最小公倍数也有同样的记号。

二、性质

1.最小公倍数的性质:公倍数(common multiple)指在两个或两个以上的自然数中,如果它们有相同的倍数,这些倍数就是它们的公倍数,其中除0以外最小的一个公倍数,叫做这几个数的最小公倍数。

2.最大公约数的性质:质因数分解法:把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数。

3.最大公因数和最小公倍数之间的性质:两个自然数的乘积等于这两个自然数的最大公约数和最小公倍数的乘积。

重要性质:

(a,b)=(b,a) (交换律)

(-a,b)=(a,b)

(a,a)=|a|

(a,0)=|a|

(a,1)=1

(a,b)=(b, a mod b)

(a,b)=(b, a-b)

如果有附加的一个自然数m,

则: (ma,mb)=m * (a,b) (分配律)

(a+mb ,b)=(a,b)

如果m是a和b的最大公约数,

则: (a/m ,b/m)=(a,b)/m

在乘法函数中有:

(ab,m)=(a,m) * (b,m)

两个整数的最大公约数主要有两种寻找方法:

* 两数各分解质因数,然后取出同样有的质因数乘起来

*辗转相除法(扩展版)

和最小公倍数(lcm)的关系:

(a, b) * [a, b] = ab

(a, [b, c]) = [(a, b), (a, c)]

[a, (b, c)] = ([a, b], [a, c])

三、如何求解最大公约数和最小公倍数

短除法求解最大公约数和最小公倍数

短除法求最大公约数,先用这几个数的公约数连续去除,一直除到所有的商互质为止,然后把所有的除数连乘起来,所得的积就是这几个数的最大公约数。

短除法求最小公倍数,先用这几个数的公约数去除每个数,再用部分数的公约数去除,并把不能整除的数移下来,一直除到所有的商中每两个数都是互质的为止,然后把所有的除数和商连乘起来,所得的积就是这几个数的最小公倍数。具体算法如下图。

四、最小公倍数和最大公因数关系

关系一:乘积关系

最小公倍数和最大公因数之间存在乘积关系,即:(a, b) × [a, b] = a × b。

其中 (a, b) 表示 a 和 b 的最大公因数,[a, b] 表示 a 和 b 的最小公倍数。

这个关系可以理解为:两个自然数的乘积等于这两个自然数的最大公约数和最小公倍数的乘积。

关系二:互质数

如果两个数互质,即它们的最大公因数为1,那么它们的最小公倍数就是它们的乘积。

关系三:倍数关系

如果两个数中,较大数是较小数的倍数,那么较小数就是这两个数的最大公因数,较大数就是这两个数的最小公倍数。

关系四:质因数分解

最小公倍数等于它们所有质因数的最高次幂的乘积。

例如,对于两个数 12 和 18:

12 = 2² × 3        18 = 2 × 3²

它们的最大公因数是 6(2 × 3),最小公倍数是 36(2² × 3²)。

五、质数

质数又称素数,是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数(规定1既不是质数也不是合数)。

1000以内的质数可以点下面链接查看:

1000以内的质数有哪些?分别是什么?

六、互素(互质)

互素,即互为质数,是指两个或多个整数之间除了1之外没有其他公约数。其性质包括:

‌定义性质‌:两个整数如果只有1作为它们的公因数,则称这两个整数互素。

‌质数性质‌:两个不同的质数一定是互素的,因为质数只有1和它本身两个因数。

‌倍数性质‌:一个质数与另一个不为它倍数的数互质。

‌相邻性质‌:相邻的两个自然数(包括相邻的两个奇数)是互质的,因为它们的差是1,而1不是除了1以外的任何数的因数。

‌特殊性质‌:1和-1与所有整数互素,且它们是唯一与0互素的整数。