合同-一次同余式-ou.ppt
《合同-一次同余式-ou.ppt》由会员分享,可在线阅读,更多相关《合同-一次同余式-ou.ppt(52页珍藏版)》请在咨信网上搜索。
1、5.3合同合同一次同余式一次同余式引入引入看任意整数看任意整数a除以除以3所得的余数:所得的余数:003+0;103+1;-1(-1)3+2;203+2;-2(-1)3+1;可以看到余数有三种情况:可以看到余数有三种情况:0,1,2;对于对于-1和和2,它们除以它们除以3余数相同,两式相减则有:余数相同,两式相减则有:2-(-1)=(0-(-1)3+(2-2),则,则,3|(2-(-1)引入引入引入一种新的记法来对引入一种新的记法来对3|(2-(-1)进行表达:进行表达:2-1(mod3)则,还有下面的式子:则,还有下面的式子:3 0(mod3)0 3(mod3)4 1(mod3)1 4(mo
2、d3)5 2(mod3)2 5(mod3)5.3.1合同及其性质合同及其性质 定义定义.设设a,b为二整数,为二整数,m是任意非是任意非0整数。整数。若若m|a-b,则称,则称a合同于合同于b模模m。记为:记为:a b(modm)Note:(1)合同为整除的另一种表示法,故整除的性质合同为整除的另一种表示法,故整除的性质在此可用。在此可用。特别地,若特别地,若b=0,则,则a 0(modm)表示的就是表示的就是m|a。(2)若若m|a,则,则-m|a。所以,若未指定。所以,若未指定m而一般地而一般地讨论模讨论模m合同时,总假定合同时,总假定m是正整数是正整数。5.3.1合同及其性质合同及其性质
3、 (3)设设a=q1m+r1,0r1m;b=q2m+r2,0r2m。于是于是a-b=(q1-q2)m+(r1-r2)则则m|(a-b)iffm|(r1-r2),但但|r1-r2|1。设设mm1m2,在模,在模m时属于同一剩时属于同一剩余类的整数,在模余类的整数,在模m1(或者模或者模m2)时时必定属于同一个剩余类,但在模必定属于同一个剩余类,但在模mq时就会被分到时就会被分到q个不同的剩余类中。个不同的剩余类中。合同的基本性质合同的基本性质性质性质11若若ac bc(modm),且(且(c,m)=d,则则a b(modm/d)证明:由证明:由ac bc(modm)知,知,m|(a-b)c,而而
4、(c,m)=d,故故m/d|(a-b)c/d。注意到注意到(m/d,c/d)=1,所以由所以由定理定理5.2.2,m/d|(a-b),即即a b(modm/d)。合同的基本性质合同的基本性质对于对于质数模质数模p(即即模模p为质数,如为质数,如mod3),则有与相等完全类似的消去律。则有与相等完全类似的消去律。性质性质12若若p为质数,为质数,c 0(modp),而而ac bc(modp),则则a b(modp)。证明:因为证明:因为p是质数,是质数,c 0(modp)就表示就表示p|c,即即c和和p互质,互质,(c,p)=1,因而性因而性质质12不过是性质不过是性质10的推论的推论(原来的整
5、原来的整数模数模m换成了现在的质数模换成了现在的质数模p)。合同的基本性质合同的基本性质性质性质13设设p(x)是整系数多项式,是整系数多项式,x和和y是整数变量,是整数变量,则由则由x y(modm)可得可得p(x)p(y)(modm)。证明:设证明:设p(x)=anxn+an-1xn-1+a1x1+a0,p(y)=anyn+an-1yn-1+a1y1+a0,由由x y(modm)和性质和性质8,xk yk(modm).由性质由性质7得得akxk akyk(modm).由性质由性质4得得anxn+an-1xn-1+a1x1+a0 anyn+an-1yn-1+a1y1+a0(modm).即即p
6、(x)p(y)(modm)。例例.求能被求能被9整除的正整数的整除的正整数的数码特征数码特征。设设N=an10n+an-110n-1+a110+a0为一整数,为一整数,因为因为10 1(mod9),由性质由性质13得得N an1n+an-11n-1+a1+a0(mod9)即即。于是于是9|N当且仅当当且仅当9|模模m合同既然是一种等价关系,就可以把合同既然是一种等价关系,就可以把所有整数按照模所有整数按照模m合同的关系分为等价类,合同的关系分为等价类,每一个等价类称为模每一个等价类称为模m的一个剩余类。的一个剩余类。同一个剩余类中的数互相合同,不同的剩同一个剩余类中的数互相合同,不同的剩余类中
7、的数不互相合同。余类中的数不互相合同。因为以因为以m去除任意整数,可能得到的余数去除任意整数,可能得到的余数恰有恰有0,1,m-1,这这m个数,所以模个数,所以模m共有共有m个剩余类,用个剩余类,用a表示表示a所在的剩余类。所在的剩余类。剩余类间的运算剩余类间的运算设设S为由模为由模m的所有剩余类组成的集合,在的所有剩余类组成的集合,在S上定义上定义和和两种运算。两种运算。这样规定合理吗?这样规定合理吗?记为,为,则对于任意剩余类记为,为,则对于任意剩余类求求在模的剩余类集合中是否存在元素满在模的剩余类集合中是否存在元素满足?记足?记若剩余类若剩余类A中存在与中存在与m互质的元素,则互质的元素
8、,则存在。存在。在模的剩余类集合中在模的剩余类集合中ABAC成成立立未必能保证未必能保证BC成立。成立。例如,在模例如,在模6的剩余类集合中的剩余类集合中3135不不能得出能得出15但是,若但是,若存在时,由存在时,由 ABAC可可以得到以得到BC。若剩余类若剩余类A中存在中存在a与与m互质,则互质,则A中任意元中任意元素素x均与均与m互质。互质。结论结论5.3.2剩余类剩余类一次同余式一次同余式模模m合同既然是一种等价关系,就可以把合同既然是一种等价关系,就可以把所有整数按照模所有整数按照模m合同的关系分为等价类,合同的关系分为等价类,每一个等价类称为模每一个等价类称为模m的一个的一个剩余类
9、剩余类。例如,整数集合例如,整数集合Z,模,模3,得到:,得到:余数为余数为0:,-6,-3,0,3,6,余数为余数为1:,-5,-2,1,4,7,余数为余数为2:,-4,-1,2,5,8,5.3.2剩余类剩余类一次同余式一次同余式同一个剩余类中的数互相合同,不同的剩同一个剩余类中的数互相合同,不同的剩余类中的数不互相合同。余类中的数不互相合同。因为以因为以m去除任意整数,可能得到的余数去除任意整数,可能得到的余数恰有恰有0,1,m-1,这这m个数,所以个数,所以模模m共有共有m个剩余类个剩余类.5.3.2剩余类剩余类一次同余式一次同余式从模从模m每个剩余类中每个剩余类中任意任意取出取出一个数
10、一个数作为代表,作为代表,得到得到m个数,比方个数,比方r1,r2,rm,称这,称这m个数作成个数作成一个一个完全剩余系完全剩余系。例例0,1,m-1便是这样一个完全剩余系,便是这样一个完全剩余系,称为模称为模m的非负最小完全剩余系。的非负最小完全剩余系。任意整数模任意整数模m恰好恰好合同于此完全剩余系中的一个合同于此完全剩余系中的一个数。数。例例模模3,三个数,三个数0,1,2作成一个完全剩余系,作成一个完全剩余系,-1,0,1也作成一个完全剩余系。也作成一个完全剩余系。例例模模2,两个数,两个数0,1作成一个完全剩余系,作成一个完全剩余系,0代代表所有偶数,表所有偶数,1代表所有奇数代表所
11、有奇数.5.3.2剩余类剩余类一次同余式一次同余式由模由模m的全部剩余类构成的集合称为该等价关的全部剩余类构成的集合称为该等价关系(模系(模m合同关系)的商集,商集是惟一确定的。合同关系)的商集,商集是惟一确定的。模模m的完全剩余系在形式上不惟一。的完全剩余系在形式上不惟一。例例模模3,三个数,三个数0,1,2作成一个完全剩余系,作成一个完全剩余系,-1,0,1也作成一个完全剩余系。也作成一个完全剩余系。即,模即,模m的不同的完全剩余系间可以建立双射。的不同的完全剩余系间可以建立双射。m个整数构成模个整数构成模m的完全剩余系,的完全剩余系,这这m个整数中不存在模个整数中不存在模m合同的两个数合
12、同的两个数(这这m个个整数中任何两个数模整数中任何两个数模m均不同余均不同余)。证明:证明:()A=0,1,2,m-1记记m个整数构成的集合为个整数构成的集合为B=b1,b2,bm对于对于任意的任意的bi,存在,存在A中元素中元素f(bi)满足满足bi f(bi)(modm)。则则f为集合为集合B到到A的映射,由已知,的映射,由已知,f为单射为单射,又,又|B|=m=|A|,则,则f为双射,故这为双射,故这m个整个整数构成了模数构成了模m的完全剩余系。的完全剩余系。注意注意若若|A|=|B|,存在从,存在从B到到A内内的单射的单射f,则,则f未必为满射。未必为满射。例如,为例如,为A无限集。无
13、限集。同余式同余式有棋子若干枚,三个三个的数剩两个,问有棋子若干枚,三个三个的数剩两个,问至少有多少个棋子?至少有多少个棋子?答:由题意,棋子的个数减答:由题意,棋子的个数减2是是3的倍数,的倍数,从而从而有,有,(x-2)=3y,x0,用合同式表示为:,用合同式表示为:x2(mod3),从而棋子的个数可能是:,从而棋子的个数可能是:2,5,7,,都是,都是mod3合同合同2。同余式同余式含有整数变量的合同式,称为合同方程或含有整数变量的合同式,称为合同方程或同余式同余式。ax b(modm)这种形式的合同式称为一这种形式的合同式称为一次同余式;类似地,次同余式;类似地,a2x2+a1x b(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 合同 一次 同余式 ou
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。