什么是最大公约数

大家好，欢迎来到IT知识分享网。

 弄懂背后的原理，再去学习。读书切记太慌忙，涵咏功夫意味长。别着急，慢慢读！

最大公约数的定义

最大公约数，指某几个整数共有因子中最大的一个。如果有一个自然数 a 能被自然数 b 整除，则称 a 为 b 的倍数，b 为 a 的约数。几个自然数公有的约数，叫做这几个数的公约数，其中最大的一个，叫做这几个数的最大公约数。

• 数学概念 最大公约数是数论中的一个重要概念，在分数的化简和整数的约分中都有着广泛的应用。此外，在物理学、工程和其他领域中，最大公约数也是一个重要的概念。
  • 例如在坐标里，将点(0,0)和(a,b)连起来，通过整数坐标的点的数目（除了(0,0)一点之外）就是 gcd(a,b)。
  • 如 12 和 30 的公约数有：1、2、3、6，其中 6 就是 12 和 30 的最大公约数。
• 常见方法 常见求最大公约数的方法有质因数分解法、短除法、辗转相除法、更相减损法等。

重要性质

• gcd(a,b)=gcd(b,a)（交换律）
• gcd(-a,b)=gcd(a,b)
• gcd(a,1)=1
• gcd(a,b)=gcd(b,a mod 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)
• 两个整数的最大公因子和最小公倍数中存在分配律：
  • gcd(a,lcm(b,c))=lcm(gcd(a,b),gcd(a,c))
  • lcm(a,gcd(b,c))=gcd(lcm(a,b),lcm(a,c))

辗转相除法原理 辗转相除法使用到的原理很聪明也很简单，假设用 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，剩下的另外一个数就是两者最大的公约数。

举例说明 例如，从求 42897 与 18644 的最大公约数出发：42897=2×18644+5609,(i) 18644=3×5609+1817,(ii) 5609=3×1817+158,(iii) 1817=11×158+79,(iv) 158=2×79。这样求出最大公约数是 79。

贝祖等式 贝祖等式，依艾蒂·贝祖命名，是线性丢番图方程。例如 12 和 42 的最大公因子是 6，便可以写(-3)×12 + 1×42 = 6 及 4×12 + (-1)×42 = 6。d 其实就是最小可以写成 ax + by 形式的正整数。

更相减损术_百度百科