擴(kuò)展歐幾里德定理

擴(kuò)展歐幾里德定理對(duì)于與不完全為0的非負(fù)整數(shù)a，b，gcd（a，b）表示a，b的最大公約數(shù)那么存在唯一的整數(shù)x，y使得gcd（a，b）=ax+by

“擴(kuò)展歐幾里德原理”是由“歐幾里德原理”擴(kuò)展來(lái)的（PS：廢話），有的書(shū)上叫“費(fèi)蜀（Bezout）定理”，總之有個(gè)這個(gè)事

c=gcd(a,b)表示a，b兩數(shù)的最大公約數(shù)，則存在：ax+by=c一定存在整數(shù)x，y使等式成立

先說(shuō)一下“歐幾里德原理”，其實(shí)就是“輾轉(zhuǎn)相除法”，也就是中國(guó)老祖先的“更相減損之術(shù)”，這個(gè)算法的主要目的是求出兩個(gè)數(shù)的最大公約數(shù)，具體是一個(gè)遞歸的過(guò)程，簡(jiǎn)單說(shuō)來(lái)是：

gcd（a,b）=gcd(b,amodb)

終止條件是：gcd（a,b）中的amodb=0，然后輸出b

證明“歐幾里德原理（算法）”：（如果看不明白就跳過(guò)，本來(lái)我是不想寫(xiě)的，如果你達(dá)到高中畢業(yè)的數(shù)學(xué)水平就看一看，否則就會(huì)像我一樣看半天明白了一點(diǎn)）（PS：本人高二）

設(shè)a,b,c為三個(gè)不全為零的整數(shù)，且有整數(shù)t使：a=b*t+c，則a、b與b、c有相同的公約數(shù)，因而，gcd(a,b)=gcd(b,c)，即gcd(a,b)=gcd(b,a-b*t)（證明這個(gè)：d是a,b的公約數(shù)，則設(shè)a=d*i，b=d*j，由a=b*t+c=>c=a-b*t=>c=d*(i-j*t)，所以，d也是c的公約數(shù)）

歐幾里德算法（輾轉(zhuǎn)相除法）的工作過(guò)程如下：1、a=b*q[1]+r[1]2、b=r[1]*q[2]+r[2]3、r1=r[2]*q[3]+r[4]...n、r[n-2]=r[n-1]*q[n]+r[n]n+1、r[n-1]=r[n]*q[n+1]+r[n+1]此時(shí)，r[n+1]=0，因?yàn)槊看螏в喑?，余?shù)至少減一（因?yàn)橛鄶?shù)比除數(shù)小，這里以第一個(gè)式子為例，這個(gè)式子相當(dāng)于a除以b商q[1]余r[1]，這里一定存在b>r[1]），即b>r[1]>r[2]>r[3]>…>r[n]>r[n+1]=0，而b為有限數(shù)，因此必有一個(gè)最多不超過(guò)b的正整數(shù)n存在，使得r[n]>0，而r[n+1]>0，故有r[n]=gcd(r[n+1],r[n])=gcd(r[n],r[n-1])=…=gcd(r[2],r[1])=gcd(r[1],b)=gcd(a,b)

這就是“歐幾里德原理（算法）”的證明

擴(kuò)展“歐幾里德原理（算法）”的證明：（同樣，如果沒(méi)有一定的數(shù)學(xué)水平也是看不了的）

其實(shí)，剛才已經(jīng)證明了，因?yàn)榫褪禽氜D(zhuǎn)相除法的遞推過(guò)程，大家如果不明白的話，就自己遞歸一下（小提示：推出的等式應(yīng)該是這樣的——c=r[n]=ax+by）

有一種特殊情況，就是當(dāng)gcd(a,b)=1時(shí)，存在ax+by=1，x,y存在整數(shù)解

結(jié)論（大家都可以記住的）：a*x+b*y=gcd（a，b）x，y一定有整數(shù)解粗略證明存在唯一的整數(shù)x，y使得gcd（a，b）=ax+bya是gcd的倍數(shù)，可設(shè)a=i*gcdb是gcd的倍數(shù)，可設(shè)b=j*gcd現(xiàn)在要用整數(shù)個(gè)a,b湊出gcd來(lái)為了分析方便，不妨設(shè)a>b不難看出：a-b可被表示出來(lái)，且它也是gcd的倍數(shù)因此gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)實(shí)際上如果a=n個(gè)b+余數(shù)，則可以把n個(gè)b都減去再怎么減，都是gcd的倍數(shù)當(dāng)n足夠大時(shí)：a-nb=amodb因此gcd(a,b)=gcd(b,amodb)歐幾里德定理證明結(jié)束從上邊證明過(guò)程可以看出a-b,a-2b,a-3b,…a-nb都可以被表示出來(lái)，且x,y都是整數(shù)解當(dāng)n足夠大時(shí)：a-nb=amodb即amodb可被表示出來(lái)，且x,y為整數(shù)解gcd(a,b)=gcd(b,amodb)等價(jià)，且x,y都為整數(shù)解相同子問(wèn)題最終gcd可以被表示出來(lái)ab過(guò)河擴(kuò)展歐幾里德定理對(duì)于與不完全為0的非負(fù)整數(shù)a，b，那么存在唯一的整數(shù)x，y使得gcd（a，b）=xa+yb如果a,b互質(zhì)，則1=xa+yb存在整數(shù)解(x,y)1都能表示了，那其它的數(shù)呢？所有的正數(shù)L都能被表示成ax+by！細(xì)節(jié)x,y可能為負(fù)，所以L>=a*b就可以保證x,y為正了。結(jié)論：若青蛙每次只能跳a和b,則任意點(diǎn)M后距離超過(guò)L的每個(gè)點(diǎn)都可被M覆蓋到。在兩個(gè)石頭間轉(zhuǎn)移狀態(tài)方程變