最大公约数

　　最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为(a，b)，同样的，a，b，c的最大公约数记为(a，b，c)，多个整数的最大公约数也有同样的记号。求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。与最大公约数相对应的概念是最小公倍数，a，b的最小公倍数记为[a，b]。

　　基本信息

　　中文名称最大公约数外文名称Greatest Common Divisor(GCD) 别名Highest Common Factor(HCF)所属学科数论 折叠编辑本段基本介绍最大公约数(greatest common divisor，简写为gcd;或highest common factor，简写为hcf)，指某几个整数共有因子中最大的一个。

　　最大公约数能够整除一个整数的整数称为其的约数(如5是10约数);能够被一个整数整除的整数称为其的倍数(如10是5的倍数);如果一个数既是数A的约数，又是数B的约数，称为A,B的公约数，A,B的公约数中最大的一个(可以包括AB自身)称为AB的最大公约数[1]折叠编辑本段定义如果有一个自然数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余42123÷42=2余3942÷39=1余339÷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)=1gcd(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) = aba与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)。折叠应用贝祖注意：网页中无法显示数学中的脚标! a0,a1,...，a(n-1),a(n) 是数列，r1.r2,...,r(n-1),r(n)也是数列。 r(n-1) 即数列的第(n-1)项 别弄错了。对任意两个整数a、b，设d是它们的最大公约数。那么关于未知数x和y的线性丢番图方程(称为贝祖等式)：贝祖等式，依艾蒂·贝祖命名，是线性丢番图方程。它说明若有整数a、b和其最大公因子d，必存在整数x、y使得： ax + by = d x、y称为贝祖数，可用扩展版辗转相除法求得，但结果不是唯一的。例如12和42的最大公因子是6，便可以写(-3)×12 + 1×42 = 6及4×12 + (-1)×42 = 6。 d其实就是最小可以写成ax + by形式的正整数。辗转相除法是用来求最大公约数的.我们用代数的形式来表达(实质上，算术形式也是可以完全讲得清楚的).给出两个正整数a和b，用b除a得商a0，余数r，写成式子 a=a0b+r，0≤r<b.(1) 这是最基本的式子，辗转相除法的灵魂.如果r等于0，那么b可以除尽a，而a、b的最大公约数就是b. 如果r≠0，再用r除b，得商a1，余数r1，即 b=a1r+r1，0≤r1<r.(2) 如果r1=0，那么r除尽b，由(1)也除尽a，所以r是a、b的公约数.反之，任何一除尽b的数，由(1)，也除尽r，因此r是a、b的最大公约数. 如果r1≠0，则用r1除r得商a2，余数r2，即 r=a2r1+r2，0≤r2<r1.(3) 如果r2=0，那么由(2)可知r1是b、r的公约数，由(1)，r1也是a、b的公约数.反之，如果一数除得尽a、b，那末由(1)，它一定也除得尽b、r，由(2)，它一定除得尽r、r1，所以r1是a、b的最大公约数. 如果r2≠0，再用r2除r1，如法进行.由于b>r>r1>r2>…逐步小下来，而又都是正整数，因此经过有限步骤后一定可以找到a、b的最大公约数d(它可能是1).这就是有名的辗转相除法，在外国称为欧几里得算法.这个方法不但给出了求最大公约数的方法，而且帮助我们找出x、y，使 ax+by=d.(4)在说明一般道理之前，先看下面的例子. 从求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.我们现在来寻求x、y，使 42897x+18644y=79. 由(iv)可知 1817-11×158=79. 把(iii)式的158表达式代入此式，得 79=1817-11(5609-3×1817) =34×1817-11×5609. 再以(ii)式的1817表达式代入，得 79=34×(18644-3×5609)-11×5609 =34×18644-113×5609. 再以(i)式的5609表达式代入，得 79=34×18644-113×(42897-2×18644) =260×18644-113×42897. 也就是x=-113，y=260. 这虽然是特例，也说明了一般的理论.一般的理论是：把辗转相除法写成为 a=a0b+r， b=a1r+r1， r=a2r1+r2， r1=a3r2+r3， ……… r(n-1)=a(n+1)r(n)+ r(n+1)， r(n)=a(n+2)r(n+1). 这样得出最大公约数d=r(n+1).由倒数第二式，r(n+1)可以表为r(n-1)、r(n)的一次式，再倒回一个可以表为r(n-2)、r(n-1)的一次式，…，最后表为a、b的一次式.即把d放在等式的一边，另一边不断代入上一个等式，最后可找出一组(x、y)值，使 ax+by=d. 成立。由此，贝式等式得证。折叠编辑本段程序实现PASCALprogram zuidagongyueshu;var m,n,a,b,r:integer;begin

