擴(kuò)展歐幾里得算法詳細(xì)舉例解析

擴(kuò)展得算？②amodba-[a/b]b（[a/b]Pascaladivb）a|bmoda=0③(a,b)表示a和b的最大公約（這很重要現(xiàn)在證明一個(gè)重要的定理：(a,b)是a和b的最小的正線性組合例：a=6b=4，最小正線性組合為1*a+(-1)*b=2=(a,b)證明設(shè)(a,b)為d，ab的最小的正線性組合為∵d|a∴d|samods=a- =a- =a(1-[a/s]x)-ab的線性組∵amods<s，amodsab∴amods=0s|a同理由s|b∴s為a,b的公約∴d=s。證由這條定理易推知：若d|a且d|b，則d|Euclid首先先提出一個(gè)定理：(a,b)=(b,a- 為正整數(shù)）證明 (b,a-bx)=e,∴d|a- (b,a-bx)，即∵e|b,e|a- (a,b)，即 (a,b)，即∴d=e。證當(dāng)x=1時(shí)，(a,b)=(b,a-b)。這就是輾轉(zhuǎn)相減法當(dāng)x達(dá)到最大時(shí)，即x=[a/b]時(shí)，(a,b)=(b,amodb)。這個(gè)就是Euclid算法它是不是Euclid我不知道但聽(tīng)說(shuō)是在Euclid時(shí)代形成的所以就叫Euclidfunctionifb=0thenelseexit(Euclid(b,amod一次遞歸就會(huì)轉(zhuǎn)為(b,a)，接著就能正常運(yùn)行了。擴(kuò)展前面，(a,b)可以表示為a和b的最小的正線性組合?，F(xiàn)在就要求這個(gè)最小的正線性組合ax+by中的x和y。這個(gè)可以利用的Euclid算法。當(dāng)b=0時(shí)，取x=1,y=0例：a=5，b=0，最小正線性組合為5*1+y*0=5,y為任意整數(shù)。這里為方便起見(jiàn)規(guī)定y=0性組合表示bx'+(amodb)y'，則 =bx'+(amod =bx'+(a- =ay'+b(x'-那么，x=y'，y=x'-[a/b]y'。這樣就可以在Euclid的遞歸過(guò)程中求出x和yfunctionvarifb=0thenp:=(b,amodb);y:=n-adivb*y;現(xiàn)在還有一個(gè)問(wèn)題：x,y是不是確定的？答案：不是。如果x,y符合要求，那么際上y可以取任何正整數(shù)。以(26,15)為例X=-4Y=3-1*(-4)=726*(-↑X=3Y=-1-1*3=-415*3+11*(-X=-1Y=1-2*(-1)=311*(-X=1Y=0-1*1=-14*1+3*(-X=0Y=1-3*0=1X=1Y=0種特殊情況，實(shí)際上呢，不定方程卻是用Euclid算法解的。對(duì)于不定方ax+by=c，設(shè)(a,b)=d，如果ax+by=c有解，則d|c（這也是許多奧數(shù)題的切入點(diǎn)）。所以一旦d不是c的約數(shù)，那么ax+by=c一定無(wú)解d|c時(shí)，先求ax’+by’=d=(a,b)x'y'ax’+by’=dax’+by’=c，將c/d倍x=x'*c/d，y=y'*c/dax+by=cEuclid算法還可以求解同余方程ax≡b(modm)及其最小x。這其實(shí)和不定方程沒(méi)有區(qū)別。（不定方程和同余方程一般都有范圍限制，這其實(shí)也很容易解決，就不說(shuō)了