第三讲欧几里德算法

第三讲欧几里德算法演示文稿现在是1页\一共有16页\编辑于星期一优选第三讲欧几里德算法现在是2页\一共有16页\编辑于星期一irst欧几里德算法证明Fa表示成a=kb+r，则r=amodb假设d是a,b的一个公约数d|a,d|b而r=a-kb，因此d|r。d也是（b,amodb）的公约数。（a,b）和（b,amodb）的公约数是一样的，其最大公约数也必然相等。现在是3页\一共有16页\编辑于星期一程序如下：intgcd(inta,intb){if(b==0)returna;elsereturngcd(b,a%b);}现在是4页\一共有16页\编辑于星期一econd唯一分解定理S算数基本定理又名唯一分解定理内容：任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为N的标准分解式。现在是5页\一共有16页\编辑于星期一利用gcd(a,b)求最小公倍数lcm(a,b)、gcd(a,b)*lcm(a,b)=a*blcm(a,b)=a/gcd(a,b)*b先除后乘，可有效防止数据溢出现在是6页\一共有16页\编辑于星期一hirdly扩展欧几里德算法T。如果一个方程含有两个未知数，并且所含未知项的次数是１，那么这个整式方程就叫做二元一次方程，有无穷个解,若加条件限定有有限个解。二元一次方程的一般形式：ax+by+c=0其中a、b不为零。这就是二元一次方程的定义。x+y=1是一个典型的二元一次不定方程形如ax+by=c的不定方程称为二元一次不定方程，显然（1）a=0或者b=0时，方程的解确定（2）c不是gcd的倍数时，方程无解。所以只考虑ab!=0且gcd(a,b)能整除c的情况。推导过程省略gcd(a,b)=a*x+b*y显然gcd(a,0)=1*a-0*0=a现在是7页\一共有16页\编辑于星期一公式推导过程：已知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)现在是8页\一共有16页\编辑于星期一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;}扩展欧几里德的代码现在是9页\一共有16页\编辑于星期一推导求直线ax+by+c=0上有多少个整数点（x,y）满足x∈(X1,X2),y∈(Y1,Y2)任取（x1,y1）和（x2,y2）为ax+by=gcd(a,b)的整数解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`的整数倍，设为kb`

y2-y1=ka`,同理x1-x2=kb`.所以得到推论1：设a,b,c为任意整数，若方程ax+by=gcd(a,b)的一组解为（x0,y0）,则他的任意解都可以写成（x0+kb`,y0-ka'）其中a`=a/gcd(a,b)b`=b/gcd(a,b)k取任意数

现在是10页\一共有16页\编辑于星期一推论2：设a,b,c为任意整数，g=gcd(a,b),方程ax+by=g的一组解是（x0,y0）,则当c是g的倍数时ax+by=c的一组解是（x0c/g,y0c/g）;当c不是g的倍数时无整数解。例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.左边是整数，右边不是整数，所以无解现在是11页\一共有16页\编辑于星期一中国剩余定理(孙子定理)中国古代求解一次同余式组的方法。是数论中一个重要定理Answer=a(modm1);Answer=b(modm2);Answer=c(modm3);注释：三数为abc，余数分别为m1m2m3，%为求余计算，&&是“且”运算。1、分别找出能被两个数整除，而满足被第三个整除余一的最小的数。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、将三个未知数乘对应数字的余数再加起来，减去这三个数的最小公倍数的整数倍即得结果。Answer=k1×m1+k2×m2+k3×m3-P×(a×b×c);P为满足Answer>0的最大整数；现在是12页\一共有16页\编辑于星期一（中国剩余定理CRT）设m1,m2,...,mk是两两互素的正整数，即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的逆元现在是13页\一共有16页\编辑于星期一中国剩余定理的代码：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;}现在是14页\一共有16页\编辑于星期一《孙子算经》中的题目：有物不知其数，三个一数余二，五个一数余三，七个一数又余二，问该物总数几何？题目大意：M/3余2，M/5余3，M/7余2，求MM=3X+2;M=5Y+3;M=7Z+2;一.基本解法：1.找最小公倍数lcm(3,5)=15,lcm(5,7)=35,lcm(3,7)=21;2.分别找出除3，除5，除7为1的数，70=3（mode1);21=5(mode1);15=7(mode1);3.求结果70*2+21*3+15*2-2*105=23二.同余的解法：因M除以3和7都余2，有等差数列2+21N满足除以3和7都余2，在2+21N数列取5项：2，23，44，65，86，得23/5余3，因3*5*7=105，即23+105N数列的数都满足这些条件。最小的就是23现在是15页\一共有16页\编辑于星期一例题：例1：一个数除以5余4，除以8余3，除以11余2，求满足条件的最小的自然数。题中5、8、11三个数两两互质。则〔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，就是所求的数。例2：有一个年级的同学，每9人一排多5人，每7人一排多1人，每5人一排多2人，问这个年级至少有多少人？（幸福12