第三講歐幾里德算法

第三講歐幾里德算法演示文稿當(dāng)前1頁(yè)，總共16頁(yè)。優(yōu)選第三講歐幾里德算法當(dāng)前2頁(yè)，總共16頁(yè)。irst歐幾里德算法證明Fa表示成a=kb+r，則r=amodb假設(shè)d是a,b的一個(gè)公約數(shù)d|a,d|b而r=a-kb，因此d|r。d也是（b,amodb）的公約數(shù)。（a,b）和（b,amodb）的公約數(shù)是一樣的，其最大公約數(shù)也必然相等。當(dāng)前3頁(yè)，總共16頁(yè)。程序如下：intgcd(inta,intb){if(b==0)returna;elsereturngcd(b,a%b);}當(dāng)前4頁(yè)，總共16頁(yè)。econd唯一分解定理S算數(shù)基本定理又名唯一分解定理內(nèi)容：任何一個(gè)大于1的自然數(shù)N,如果N不為質(zhì)數(shù)，那么N可以唯一分解成有限個(gè)質(zhì)數(shù)的乘積這里P1<P2<P3......<Pn均為質(zhì)數(shù)，其中指數(shù)ai是正整數(shù)。這樣的分解稱為N的標(biāo)準(zhǔn)分解式。當(dāng)前5頁(yè)，總共16頁(yè)。利用gcd(a,b)求最小公倍數(shù)lcm(a,b)、gcd(a,b)*lcm(a,b)=a*blcm(a,b)=a/gcd(a,b)*b先除后乘，可有效防止數(shù)據(jù)溢出當(dāng)前6頁(yè)，總共16頁(yè)。hirdly擴(kuò)展歐幾里德算法T。如果一個(gè)方程含有兩個(gè)未知數(shù)，并且所含未知項(xiàng)的次數(shù)是１，那么這個(gè)整式方程就叫做二元一次方程，有無(wú)窮個(gè)解,若加條件限定有有限個(gè)解。二元一次方程的一般形式：ax+by+c=0其中a、b不為零。這就是二元一次方程的定義。x+y=1是一個(gè)典型的二元一次不定方程形如ax+by=c的不定方程稱為二元一次不定方程，顯然（1）a=0或者b=0時(shí)，方程的解確定（2）c不是gcd的倍數(shù)時(shí)，方程無(wú)解。所以只考慮ab!=0且gcd(a,b)能整除c的情況。推導(dǎo)過(guò)程省略gcd(a,b)=a*x+b*y顯然gcd(a,0)=1*a-0*0=a當(dāng)前7頁(yè)，總共16頁(yè)。公式推導(dǎo)過(guò)程：已知a,b求解一組p，q使得p*a+q*b=Gcd(a,b)對(duì)于a'=b,b'=a%b而言，我們求得x,y使得a'x+b'y=Gcd(a',b')a=k*b+r===>r=a-k*bk=a/br=a%b=a-k*b===>b'=a%b=a-a/b*b(注：這里的/是程序設(shè)計(jì)語(yǔ)言中的除法)那么可以得到:a'x+b'y=Gcd(a',b')===>bx+(a-a/b*b)y=Gcd(a',b')=Gcd(a,b)===>ay+b(x-a/b*y)=Gcd(a,b)因此對(duì)于a和b而言，他們的相對(duì)應(yīng)的p，q分別是y和(x-a/b*y)當(dāng)前8頁(yè)，總共16頁(yè)。intexGcd(inta,intb,int&x,int&y){if(b==0){x=1;y=0;returna;}intr=exGcd(b,a%b,x,y);intt=x;x=y;y=t-a/b*y;returnr;}擴(kuò)展歐幾里德的代碼當(dāng)前9頁(yè)，總共16頁(yè)。推導(dǎo)求直線ax+by+c=0上有多少個(gè)整數(shù)點(diǎn)（x,y）滿足x∈(X1,X2),y∈(Y1,Y2)任?。▁1,y1）和（x2,y2）為ax+by=gcd(a,b)的整數(shù)解ax1+by1=ax2+by2=gcd(a,b)a(x1-x2)=b(y2-y1).假設(shè)gcd(a,b)=g兩邊同時(shí)除以ga`(x1-x2)=b`(y2-y1)其中a`=a/gb`=b/ga`與b`互素x1-x2是b`的整數(shù)倍，設(shè)為kb`

