同余理论及应用.doc

同余理论及应用.doc

ID:58446699

大小:987.00 KB

页数:8页

时间:2020-05-13

同余理论及应用.doc_第1页
同余理论及应用.doc_第2页
同余理论及应用.doc_第3页
同余理论及应用.doc_第4页
同余理论及应用.doc_第5页
资源描述:

《同余理论及应用.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、同余理论及其应用基础知识一.定义定义1.设m为正整数,整数a和b之差可被m整除时,称为a和b关于模m同余,记作定义2.被正整数m除余数相等的所有整数的集合称为模m的剩余类。模m的剩余类共有m个。定义3.在模m的m个剩余类中各取一个整数作为代表,这些代表的集合称为模m的完全剩余系。定义4.绝对值不超过的模m的完全剩余系称为模m的绝对最小剩余系。定义5.当模m的某一剩余类的所有整数均与m互素时,则称此剩余类是模m的简化类。模m的简化类共有个。定义6.在模m的个简化类中各取一个整数作为代表,这些代表的集合称为模m的简化剩余系。定义

2、7.欧拉函数:设为正整数,从1到的整数中与互素的整数的个数用表示,称为欧拉函数。当时,有二.定理定理1.的必要充分条件是a和b被m除的余数相等。定理2.I.II.若则III.若则定理3.若,,则I.;II.;III..定理4.如果,则I.;II.推论.如果n为任意正整数,则定理5.如果则推论.如果,则定理6.如果则定理7.a和b属于模m的同一剩余类的充要条件是定理8.m个整数是模m的完全剩余系的充要条件是关于模m两两互不同余。定理9.设f是正整数m的正因数。在模f的属于c的剩余类中取整数,则它们是模m的个剩余类。定理10.与

3、m互素的个整数是模m的简化剩余系的充要条件是这个整数关于模m两两互不同余。又设是模m的简化剩余系,如果,则也是模m的简化剩余系。定理11.欧拉定理:如果,则定理12.费马小定理:如果,则,其中为素数。它也常写作:,这里不要求互素。定理13.裴蜀定理:设是整数,则的充要条件是,存在整数使得推论1.的充要条件是,存在整数使得推论2.均为正整数,的充要条件是,存在正整数使得典型例题:一.同余与完全平方数例1.设素数p满足,证明p必不能表作三个平方数之和。分析我们利用平方数模8的性质进行处理。证明:设存在三个整数使其中或为偶数,或为

4、奇数。因此下式必居其一。事实上,当a是奇数或时,有当a是偶数或时,有或同样b和c也必居下式之一:将所有可能满足的式子任意组合,只能得到而得不到因此形如的素数不能表作三个平方数之和。评注选择合适的模是处理平方数问题的技巧之一。例2.(2003年越南数学奥林匹克)求最大的正整数n,使得方程组有整数解分析我们利用平方数的性质处理问题。解:当时,易知所给的方程组有整数解,当时,,则奇偶交替出现,则且若为奇数,则矛盾。同理:若为偶数,则为奇数。后面式子又矛盾,所以无解。显然无解。评注选择适当的模,利用平方数性质是解决平方问题的技巧之一

5、。二.费马小定理与欧拉定理例3.证明分析由原式联想到费马小定理。证明:,由费马小定理,,,,,,而并且,由此可知:,所以原命题成立。评注费马小定理是处理此类整除问题的重要工具。例4.(2004年加拿大)为奇素数,证明:解:由于为偶数,则,由二项式定理:右侧除最后两项外均被整除。因此由于由费马小定理,,则所以所以,原结论成立。评注二项式定理也是处理数论问题的重要工具。三.同余与不定方程例5.(2004年韩国数学竞赛)证明:方程没有正整数解。分析我们选择适当的模对进行分类处理问题。证明:(1)当时,而方程左边能被3整除,此时无解

6、。(2)当时,,,而,,,均为完全平方数。而所以此时无解。(3)当时,,令则,令,则与(2)类似,均为完全平方数。设则,即,所以方程无整数解。综上所述,原方程无整数解。评注方程右边可以进行因式分解,而左边系数为3,因而选择模3对进行分类处理问题。例6.(2004年巴尔干数学奥林匹克)是质数,解:分析我们要充分利用是质数的条件。解:若,则无整数解;若,则由于是质数,由费马小定理,即,①,再由费马小定理即1.若则②;2.由①知:;由②知:即,,又为质数。而为奇质数,为偶数,与为质数矛盾。所以此时无解;3.若,由知,无解;4.若,

7、则当时:易知:时,,无解,,当时,两边模4,知无解;时,左边小于0,无解;当时:两边模4,时,左边小于0。当时:同理无解;时,左边小于0。当时:无解;时,满足条件。为一组解。当时,无解;时,无整数解;当时,,为一组解。综上,;为解。评注在处理有关质数的幂的问题中,费马小定理常发挥重要作用。四.同余定理例7.设p是奇素数,a是连续数列①中的任一数,则数列②中必有一个且只有一个数关于模p与1同余,设此数为ia,则i为①中一数且与a相异。分析利用为素数证明:因为①中各数均小于p,p为素数,所以①中每一个数均与p互素。由于a是①中某

8、数,故因此,由定理11,数列与数列①代表同一类数,也就是说,数列②表示模p的除p的倍数外,其余的一切类数。因此②中必有一数,使。这个i决不能等于a,事实上,如果,则有,从而就有。由于p是素数,且,故或,两者必居其一。但,即。所以不可能有及。故另外可以证明否则如果就有但,即,所以,因此不可能

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。