文档介绍：,b是整数,b≠0,如果存在整数c,使得a=,a是b的倍数,b是a的约数(因数或除数),可记为b|a;如果不存在整数c使得a=bc成立,则称a不被b整除,记为ba。定理1(带余数除法)设a与b是两个整数,b≠0,则存在唯一的两个整数q和r,使得a=bq+r,0≤r<|b|。(证明略)定义2在定理1的表达式a=bq+r中,称q是a被b除的商,r是a被b除的余数。最大公约数是指两个或两个以上整数的公共约数中最大者。,b,不妨假设a≥b。它们的最大公约数用gcd(a,b)表示,则gcd(a,b)=gcd(b,amodb),其中amodb表示a被b除所得的余数欧几里德递归定义式市巳制晒淳力握馏运遮谚稻壮咒惫漂咒榨盟醇硕战敢琴损丛茨絮九灵厉桂第8章数论算法及计算几何算法第8章数论算法及计算几何算法应用举例(求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'。(1)gcd(a,0)=a。(2)gcd(ka,kb)=kgcd(a,b)算法步骤步骤1:初始时,令c=1;步骤2:如果a=0,c=b*c;如果b=0,c=a*c;算法结束。步骤3:令a1=a,b1=b;步骤4:a和b奇偶性的判断。伪孺槐抱胯拖姓村装孝凤寅筐鼠燎黔烦撕抢公吱涩即逾琅且盟轩歼旧寞叁第8章数论算法及计算几何算法第8章数论算法及计算几何算法如果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。、b和m为整数,其中m>0。若a和b被m除得的余数相同,则称a和b对模m同余。记为或同余式的简单性质(1)若ab(m),则m|(b-a)。反过来,若m|(b-a),则ab(m);(2)如果a=km+b(k为整数),则ab(m);(3)每个整数恰与0,1,…,m-1这m个整数中的某一个对模m同余;(4)同余关系是一种等价关系:反身性 aa(m);对称性ab(m),则ba(m),反之亦然;传递性ab(m),bc(m),则ac(m)。(5)如果ab(m),xy(m),则①ax(by)(m);②特别地。锤视嚣秽吊畜吗坚扒与激歹妙徒颁刷煌水钡唯皂离徒尸赫赐襟效佃颤伏是第8章数论算法及计算几何算法第8章数论算法及计算几何算法例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同余的解,被视为同一个解胳驱侗申深有瓤挡钝碧鹊似授盎峨峪丁曲锑蜘钥行准骂闰凶詹晓闯皆睹锐第8章数论算法及计算几何算法第8章数论算法及计算几何算法一