y2-y1=ka`,同理x1-x2=kb`.所以得到推論1：設(shè)a,b,c為任意整數(shù)，若方程ax+by=gcd(a,b)的一組解為（x0,y0）,則他的任意解都可以寫成（x0+kb`,y0-ka'）其中a`=a/gcd(a,b)b`=b/gcd(a,b)k取任意數(shù)

當(dāng)前10頁(yè)，總共16頁(yè)。推論2：設(shè)a,b,c為任意整數(shù)，g=gcd(a,b),方程ax+by=g的一組解是（x0,y0）,則當(dāng)c是g的倍數(shù)時(shí)ax+by=c的一組解是（x0c/g,y0c/g）;當(dāng)c不是g的倍數(shù)時(shí)無(wú)整數(shù)解。例1.gcd(6,15)=3,6x+15y=9.求x,y6*(-2)+15*1=3,兩邊同乘36*（-6）+15*3=9

x=-6y=32.6x+15=8兩邊同除3，2x+5=8/3.左邊是整數(shù)，右邊不是整數(shù)，所以無(wú)解當(dāng)前11頁(yè)，總共16頁(yè)。中國(guó)剩余定理(孫子定理)中國(guó)古代求解一次同余式組的方法。是數(shù)論中一個(gè)重要定理Answer=a(modm1);Answer=b(modm2);Answer=c(modm3);注釋：三數(shù)為abc，余數(shù)分別為m1m2m3，%為求余計(jì)算，&&是“且”運(yùn)算。1、分別找出能被兩個(gè)數(shù)整除，而滿足被第三個(gè)整除余一的最小的數(shù)。k1%b==k1%c==0&&k1%a==1;k2%a==k2%c==0&&k2%b==1;k3%a==k3%b==0&&k3%c==1;2、將三個(gè)未知數(shù)乘對(duì)應(yīng)數(shù)字的余數(shù)再加起來(lái)，減去這三個(gè)數(shù)的最小公倍數(shù)的整數(shù)倍即得結(jié)果。Answer=k1×m1+k2×m2+k3×m3-P×(a×b×c);P為滿足Answer>0的最大整數(shù)；當(dāng)前12頁(yè)，總共16頁(yè)。（中國(guó)剩余定理CRT）設(shè)m1,m2,...,mk是兩兩互素的正整數(shù)，即gcd(mi,mj)=1,i≠j,i,j=1,2,...,k則同余方程組：x≡b1（modm1)x≡b2（modm2)...x≡bk（modmk)模[m1,m2,...,mk]有唯一解，即在[m1,m2,...,mk]的意義下，存在唯一的x，滿足：x≡bimod[m1,m2,...,mk],i=1,2,...,k即X=((M_1*M1*b1)+(M_2*M2*b2)+...+(M_n*Mn*bn))modM其中M=m1*m2*m3...*mn;Mi=M/mi;M_i是Mi的逆元當(dāng)前13頁(yè)，總共16頁(yè)。中國(guó)剩余定理的代碼：intchina(int*a,int*m,intn){intM=1,ans=0,mi,i,x,y;for(i=0;i<n;i++)M*=m[i];//M=m1*m2*m3...*mnfor(i=0;i<n;i++){mi=M/m[i];//Mi=M/miexGcd(m[i],mi,x,y);//擴(kuò)展歐幾里德ans=(ans+mi*y*a[i])%M;}return(ans%M+M)%M;}當(dāng)前14頁(yè)，總共16頁(yè)?！秾O子算經(jīng)》中的題目：有物不知其數(shù)，三個(gè)一數(shù)余二，五個(gè)一數(shù)余三，七個(gè)一數(shù)又余二，問(wèn)該物總數(shù)幾何？題目大意：M/3余2，M/5余3，M/7余2，求MM=3X+2;M=5Y+3;M=7Z+2;一.基本解法：1.找最小公倍數(shù)lcm(3,5)=15,lcm(5,7)=35,lcm(3,7)=21;2.分別找出除3，除5，除7為1的數(shù)，70=3（mode1);21=5(mode1);15=7(mode1);3.求結(jié)果70*2+21*3+15*2-2*105=23二.同余的解法：因M除以3和7都余2，有等差數(shù)列2+21N滿足除以3和7都余2，在2+21N數(shù)列取5項(xiàng)：2，23，44，65，86，得23/5余3，因3*5*7=105，即23+105N數(shù)列的數(shù)都滿足這些條件。最小的就是23當(dāng)前15頁(yè)，總共16頁(yè)。例題：例1：一個(gè)數(shù)除以5余4，除以8余3，除以11余2，求滿足條件的最小的自然數(shù)。題中5、8、11三個(gè)數(shù)兩兩互質(zhì)。則〔8，11〕=88；〔5，11〕=55；〔5，8〕=40；〔5，8，11〕=440。為了使88被5除余1，用88×2=176；使55被8除余1，用55×7=385；使40被11除余1，用40×8=320。然后，176×4+385×3+320×2=2499，因?yàn)椋?499>440，所以，2499－440×5=299，就是所求的數(shù)。例2：有一個(gè)年級(jí)的同學(xué)，每9人一排多5人，每7人一排多1人，每5人一排多2人，問(wèn)這個(gè)年級(jí)至少有多少人？（幸福