在幾何原本卷十命題三中已知兩個可公度的量計算它們的最大公度量歐幾里得給出了遞歸解法設(shè)兩條線段a,b可公度如果它們相等則最大公度就是其中任意一條線段此時算法返回a作為結(jié)果如果線段a比b長就用圓規(guī)不斷從a中截去b然后求截端后的線段a和b的最大公度如果線段b比a長就反過來不斷從b中截去a,然后求截端后的線段b和a的最大公度.由于ab時,a mod b a公式可以進一步寫成示意如下計算gcd(24, 110)2的過程程序?qū)崿F(xiàn)gcda b gcdb a % b gcd(a%b, b %(a%b)) ....先上輾轉(zhuǎn)相除法歐幾里得算法的三種代碼實現(xiàn)#include stdio.h #include stdlib.h int gcd1(int a, int b) { int ret; while(1) { if(a b) { a a%b; if(a 0) { ret b; break; } } else { b b %a; if(b 0) { ret a; break; } } } return ret; } int gcd2(int a,int b) { if(b 0) return a; return gcd2(b,a%b); } int gcd3(int a,int b) { while(b){ int t b; b a%b; a t; } return a; } int main(void) { int a, b; a 100; b 45; printf(%s line %d, res1 %d, res2 %d, res3 %d.\n, __func__, __LINE__, gcd1(a, b), gcd2(a, b), gcd3(a, b)); return 0; }下面用一幅圖示解題過程圖中藍色的矩形單元表示一個最小公約的單元。它具有以下性質(zhì)1.以最小公約表示的兩個原數(shù)字互質(zhì)。這是必然反證法如果不互質(zhì)則可以提取一個共同的因子重新定義最小公約單元直到表示為互質(zhì)比如圖中的8和3互質(zhì)。2.輾轉(zhuǎn)相除的每個階段的兩個數(shù)字也均互質(zhì)證明過程類似反正法即可當前輾轉(zhuǎn)階段如果存在共同的約數(shù)則必然傳遞到之前的階段也都有同樣的約數(shù)所以同理最小公約單元也要重新定義直到每級輾轉(zhuǎn)互質(zhì)?；谝陨蟽蓚€嚴密的邏輯輾轉(zhuǎn)相除一定能夠找到組成兩個數(shù)字的最基本的公約塊兒它是兩個數(shù)字共有的零件。擴展-求最小公倍數(shù)既然上一步已經(jīng)計算得到了最小公約數(shù)并且得到了以最小公約表示的兩個原數(shù)字互質(zhì)的推論就不難得到計算最小公倍數(shù)的公用公式。通用算法已知數(shù)字m,n的最大公約數(shù)是g,則m/g, n/g互質(zhì)兩個互質(zhì)的數(shù)的最小公倍數(shù)就是兩個質(zhì)數(shù)之積所以最小公倍數(shù)為由于單元為g,所以最小公倍數(shù)的真實值為#include stdio.h #include stdlib.h int gcd1(int a, int b) { int ret; while(1) { if(a b) { a a%b; if(a 0) { ret b; break; } } else { b b %a; if(b 0) { ret a; break; } } } return ret; } int gcd2(int a,int b) { if(b 0) return a; return gcd2(b,a%b); } int gcd3(int a,int b) { while(b){ int t b; b a%b; a t; } return a; } int lcm1(int a, int b) { int g_c_d gcd1(a, b); return a*b/g_c_d; } int lcm2(int m, int n) { int mn, r ; if(mn){ mn m ; m n ; n mn; } mn m * n ;//倆個數(shù)的乘積 r m % n ; while(r!0){ m n ; n r ; r m % n ; } return mn/n; //n為最大公約數(shù) } int main(void) { int a, b; a 100; b 45; printf(%s line %d, res1 %d, res2 %d, res3 %d, lcm1 %d, lcm2 %d.\n, __func__, __LINE__, gcd1(a, b), gcd2(a, b), gcd3(a, b), lcm1(a, b), lcm2(a,b)); return 0; }main line 84, res1 5, res2 5, res3 5, lcm1 900, lcm2 900.圖解LCM of 32, 48 and 72 2 × 2 × 2 × 2 × 2 × 3 × 3 288關(guān)于兩個互質(zhì)數(shù)的最小公倍數(shù)是兩數(shù)之積可以證明如下假設(shè)a,b兩數(shù)互質(zhì)也就是兩數(shù)沒有1以外的公約數(shù)則最小公倍數(shù)是axb.不失一般情況假設(shè)ab,則a的倍數(shù)從小到大排列為a,2a,3a,......(b-1)a, ba;在ba之前的所有a的倍數(shù)中假設(shè)ka(1kb)同樣也是b的倍數(shù)則是整數(shù)。由于a,b互質(zhì)則a/b不可能存在導致結(jié)果為整數(shù)的因子所以只有k存在這個因子但是k小于b,所以同樣得到結(jié)論這樣的K不存在這樣最小的公倍數(shù)只能是ab了結(jié)論得證?；蛘哂梅醋C法我們知道ab一定是公倍數(shù)要證明是最小其它公倍數(shù)對最小公倍數(shù)之間一定可以整除其他公倍數(shù)之間不一定所以假設(shè)ab/n是其最小公倍數(shù)則根據(jù)ab/n整除a,b可以推理出n是a,b的公因數(shù)這和a,b互質(zhì)矛盾。上面那句雖然結(jié)論正確,但是推理顯然是錯誤,反例如下40*5/25 8. 但是40和5任何一個都不能整除25,所以得不到ab/n整除,n是a,b公因數(shù)的結(jié)論.倒是可以證明:ab/n為整數(shù),則a,b一定不互質(zhì),因為假如a,b互質(zhì),則設(shè)mab,ab為m的一個質(zhì)因數(shù)分解.根據(jù)算數(shù)基本定理,這個指因數(shù)分解唯一.如果存在cab/nm/n,則必然存在mcn,n小于a,b的情況下則m又引入了一個非a,b的因子n和c,不管n,c是質(zhì)數(shù)還是合數(shù),都違背了算數(shù)基本定理的唯一性要求.所以得證.PS只有當a,c互質(zhì)且ab/c整除時才能得出b/c整除的結(jié)論40*5/25由于無論40或者5都和25不互素所以不適用于這個結(jié)論無論40或者5都無法整除25.關(guān)于這個定義初等數(shù)論中的描述如下如果a,b和c是正整數(shù)滿足(a,b)1.且a|bc,則a|c.證明如下由于(a,b)1也就是a,b互素存在整數(shù)x,y,使得axby1,等式兩邊同時乘以c得到acxbcyc.由于bc能夠整除a所以a*cxbc*y實際上是兩個能夠整除a的整數(shù)的線性組合cx,y為系數(shù)所以a*cxbc*y也能夠整除a. 而a*cxbc*y等于什么呢它就等于c所以a|c. 結(jié)論得到證明?；蛘咄ㄟ^歐幾里德定理證明素數(shù)的唯一分解角度(a,b)1.且a|bc如果將a,b,c三個數(shù)字進行歐幾里德素數(shù)分解則a,b互素所以它們一定沒有除1以外的共因子。 因此c必須包含所有a的素因子并且唯一因此a一定能夠整除c.總結(jié)基本原理兩個整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)的差的最大公約數(shù)。個人解析若A、B有最大公約數(shù)KA B)則A、B、A - B、A mod BA / B的余數(shù)都是K的倍數(shù)。即余數(shù)A - B和 B 的最大公公約數(shù)也是 K 。由此遞歸可知當 A mod B 0即 A 是 B 的倍數(shù)時此時B 即為 K 。實際上存在如下定理兩數(shù)最大公約數(shù)與最小公倍數(shù)的積等于兩數(shù)之積用公式表示就是當時實際上有更普遍的結(jié)論最大公因數(shù)*最小公倍數(shù)pq。這個證明過程也很簡單假設(shè)a,b互質(zhì)那么它們的最小公倍數(shù)是ab,最大公因數(shù)1滿足題設(shè)。當整數(shù)a和b的最小公倍數(shù)就是他們的乘積ab時則他們也是互素的。假如a,b不互質(zhì)則必然存在質(zhì)數(shù)p,q (p,q)1,sgcd(a,b),使的a sp,bsq, s為整數(shù)。則最小公倍數(shù)為spq,最大公約數(shù)為s.s*spq sp*sq a*b同樣滿足題設(shè)。這個結(jié)論用整數(shù)的質(zhì)因數(shù)分解更加容易。這個證明需要的引理(p,q)1則lcmpq可以根據(jù)算數(shù)基本定理證明(p,q)1說明,p,q的素分解式中不存在相同的素數(shù)否則他們的(p,q)1必定不成立要么某個相同的素數(shù)要么某幾個相同的素數(shù)之積所以他們的lcm一定是所有p,q的素因子之積而素因子又不存在交集所以lcm一定是pxq.圖形化表示輾轉(zhuǎn)相除獲取最大公約數(shù)證明: gcd(a,b) gcd(b, a%b).設(shè)cgcd(a,b). 則a mcb nc并且m,n互素假如m,n有公因子則一定可以抽取出來和c作乘積產(chǎn)生新的最大公約數(shù)而前提我們已經(jīng)設(shè)定c為最大公約了所以一定有辦法讓m,n互素).aqbrmcqncr rmc-qnc (m-qn)c.所以c仍然是a%b的因子。又因為m-qn和n互素證明如下假如m-qn和n有非1公因子s,gcd(n, m-qn) s, nxs, m-qnys.則r(m-qn)c ysc, aqxscysc, b xsc.所以a,b的公因子是少是sc而非c. 或者這樣理解m-qnx*s, ny*sm(qyx)s,所以m,n有公因子s和m,n互素矛盾所以m-qn和n互素。所以bnc和a%b(m-qn)c的最大公因子也是c否則n和m-qn一定能抽取另一個公因子和C相乘得到新的最大公因子矛盾。所以 gcd(a,b) gcd(b, a%b).b, a%b和a,b有相同的最大公因子。從下圖也可以看出如果某級運算出現(xiàn)了新的更大的公約數(shù)則這個公約數(shù)一定會反推回a,b導致更新前提所以GCD的運算會保持最大公約數(shù)不變。下圖展示了歐幾里得算法的一個幾何解釋反復剪掉正方形用最終的小正方形鋪滿整個原圖。以上圖形化證明過程的代碼表達如下設(shè)初始兩個自然數(shù)為a,b, 并且abb非0可以證明存在兩個唯一的整數(shù) q 和 r滿足 a q*b r , q 為整數(shù)且0 ≤ |r| |d|。其中q 被稱為商r 被稱為余數(shù)a,b分別被除數(shù)和除數(shù)取余運算求取的就是這個余數(shù)r。只要a,b是可公度的這些式子不會無限列下去從r0開始每一步r(n1)是r(n)的余數(shù)r(n1) r(n),但是r0是自然數(shù)起始值是有限的所以這個過程不可能無限進行下去最后一步總歸能夠整除最后一步的除數(shù)r(n2)就是最大公約數(shù)。往回迭代.........下一步證明任何a,b的公度c,一定可以度量r(n2).由于c是公度因此a,b都可以用它來表示m,n為自然數(shù)這樣上面的式子可以寫成.....所以r0,r1,.....r(n),r(n1), r(n2)都可以由c來公度所以r(n2)是最大公度。以本片開頭的例子為例計算110和24的最大公約數(shù)a110,b24.a110,b24.1104*2414.241*1410.141*104.102*42.42*2 0.定理得證。裴蜀定理裴蜀定理或貝祖定理得名于法國數(shù)學家艾蒂安·裴蜀說明了對任何整數(shù)a ,b 和它們的最大公約數(shù)d,關(guān)于未知數(shù)x和y 的線性不定方程稱為裴蜀等式):若a ,b 是整數(shù),且gcd(a,b)d,那么對于任意的整數(shù)x ,y , axby都一定是d的倍數(shù)特別地一定存在整數(shù)x,y使axbyd成立,對于a,b互素的情況一定存在x,y使的axby1.可以這樣抽象理解每次a mod bm余r的過程都是所以.......也就是說通過GCD計算最大公約數(shù)的過程就是計算a,b線性組合的過程系數(shù)分別為x,yraxby.計算gcd(a,b)axby所需的x,y:......方程是不定方程無法限定x,y.符合要求的x,y可以構(gòu)成一個一維空間在一條直線上但是滿足x,y為整數(shù)的并不多。另外對于axbyk形式的直線如果a,b互質(zhì)則K可以為任意整數(shù)但是如果a,b的最小公因數(shù)大于1則小于其最公因數(shù)的數(shù)字不能被表示?？梢院唵巫C明如下axbyk, anc, bmc. 則ncxmcykc(nxmy)k,n,m互質(zhì)所以能表示任意整數(shù)。((m,n)1,則存在 mxby1,兩邊同時乘以任意整數(shù)則可以表示任意數(shù)在乘以一個c則只能表示sc了,s是整數(shù)。不能表示任意整數(shù)了。在使用歐幾里德算法計算GCD時每一步得到的兩個數(shù)字GCD都和初始兩個數(shù)字的GCD相同所以每一步的兩個數(shù)字p,q均可應(yīng)用貝祖定理。假設(shè)第k層則第k1層:所以展開:對照第K層所以并且在最后一次的迭代中一定是,編程得到#includestdio.h #includestdlib.h //注意ab必須互質(zhì) int ex_gcd(int a, int b, int *x, int *y) { int x1, y1, r; if(b 0) { if(a! 1) { printf(%s line %d, error, a %d is not 1 in last recursive.\n, __func__, __LINE__, a); exit(-1); } *x 1; *y 0; return a; } r ex_gcd(b, a % b, x1, y1); *y x1 - a / b * y1; //根據(jù)推導的每層xy的關(guān)系而來 *x y1; //同上 return r; } int main(void) { int a, b, x, y; while(~scanf(%d%d, a, b)){ int ret ex_gcd(a, b, x, y); printf(x : %d, y : %d, ret %d\n, x, y, ret);//其實ret就是ab的最大公約數(shù) printf(%d * %d %d * %d %d\n, a, x, b, y, a * x b * y); } return 0; }下圖展示了兩個整數(shù)6和9的最大共因子是兩個整數(shù)的線性組合的最小正整數(shù)這個事實程序中關(guān)于輸入的兩個數(shù)必須互質(zhì)的條件可以拿掉因為互質(zhì)的情況下1是兩個數(shù)的最大公約數(shù)拿掉的話程序的通用性更強得到的x,y會普適下列形式的貝祖定理axby gcd(a,b)#includestdio.h #includestdlib.h int ex_gcd(int a, int b, int *x, int *y) { int x1, y1, r; if(b 0) { #if 0 if(a! 1) { printf(%s line %d, error, a %d is not 1 in last recursive.\n, __func__, __LINE__, a); exit(-1); } #endif *x 1; *y 0; return a; } r ex_gcd(b, a % b, x1, y1); *y x1 - a / b * y1; //根據(jù)推導的每層xy的關(guān)系而來 *x y1; //同上 return r; } int main(void) { int a, b, x, y; while(~scanf(%d%d, a, b)){ int ret ex_gcd(a, b, x, y); printf(x : %d, y : %d, ret %d\n, x, y, ret);//其實ret就是ab的最大公約數(shù) printf(%d * %d %d * %d %d\n, a, x, b, y, a * x b * y); } return 0; }比如使用程序計算滿足100和60的最大公因數(shù)20的x,y:貝祖定理的XY是多值的具體看如下分析多值性從程序中可見端倪遞歸結(jié)束條件成立時*x 1;*y 0;其實是表達滿足最后一級的兩個輸入gcd(a,b) 和 0的 x,y可以看到滿足gcd(a,b) * x 0 *y gcd(a,b)的解有無數(shù)多組只要滿足x1, y等于任何值都沒有關(guān)系。程序中的遞歸結(jié)束條件修改為*y 100;程序仍然能夠找到另一組x,y滿足 gcd(100,60) * x 0 *y gcd(100,60)程序結(jié)論和證明完美統(tǒng)一。GCD的另一個理解無論怎樣如果 (a,b)d的話則后續(xù)每一部大數(shù)減小數(shù)與某個整數(shù)乘積的步驟得到的結(jié)果都是d的倍數(shù)并且一定能夠取到d的1倍的程度看下圖如果最后一步r4kxr5, 如果r5不是1xd, 而是nxd那么根據(jù)公式反推回去一定會得到(a,b) nd 而不是(a,b) d所以GCD運算最后一步r5一定是1xdd.完善證明證明過程中依據(jù)“每次都保證余數(shù)小于除數(shù)但是余數(shù)不可能小于0由于起始值是有限的所以最終算法一定會停止” 為什么不會出現(xiàn)無限接近0但是不為0的情況算法為什么一定會停止呢a,b可公度這一前提到底保證了什么?可以利用自然數(shù)的良序原理(well-ordering principle)說明歐幾里得算法一定會終止最小數(shù)原理是自然數(shù)所具有的一種基本性質(zhì)即任何非空的自然數(shù)集中都有最小的自然數(shù)該原理可以推廣到整數(shù)集有理數(shù)集。完整表達是良序原理指出自然數(shù)集的每個非空子集都有個最小元素即自然數(shù)在其標準的大小關(guān)系下構(gòu)成一良序集。應(yīng)用-判斷鏈表中存在環(huán)路判讀鏈表有環(huán)路的快慢指針經(jīng)典算法的數(shù)學基礎(chǔ)基于以上討論算法的邏輯是快慢指針算法是通過兩個指針慢指針每次移動一步快指針每次移動兩步如果兩個指針最終相遇那么鏈表就存在環(huán)。只要慢指針的速度為1快指針的速度可以是任意大于1的值我們可以通過以下數(shù)學證明來說明這個算法的正確性假設(shè)環(huán)鏈表的長度為O慢指針每次移動1步快指針每次移動s步經(jīng)過n步后相遇則列出相遇狀態(tài)的方程為也就是說所以n表示算法進行的步數(shù)我們可以取任意自然數(shù)表示算法結(jié)束時走了多少步為了證明這個算法對任意s都有效我們可以讓n O,也就是步數(shù)等于鏈表長度這個時候sk1,也就是說s可以取任意大于1的自然數(shù)算法都成立最差最差我在終點等你。2025/03/30 update:前面的證明貌似存在問題確實存在即便存在環(huán)路算法仍然檢測不出來相遇的情況比如下圖環(huán)路長度為2快慢節(jié)點速度分別為1和3這樣每步行動后距離變化2 mod 20也就是距離永遠不變永遠是初始距離1這樣快慢節(jié)點永遠不會相遇。每次快指針相對于慢指針移動2步設(shè)初始距離為d則每步間距變化為 d-(d2)mod 2 d所以如果初始距離d不為0即便鏈表中存在環(huán)快慢指針也不會相遇算法失效。只要初始距離d0從同一個位置出發(fā)首次相遇不算在內(nèi)無論環(huán)長多少或者快慢指針速度幾何算法總會有效的。最大公因數(shù)的性質(zhì)兩個整數(shù)的最大公因數(shù)確實是所有其他公因數(shù)的倍數(shù)證明如下根據(jù)貝祖定理存在整數(shù)x和y使得ax by g。如果另一個因數(shù)d是a和b的公因數(shù)那么d | ad | b所以d也整除ax by即d | g。因此d | g即存在整數(shù)k使得g d * k。這就意味著g是d的倍數(shù)也就是g是每個公因數(shù)d的倍數(shù)。所以結(jié)論成立。所以兩個整數(shù)的最大公因數(shù)確實是所有其他公因數(shù)的倍數(shù)因為每個公因數(shù)都能整除最大公因數(shù)從而最大公因數(shù)就是它們的倍數(shù)。且有其中且則證明N表示包括0的自然數(shù)集合N*表示排除0的自然數(shù)集合。如何計算三個整數(shù)a,b,c的的最大公約數(shù)要計算三個整數(shù) a、b、cc的最大公約數(shù)GCD可以分兩步進行利用兩次歐幾里得算法:GCD(a,b,c)GCD(GCD(a,b),c)貝祖定理的證明參考下面這篇文章https://blog.csdn.net/tugouxp/article/details/146010944?sharetypeblogdetailsharerId146010944sharereferPCsharesourcetugouxpspm1011.2480.3001.8118九章算術(shù)中對GCD算法的描述九章算術(shù)是中國傳統(tǒng)數(shù)學的重要教科書其全書問題共分九類有246問和202術(shù)匯總了中國先秦至漢朝的數(shù)學成就其中就有對GCD算法的描述GCD算法在書中被稱為“約分術(shù),其算法描述為月份術(shù)曰”可半者半之不可半者副置分母子之數(shù)以少減多更相減損求其等也以等數(shù)約之“。翻譯后是約分算法分子分母都是偶數(shù)的可以用2約簡否則將分母與分子列在一起然后用大數(shù)減去小數(shù)將差與上一步的減數(shù)再次相減不斷重復直到差與減數(shù)相等為止這個相等的數(shù)字就是他們的最大公約數(shù)然后就可以用最大公約數(shù)區(qū)約簡分子和分母了。小時候都做過一類應(yīng)用題用兩種大小的指定杯子裝出定量的水這類題在某種情況下無解比如如果兩個杯子的最大公因子不能整除要求裝出的水量此時無解如果兩個杯子互質(zhì)則可以裝出所有整數(shù)量的水比如用5L的杯子和6L的杯子裝出3L的水的過程如下事實上對于aL和bL杯子裝出c L水的問題所有滿足 axbyc 的整數(shù)解 (x,y)都對應(yīng)一個可行的用a,b升的桶倒出c升水的方案。參考資料無理數(shù)存在性的幾何證明-CSDN博客初等數(shù)論中整除性規(guī)律證明-CSDN博客歐幾里得定理的證明-CSDN博客初等數(shù)學的整除性規(guī)律證明-CSDN博客[深入淺出C語言]理解取整、取余和取模 - 知乎https://zh.wikipedia.org/wiki/%E7%AE%97%E6%9C%AF%E5%9F%BA%E6%9C%AC%E5%AE%9A%E7%90%86結(jié)束