第三講歐幾里德算法

第三講歐幾里德算法第一頁，共十八頁，2022年，8月28日計算兩個正整數(shù)a，b的最大公約數(shù)用途a>b且amodb不為0條件輾轉相除法別名gcd(a,b)=gcd(b,amodb)原理歐幾里德算法用途條件別名原理第二頁，共十八頁，2022年，8月28日irst歐幾里德算法證明Fa表示成a=kb+r，則r=amodb假設d是a,b的一個公約數(shù)d|a,d|b而r=a-kb，因此d|r。d也是（b,amodb）的公約數(shù)。（a,b）和（b,amodb）的公約數(shù)是一樣的，其最大公約數(shù)也必然相等。第三頁，共十八頁，2022年，8月28日程序如下：intgcd(inta,intb){if(b==0)returna;elsereturngcd(b,a%b);}第四頁，共十八頁，2022年，8月28日econd唯一分解定理S算數(shù)基本定理又名唯一分解定理內(nèi)容：任何一個大于1的自然數(shù)N,如果N不為質數(shù)，那么N可以唯一分解成有限個質數(shù)的乘積這里P1<P2<P3......<Pn均為質數(shù)，其中指數(shù)ai是正整數(shù)。這樣的分解稱為N的標準分解式。第五頁，共十八頁，2022年，8月28日利用gcd(a,b)求最小公倍數(shù)lcm(a,b)、gcd(a,b)*lcm(a,b)=a*blcm(a,b)=a/gcd(a,b)*b先除后乘，可有效防止數(shù)據(jù)溢出第六頁，共十八頁，2022年，8月28日hirdly擴展歐幾里德算法T。如果一個方程含有兩個未知數(shù)，并且所含未知項的次數(shù)是１，那么這個整式方程就叫做二元一次方程，有無窮個解,若加條件限定有有限個解。二元一次方程的一般形式：ax+by+c=0其中a、b不為零。這就是二元一次方程的定義。x+y=1是一個典型的二元一次不定方程形如ax+by=c的不定方程稱為二元一次不定方程，顯然（1）a=0或者b=0時，方程的解確定（2）c不是gcd的倍數(shù)時，方程無解。所以只考慮ab!=0且gcd(a,b)能整除c的情況。推導過程省略gcd(a,b)=a*x+b*y顯然gcd(a,0)=1*a-0*0=a第七頁，共十八頁，2022年，8月28日公式推導過程：已知a,b求解一組p，q使得p*a+q*b=Gcd(a,b)對于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(注：這里的/是程序設計語言中的除法)那么可以得到: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)因此對于a和b而言，他們的相對應的p，q分別是y和(x-a/b*y)第八頁，共十八頁，2022年，8月28日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;}擴展歐幾里德的代碼第九頁，共十八頁，2022年，8月28日推導求直線ax+by+c=0上有多少個整數(shù)點（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).假設gcd(a,b)=g兩邊同時除以ga`(x1-x2)=b`(y2-y1)其中a`=a/gb`=b/ga`與b`互素x1-x2是b`的整數(shù)倍，設為kb`

y2-y1=ka`,同理x1-x2=kb`.所以得到推論1：設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ù)

第十頁，共十八頁，2022年，8月28日推論2：設a,b,c為任意整數(shù)，g=gcd(a,b),方程ax+by=g的一組解是（x0,y0）,則當c是g的倍數(shù)時ax+by=c的一組解是（x0c/g,y0c/g）;當c不是g的倍數(shù)時無整數(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ù)，所以無解第十一頁，共十八頁，2022年，8月28日中國剩余定理(孫子定理)中國古代求解一次同余式組的方法。是數(shù)論中一個重要定理Answer=a(modm1);Answer=b(modm2);Answer=c(modm3);注釋：三數(shù)為abc，余數(shù)分別為m1m2m3，%為求余計算，&&是“且”運算。1、分別找出能被兩個數(shù)整除，而滿足被第三個整除余一的最小的數(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、將三個未知數(shù)乘對應數(shù)字的余數(shù)再加起來，減去這三個數(shù)的最小公倍數(shù)的整數(shù)倍即得結果。Answer=k1×m1+k2×m2+k3×m3-P×(a×b×c);P為滿足Answer>0的最大整數(shù)；第十二頁，共十八頁，2022年，8月28日（中國剩余定理CRT）設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的逆元第十三頁，共十八頁，2022年，8月28日中國剩余定理的代碼：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);//擴展歐幾里德ans=(ans+mi*y*a[i])%M;}return(ans%M+M)%M;}第十四頁，共十八頁，2022年，8月28日《孫子算經(jīng)》中的題目：有物不知其數(shù)，三個一數(shù)余二，五個一數(shù)余三，七個一數(shù)又余二，問該物總數(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.求結果70*2+21*3+15*2-2*105=23二.同余的解法：因M除以3和7都余2，有等差數(shù)列2+21N滿足除以3和7都余2，在2+21N數(shù)列取5項：2，23，44，65，86，得23/5余3，因3*5*7=105，即23+105N數(shù)列的數(shù)都滿足這些條件。最小的就是23第十五頁，共十八頁，2022年，8月28日例題：例1：一個數(shù)除以5余4，除以8余3，除以11余2，求滿足條件的最小的自然數(shù)。題中5、8、11三個數(shù)兩兩互質。則〔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，因為，2499>440，所以，2499－440×5=299，就是所求的數(shù)。例2：有一個年級的同學，每9人一排多5人，每7人一排多1人，每5人一排多2人，問這個年級至少有多少人？（幸福123老師問的題目）題中9、7、5三個數(shù)兩兩互質。則〔7，5〕=35；〔9，5〕=45；〔9，7〕=63；〔9，7，5〕=315。為了使35被9除余1，用35×8=280；