教学目标8.1最大公约数8.1.1欧几里德算法应用举例（求100和210最大公约数）欧几里德递归公式的推广来解决“已知a,b求解一组x，y使得ax+by=gcd(a,b)”问题令gcd(a,b)=d，则ax+by=d；gcd(b,amodb)=d(8-1)（1）当b=0时，则gcd(a,b)=a；ax+by=a，即ax=a，则x=1，y取任意实数。简单起见，算法取y=0；（2）当b≠0时，令a'=b，b'=amodb，则gcd(a',b')=d，a'x'+b'y'=d。由于b'=amodb=，则a'x'+b'y'=bx'+()y'=ay'+b(x'-y')=d(8-2)让式(8-1)和式(8-2)对应项相等，则x=y'，y=x'-y'。8.1.2Stein算法如果a和b都是偶数，则a=a/2，b=b/2，c=2*c；如果a是偶数，b不是偶数，则a=a/2；如果b是偶数，a不是偶数，则b=b/2；如果a和b都不是偶数，则a=|a1–b1|，b=min(a1,b1)；转步骤2。应用举例求15和9的最大公约数8.2同余方程例1：使2n+1能被3整除的一切自然数n例2：求2999最后两位数码同余方程设是整系数多项式，m是正整数，称f(x)0(modm)(8-4)是关于未知数x的模m的同余方程，简称为模m的同余方程。若则称式(8-4)为n次同余方程同余方程的解设x0是整数，当x＝x0时式(8-4)成立，则称x0是同余方程(8-4)的解。凡对于模m同余的解，被视为同一个解一次同余方程设a，b为整数，且，则称同余方程axb(modm)(8-5)为一次同余方程。定义7设a1,a2,…,an是非零整数，b是整数，称关于未知数x1,x2,…,xn的方程a1x1+a2x2+…+anxn=b是n元一次不定方程。定理3一次同余方程有解的充要条件是gcd(a,m)|b。若有解，则恰有d=gcd(a，m)个解。证明（见板书）一次同余方程的求解步骤步骤1：求gcm(a，m)；步骤2：令d=gcm(a，m)，如果db，则式(8-5)无解，算法结束；如果,则转步骤3；步骤3：根据欧几里德公式的推广，求出式(8-5)的一个解x0。步骤3-1：根据欧几里德公式的推广算法求得满足ax'+my'=d的x'，y'；具体方法：将ax'+my'=d变形可得到：ax'=d-my'(8-8)式（8-8）两边同时模m得：(8-9)可见，x'是一次同余方程(8-9)的解。步骤3-2：根据x'求x0。具体方法：由于，设，则根据同余式的性质得：即：。因此，x0=px'=x'(modm)。步骤4：根据(8-7)式可得(8-5)式的其它d-1个解为，i=1,2,…,d-1。算法结束。量水有三个分别装有a升水，b升水和c升水的量筒(gcd(a,b)=1，c＞b＞a>0)。现c筒装满水，问能否在c简中量出d升水(c>d>0)。若能，请列出一种方案。算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个特点：总有一个筒中的水没有变动；不是一个筒被倒满就是另一个筒被倒光；c筒仅起中转作用。而本身容积除了必须足够装下a筒和b筒的全部水外，别无其它限制。通过上述分析知：问题实质上是将a筒倒满x次，b筒倒满y次，使得总结果有ax十by＝d(8-10)设a＝3，b＝7，c＝10，求x,y8.3同余方程组定理对同余方程组记，其中，表示m1和m2的最小公倍数。①若d(a1-a2)，则此同余方程组无解；②若d|(a1-a2)，则此同余方程组有对模M的一类剩余解。中国剩余定理（即孙子定理）设是两两互质的正整数，记M=，则同余方程组有对模M的唯一解其中证明（见板书）例：早在几千年前中国的一本《孙子算经》就已经提及这个问题的解法了，原文为：“今有物，不知其数，三三数之，剩二；五五数之，剩三；七七数之，剩二，问物几何？”答曰：“二十三”。8.4线段相交几何意义以和为边的平行四边形的面积叉积定义为一个矩阵行列式思考1：叉积何时小于0？何时大于0？又何时等于0？思考2：对公共点P0而言，如何知道有向线段在有向线段的什么方向？通过叉积可以知道确定两条线段是否相交第一步：通过快速排斥实验来确定两条线段是否不相交；第二步：在快速排斥实验判断有可能相交的前提下进行跨立实验，来确定两条线段是否相互跨立确定任意一对线段相交对应给定的一个线段集合，确定其中任意两条线段是否相交。该算法输入由若干条线段组成的集合，若这组线段中存在任意一对线段相交，则返回true；否则，返回false两点假设（1）线段集合中的所有线段都不是竖直的；（2）未有三条输入线段相交于同一点的情形。算法思想假设一条垂