最大公约数_在线百科全书查询
最大公约数
最大公约数（greatest common divisor，简写为gcd；或highest common factor，简写为hcf)，指某几个整数共有因子中最大的一个。
基本信息
拼音：zuì dà gōng yuē shù
英语：greatest common divisor，简写为gcd；或highest common factor，简写为hcf
法语：Plus grand commun diviseur
德语：Größter gemeinsamer Teiler(ggT)
定义
如果有一个自然数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)。
应用贝祖等式来计算
注意：百度中无法显示数学中的脚标！ 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． 成立。由此，贝式等式得证。
计算机程序实现
PASCAL
program zuidagongyueshu;
var m,n,a,b,r:integer;
begin『主程序』
write(''Input m,n='');
readln(m,n);
a:=m;
b:=n;
repeat
r:=a mod b;
a:=b;
b:=r;
until r=0;
writeln(''The greatest common divide is:'',a);
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;
}
算法
1、欧几里德算法和扩展欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数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[i],&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”。
2．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(ab{
int temp = a;
a = b;
b=temp;
}
if(0==b)//the base case
return a;
if(a%2==0 && b%2 ==0)//a and b are even
return 2*gcd(a/2,b/2);
if ( a%2 == 0)// only a is even
return gcd(a/2,b);
if ( b%2==0 )// only b is even
return gcd(a,b/2);
return gcd((a+b)/2,(a-b)/2);// a and b are odd
}
歌曲
《最大公约数》
= 最大公约数 =
RADWIMPS
译&制：小夏
仆の二歩は君の三歩 【我的两步是你的三步】
仆の四歩は君の六歩 【我的四步是你的六步】
そんな风にこれからも 【从现在起一直】
歩いていければいいと思うんだ 【这样得走下去就好】
君が想うこと 【你想的事情】
それは同时に仆が想うこと 【就是我同时在想的事情】
そんな奇迹は必要ないよ 【这样的奇迹没有必要】
タダであげるって言われても 【就算是白给我也不要】
パパとママが 【爸爸和妈妈】
心だけは隠して生んでくれたのには 【之所以要把心脏藏在身体里生出我们】
それなりの理由があった 【是有其理由的】
だから二人は【所以我们2人】
忘れないように确かめ合って 【为了不忘记而互相确认】
途切れそうな夜を繋いだんだ 【把就要中断的夜串起来】
溢れないように分け合って 【为了不溢出来而分开承担】
だからそう 【所以说】
何を与えるでもなく 【并不是给予什么】
无理に寄りそうわけでもなく 【也不是硬缠在一起】
つまりは探しにいこう 【总之我们去寻找吧】
二人の最大公约数を 【2人的最大公约数】
声にならぬ想いは 【无法说出的心情】
无理に言叶にするでもなく 【不必勉强表达出来】
いつか仆も分かる时 まで???【等到我也理解的时候…】
君の心は仆の2倍 【你的心是我的2倍】
仆の小指は君の2倍 【我的小指是你的2倍】
一つ分かっててほしいのは 【想让你明白的一点是】
爱されたい気持ちは君の5倍 【我被爱的感觉是你的5倍】
「别れよう」って言われる2秒手前 【再被说出"分手吧"的2秒前】
涙はかろうじてまつ毛の手前 【你眼泪就要溢出睫毛之前】
本日100回目のごめんね【我说了今天的第一百次对不起】
呆れて君は 笑ったね 【发呆的你 笑出来了呢】
别れる理由3つあるなら 【如果有3个分手的理由】
别れない理由100探すから 【我就会去找出100个不能分手的理由】
カランコロン カランコロン きっと 【咔哒咔哒*2（木屐声） 一定哦】
とれそうなポッケ覗いたんだ 【看穿了就要解开的糊涂】
消えそうな想い诘め込んだんだ 【填满了快要消失的感觉】
崩れそうな夜も超えたんだ 【也跨越过了快要崩溃的夜】
二人で 【两个人一起】
仆が君に描く想い 【我对你描述的想法】
君が仆に抱く想い 【你对我抱有的想法】
违ったって 【就算不一样】
一つじゃなくて いいと思う 【不是一种也无所谓】
分かり合えない想いは 【无法互相了解的想法】
无理に颔くためではなく 【不必勉强点头认同】
いつかの楽しみに 【留着来期待以后某时…】
そう とっとこう 【没错 就先握着它吧】
=歌词?作曲：野田洋次郎=
何を求めるでもなく 【不是去求得什么】
无理に意味を添えるでもなく 【不必勉强增添什么意义】
つまりは探しにゆこう 【总之我们去寻找吧】
二人の最大公约数を 2人的最大公约数】
仆は仆で君は君 【我是我 你是你】
その间には无限に 【这之间应该】
あるはずだよ 【有无限的】
二人だけの公约数 【只属于2人的公约数】
君が8なら仆は2になる 【我是8的话你就是2】
仆が10なら君は5になる 【我是10的话你就是5】
君+仆は何だろう 【我+你=什么呢】
仆－君は何だろう 【我-你=什么呢】
雨のち晴れのち昙り【雨转晴转多云】
仆のち君のちつまり 【我然后你然后总之】
そうやって これからだって 【就这样 从今往后也】
やっていこう 【就这样下去吧】
