《浅谈同余及其应用》由会员分享，可在线阅读，更多相关《浅谈同余及其应用（13页珍藏版）》请在金锄头文库上搜索。
1、精品范文模板 可修改删除撰写人：_日 期：_揭阳职业技术学院 毕 业 论 文（设计） 题 目： 浅谈同余定理及其应用学生姓名 黄 指导教师 某某某系（部） 师范教育系 专 业 数学教育班级 999 班 学号 11211211 提交日期 200 年 月 日 答辩日期 200 年 月 日200 年 月 日 浅谈同余定理及其应用摘 要初等数论是研究数的规律，特别是整数性质的数学分支。它 以算术方法为主要研究方法，在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数。同余理论是初等数论中的重要内容之一，其性质及应用研究已引起许多学者的关注。本文归纳总结了同余的若干性质，
2、结合实例，探究了同余性质在检验、判断整除问题、求余数、判断合数、韩信点兵问题等方面的具体应用。体现了用同余性质解决问题的简洁性。关键词：同余 整除 余式 方程绪论初等数论是研究整数性质的一门学科，它是数学中最古老的分支之一，内容极为丰富，曾被数学家说成是数学的皇后。同余问题在当今中小学乃至大学的数学教学中都有涉及，它作为初等数论的核心内容之一，具有很强的应用价值，很多数学问题都要借助同余理论来解决。同余的应用问题分为很多种类型，每种类型的题目又有一定的解题技巧。掌握了这些题型的技巧，可以提高大家解决问题的能力。本文基于对同余理论的理解，将应用同余理论解决的问题具体整理分类，从中分析出一些借助同
3、余理论解题的技巧与规律。现在初等数论中关于同余的内容主要包括：同余的定义及基本性质、剩余类与剩余系、欧拉定理、费马小定理、循环小数、一次同余方程及一次同余方程组。到目前为止，古今中外很多学者与数学家，对同余的应用问题都有了一定的研究。在中国，早在宋代，大数学家秦九韶所著的数书九章中就记载了求解同余方程的“大衍求一术”。还有，著名的古代数学著作孙子算经中也记载能解决“物不知其数”问题的孙子定理，也被称作“中国剩余定理”。以及“韩信点兵”问题的研究，都为解决一次同余方程和同余方程组的问题带来了便利。在西方，除了高斯引入同余的概念之外，欧拉和费马提出的定理也为解决同余的相关问题做出了重要的贡献。希望
4、通过本文的研究能将同余理论的应用问题更加系统全面的展现出来。以便，今后大家在探究同余理论时，能对同余应用问题的类型和解决技巧有一个清晰的认识和理解，更好的解决相关问题。1 相关性质定理1性质1 同余是一种等价关系，即有：（1）反身性 aa（mod m）.（2）对称性 若ab（mod m），则ba（mod m）. （3）传递性 若ab（mod m）， bc（mod m），则ac（mod m）. 性质2 同余式可以相加减,即若 ab（mod m），cd（mod m），则(1) acbd（mod m）.(2) acbd（mod m）. 性质3 同余式可以相乘,即有：(1) 若ab（mod m）， c
5、为自然数, 则acbc（mod m）. (2) 若ab（mod m），cd（mod m），则acbd（mod m）.(3) 若ab（mod m）， n2, 则anbn（mod m）.性质4 若acbc（mod m），且（c，m）=1，则 有ab（mod m）.（其中（c，m）表示c与m的最大公约数）。 定理1 整数a,b对模m同余的充分与必要条件是mab ,即 abmt. (t是整数.)定理2 设a,则a(1)(1)(1)定理3 (Euler) 设m是大于1的整数， (a,m)=1， 则 a1（modm），其中为欧拉函数 定理4 (Fermat) 若p是素数，则apa（modp）. .证明以上
6、三个定理:定理1证明: 设 a=mq1r1, b=mq2r2, 0r1m, 0r2m, 若ab（mod m）, 则r1=r2, 因此ab=mq1q2. 反之, 若 m | ab, 则m |mq1q2r1r2,因此 m | r1r2. 又 | r1r2 |m,故r1=r2定理3证明: 设a1 a2 a, 是modm的一个简化剩余系，且（a,m）=1,aa1 aa2 aa也是modm的一个简化剩余系. a1 a2, a,aa1 aa2 aa (modm）aa1 a2 a（modm）. 因此a1（modm）.定理4证明: 若（a,p）1,则有ap-1a（modp）,因而apa（modp）.若（a,p
7、）1,则p|a,因而ap0（modp）, a0（modp）故apa（modp）2 同余性质的应用2.1 求余数问题 利用同余的性质及定理求余数 例1：将从1开始的连续自然数依次写下来，一直写到2003成为一个多位数，12345620022003，求这个数除以3的余数。解：由连续的3个自然数的和必能被3整除，而3|2001，（2+0+0+2+2+0+0+3）0（mod3）, 所以原多位数除以3余数为0例2：求201022001被3除所得的非负余数.解： 设201022001=3qr, 其中0r3, 故 r201022001（mod3）且0r3.又20102=36702, 所以201022(mod
8、3).从而 22001220002410002(mod3)而 22001220002410002(mod3),41(mod3)故 410001 (mod3) ,4100022 (mod3).从而 r2(mod3). 而0r3, 故r=2.即 201022001除以3所得的余数为2.分析：此类题目解题的关键在于应用同余的乘方性，先求出底数20102对3的余数，再根据性质求出余数的2001次幂对3的余数即可例3：求4373091993被7除的余数。解：4733（mod7）3091（mod7）由同余的可乘性知：43730931（mod7）3（mod7）又因为19935（mod7）所以：4373091
9、99335（mod7）15（mod7）1（mod7）即：4373091993被7除余1。分析：此类题目解题的关键在于应用同余的可乘性，分别求出每个因数对于7的余数，在相乘即可简单求出2.1.2 求星期几问题求某年某月某日为星期几时,则令D=第N年m月d日,设D这一天为星期WD ,WD dy2c(mod7)其中c,y满足N100cy,0y100.注意:算出的结果为1 至7,各代表星期一到星期日.例:1949年10月1日是星期几?2.1.3 尾数问题例1：求243402的末三位数？解：因为（243，1000）=1，=10001 ）（1 ）=400由欧拉定理知，243400 1（mod1000），故
10、243402243249（mod1000）所以243402的末三位数为049.例2：求3200172002132003的个位数字？解：应用欧拉定理，（3,10）=1,341（mod10）,则有3200134k13（mod10）；同理，741（mod10）， 7200274k29（mod10）； 1341（mod10），132003134k37（mod10）；因379189，故个位数字为 9 .分析：利用同余的性质，求一个数字的个位数字就是求其除以10所得的余数,同类题型的变换问法：求某数的末两位数字是多少?（模为100）2.2 同余在检验方面的应用 检查因数的一些方法1 方法一： 一整数能被3
11、（9）整除的必要且充分的条件是它的十进位数码的和能被3（9）整除. 证明：显然我们只须讨论任一正整数a便可.把a写成十进位数的形式：a=an10nan110n1a110a0 , 0ai10. 因101（mod 3）,故由定理2得aanan1a1a0（mod 3）.由已知性质，即知3a当且仅当ai.同法可得9a当且仅当9ai方法二： 设正整数 a=an1000nan11000n1a11000a0 , 0ai1000.则7（或11，或13）整除a的必要且充分的条件是7（或11或13）整除（a0a2）-（a1a3）=(1)iai证明：因为1000与-1对模7（或11或13）同余，故由定理知a与(1)
12、iai 对模7（或11或13）同余.由已知性质，7（或11或13） 整除a当且仅当7（或11或13）整除(1)iai 弃九法1（假设我们由普遍乘法的运算方法求出整数a，b的乘积是P，并令 a=an10nan110n1a110a0 , 0ai10.b=bm10mbm110m1b110b0 , 0bj10.P=cl10lcl110l1c110c0 , 0ck10.我们说：如果（ai）（bj）不同余于ck（mod9）， 那么所求得的乘积是错误的.因为ab（ai）（bj）（mod9），P ck（mod9）. 若 （ai）（bj）不同余于ck（mod9）， 则ab不同余P（mod9）， 故ab不是P.2.2.3 判定合数 由费马定理可得推论如下 若p是素数，且(a,p) 1，则ap11(modp).利用推论可以判定一个数是否为合数，即若N是我们要检验的数，先取某一个与N互素并比N小的数a，通常合适的是把a取为不能整除N的小素数，如a2, a3或a5 如果N是素数那么由推论它应该满足aN11(modN)，因此如果验算这个同余不成立，我们就断言 N 是合数.例2 判断 N117 是否为合数. 分析 我们根据定理3即费马定理，可以考虑若N是素数， 则有aN11(modN)，N为我们所检验的数.解：选a=2则a与N互素，aN1=2116=26423221624，而28=25622(mod117),