　　『主程序』write('Input m,n=');readln(m,n);a:=m;b:=n;repeatr:=a mod b;a:=b;b:=r;until r=0;writeln('The greatest common divide is:',a);end。【递归算法】program gcd;var k,a,b:integer;function gcd(a,b:integer):integer;beginif a mod b=0 then exit(b)else gcd:=gcd(b,a mod b);end;beginreadln(a,b);k:=gcd(a,b);writeln(k);end.C语言int gcd(int a,int b){int temp;if(a<b)/*交换两个数，使大数放在a上*/{temp=a;a=b;b=temp;}while(b!=0)/*利用辗除法，直到b为0为止*/{temp=a%b;a=b;b=temp;}return a;}折叠编辑本段算法折叠欧几里德算法和扩展欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的欧几里得最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b)证明：a可以表示成a = kb + r，则r = a mod b假设d是a,b的一个公约数，则有d|a, d|b，而r = a - kb，因此d|r因此d是(b,a mod b)的公约数假设d 是(b,a mod b)的公约数，则d | b , d |r ，但是a = kb +r因此d也是(a,b)的公约数因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证欧几里德算法就是根据这个原理来做的，其算法用C++语言描述为：void swap(int & a, int & b){int c = a;a = b;b = c;}int gcd(int a,int b){if(0 == a ){return b;}if( 0 == b){return a;}if(a > b){swap(a,b);}int c;for(c = a % b ; c > 0 ; c = a % b){a = b;b = c;}return b;}另一个求三个以上数的最大公约数拓展算法：(也是运用欧几里德算法原理，参考设计作者：苏祥)#include<STDIO.H>main(){long i,s[100],L,a,b,c,k=1;char ch;for(i=0;;i++){printf("输入一个数：");scanf("%ld%c",&s,&ch);if(ch=='n')break;}if(s[1]>s[0]){L=s[1];s[1]=s[0];s[0]=L;}a=s[0];b=s[1];do{c=a%b;if(c==0)if(b==1)break;else{k++;if(k<=i){if(s[k]<b){L=s[k];s[k]=b;b=L;}a=s[k];}}else{a=b;b=c;}图一}while(k<=i);printf("最大公约数为：%ld",b);}程序只是用了数组、循环、选择语句等C语言语法，各位读者可以自己学习、运行一下这个程序看看有何效果。下面讲一下程序计算原理：刚开始，程序对输入的第一个和第二个数进行最大公约数运算，然后把所求得的最大公约数与输入的第三个数进行最大公约数运算，然后再把所求得的最大公约数与输入的第四个数进行最大公约数运算，以此类推，直到最后一个为止。注意：输完一个数后按回车键，最后一个数后面一定要加“n”，如图一中的第五行中的“6n”。折叠Stein算法欧几里德算法是计算两个数最大公约数的传统算法，他无寻找最大公约数论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。 考虑现在的硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。为了说明Stein算法的正确性，首先必须注意到以下结论：gcd(a,a) = a，也就是一个数和他自身的公约数是其自身gcd(ka,kb) = k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除C++/java 实现// c++/java stein 算法int gcd(int a,int b){if(a < b){int temp = a;a = b;b=temp;}if(0==b)//the base casereturn a;if(a%2==0 && b%2 ==0)//a and b are evenreturn 2*gcd(a/2,b/2);if ( a%2 == 0)// only a is evenreturn gcd(a/2,b);if ( b%2==0 )// only b is evenreturn gcd(a,b/2);return gcd((a+b)/2,(a-b)/2);// a and b are odd}折叠分解质因数利用分解质因数的方法可以简便的求出两个数的最大公约数，如：126=2×3×3×7396=2×2×3×3×11126和396的最大公因数是=2×3×3=18