最大公约数Zuida gongyueshu

几个自然数的公约数中最大的一个， 叫做这几个自然数的最大公约数。a₁,a₂，……，a_n的最大公约数记作(a₁,a₂，……，an)。例如， 24和36的最大公约数是12, 可以写成(24, 36) =12; 又如， 4, 10, 12的最大公约数是2，可以写成： (4, 10, 12) =2。求n个自然数的最大公约数，可以先把每个数都分解质因数，然后把所有公有的质因数乘起来，就是它们的最大公约数。设a和b为两个自然数， a和b分别有典型分解式a=p1e1p2e2……prer,b=p1d1p2d2……prdr这里p₁, p₂, ……，p_r是互不相同的质数，指数e₁,e₂, ……，e_r,d₁, d₂, ……，dr是非负整数(如果某一个指数为0，则表示相应的质数幂在分解式中不出现), 取m₁为e₁和d₁两非负整数中较小的一个，……，m_r为e_r和d_r两个非负整数中较小的一个， 那么a和b的最大公约数是(a,b) =p1m1p2m2……prmr。例如， 求24与36的最大公约数， 24=22×3. 36=2²×3²。两式中质因数2的指数分别为3和2，取较小的指数2; 两式中质因数3的指数分别为1和2，取较小的指数1，因此，(24,36) =2²×3¹＝12。在实际计算中求几个数的最大公因数可用它们公有的质因数逐次去除，直到它们没有公有质因数为止，再把全部公有的质因数乘起来。例如，求(180,240,300)=

最大公约数

greatest common divisor(GCD)