大公約數檢視原始碼討論檢視歷史
| 大公約數 | |
|---|---|
大公約數，也稱最大公因數、最大公因子，指兩個或多個整數共有約數中最大的一個。a，b的最大公約數記為（a，b），同樣的，a，b，c的最大公約數記為（a，b，c），多個整數的最大公約數也有同樣的記號。求最大公約數有多種方法，常見的有質因數分解法、短除法、輾轉相除法、更相減損法。與最大公約數相對應的概念是最小公倍數，a，b的最小公倍數記為[a，b]。
基本介紹
最大公約數（greatest common divisor，簡寫為gcd；或highest common factor，簡寫為hcf)，指某幾個整數共有因子中最大的一個。
能夠整除一個整數的整數稱為其的約數（如5是10約數）；[1] 能夠被一個整數整除的整數稱為其的倍數（如10是5的倍數）；
如果一個數既是數A的約數，又是數B的約數，稱為A,B的公約數，A,B的公約數
中最大的一個（可以包括AB自身）稱為AB的最大公約數
定義
如果有一個自然數a能被自然數b整除，則稱a為b的倍數，b為a的約數。幾個自然數公有的約數，叫做這幾個自然數的公約數。公約數中最大的一個公約數，稱為這幾個自然數的最大公約數。
例： 在2、4、6中，2就是2，4，6的最大公約數。[2] 早在公元前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。
【遞歸算法】
program gcd;
var k,a,b:integer;
function gcd(a,b:integer):integer;
begin
if a mod b=0 then exit(b)
else gcd:=gcd(b,a mod b);
end;
begin
readln(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;=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 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}
分解質因數
利用分解質因數的方法可以簡便的求出兩個數的最大公約數，
如：
126=2×3×3×7
396=2×2×3×3×11
126和396的最大公因數是=2×3×3=18