第8章 数论算法及计算几何算法.ppt

,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章数论算法及计算几何算法一