最大公約數

　　，也稱最大公因數、最大公因子，指兩個或多個整數共有約數中最大的一個。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