同余理论及其应用论文.doc

《同余理论及其应用论文.doc》由会员分享，可在线阅读，更多相关《同余理论及其应用论文.doc（29页珍藏版）》请在三一办公上搜索。

1、齐齐哈尔大学毕业（设计）论文题 目 同余理论及其应用学 院 理学院专业班级 数学与应用数学专业 学生姓名 指导教师 成 绩 2013年 6月20日摘 要同余理论在数论中是非常重要的一个部分, 由整除概念的延拓得到了同余理论, 引进了同余之后就简化了数论中的很多问题, 它的应用十分广泛, 在生活中也经常遇到, 这也极大地推动和丰富了它们的发展, 许多新的理论、技巧和方法的诞生与发展都是同余理论的应用与推广. 本文首先归纳总结了同余的性质及其应用, 在同余的定义的基础上, 介绍了同余的中几个重要的性质, 并且侧重讨论了同余的几个重要的应用, 剩余类和剩余系也是它的研究对象.然后, 我们又归纳总结了

2、同余方程的解及应用, 例如: 一次同余式的形式、解同余式以及解一次同余式组和中国剩余定理的应用等问题, 讨论的过程中由浅入深, 层层推进, 对相关知识的总结形成了较为完整的知识体系, 对解同余方程的一些特殊的性质理解更为深刻.最后, 结合同余理论的概念与性质, 给出常见的习题及解题技巧, 并举例说明了几个重要的同余定理和它们的应用. 关键词： 同余；同余方程；剩余系；一次同余式 AbstractCongruence in number theory is an important part of, It is the concept of divisible extension, after

3、the introduction of congruence simplifies many of the problems in number theory, it is widely used, often encountered in life, it also greatly facilitate and enrich their development, many new theories, techniques and methods are the birth and development of the theory of congruence application and

4、promotion. This paper briefly describes the properties and applications of congruence, on this basis, given the definition of congruence theory, and pointed out several important congruence theory of the nature and focused on the congruence of several applications of the remaining classes and surplu

5、s lines; secondly, summarized congruence equations and applications, such as a congruence in the form of a solution of the congruence reconciliation congruence group and the Chinese Remainder Theorem and other issues, discussions Deep layers of advancing knowledge on the formation of a more complete

6、 knowledge of the system, the solution of some special congruence equation profound understanding of the nature; Finally, combining the concept of congruence theory and nature gives common exercises and problem-solving skills, and an example illustrates several important congruence theorems and thei

7、r applications. Key words: Congruence; Congruence equation; Residue system; Once congruence目 录摘要IAbstractII绪论1第1章 同余的性质及应用2 1.1 同余的概念及基本性质21.2 同余式性质的应用41.2.1 用于解决某些整除问题41.2.2 用于求余数或末位数问题61.2.3 用于解一次不定方程71.2.4 用于处理进制数的有关问题91.2.5 用于周期序列101.3 剩余系和完全剩余系11第2章 同余方程的解及应用142.1 一次同余式142.2 一次同余式组162.3 中国剩余定理及

8、其应用18第3章 几个重要的同余定理及其应用203.1 欧拉定理与费马小定理203.2 佩尔方程22结论24参考文献25致谢26绪 论无论是从理论上还是从应用上来看, 同余理论都是数论中重要的一部分, 初等数论的核心是以同余的性质、 同余的概念为基础发展起来的同余理论, 同余理论是数论所特有的思想, 也是研究余数除法的重要工具.如用于解决某些整除问题、解不定方程、处理进制数的有关问题、周期序列等常常都是同余问题的应用.在国内外数学竞赛中也经常出现数论题和用数论中定理或命题改变的题, 尤其是与同余理论相关的问题, 所以同余理论及其应用日后必为数论中研究的重点知识. 在代数学迅猛发展的今天, 随着

9、初等数论的发展, 国内外越来越多的教学工作者开始研究数论中的同余问题, 他们也取得了丰硕的成果.这里主要列举一下国内学者的研究成果. 2002年, 刘和义“在谈数论中的同余及其应用”中给出了同余理论的几个重要的应用1; 1997年, 朱翠蓉在“同余理论”中给出了同余的概念与一些基本的性质2; 1995年, 林晓燕在“谈同余理论在初等数学中的几点应用”中给出了同余理论在初等数学中用于处理有关整数问题和通过构造剩余系解题的几点应用; 2007年, 姚敦峰在“同余理论与数学竞赛”的期刊中提到了针对同余的性质在数学竞赛的应用和解决方法; 2009年, 陈景润在初等数论（）中详细的讲解了一次同余式得基本

10、解法, 和几个重要的特殊解同余式的方法3 .本文主要从同余的运算性质、性质的应用、剩余类和完全剩余系、方程组的解法、几个重要的同余方面归纳了同余理论的相关知识.通过对这一课题的研究, 我们将对同余理论的特殊性有更加具体的了解.对这些性质的理解主要通过查阅相关图书和电子期刊并运用所学知识归纳总结得到的.本文的重点是归纳总结同余的性质, 更加深入的了解同余理论里的一些特殊性, 并且利用这些特殊的性质解决某些常见的数学问题. 同余理论是一类重要数论问题的, 它的一些特殊性质值得大家牢记.第1章 同余的性质及应用1. 1 同余的概念及基本性质在整数的一些理论和日常生活中, 我们一般都不会太关心一个数是

11、多少, 而只关心这个故事被某一个确定的整数除后的余数是多少, 我们可以用一种特殊的方法处理对余数相同的数, 这就需要引进同余的概念. 定义1.14 设,是两个整数, 如果和用正整数除所得的余数相同, 则称与对于模同余, 记作, 读作同余模. 如果余数都是不相同, 就称与关于模不同余, 记作. 如, 除以余数为, 除以余数也为, 这也就是说,和模对于是同余的, 因此有, , 显然, 同余概念可用下面两个方式之一来定义.若, 则与对模同余; 若（为任意的整数）, 那么就称与对模同余. 上面的三个定义相互之间是等价的, 以后做题我们将不加以区分的随意选用, 熟练的掌握并运用它们, 对谈论分析同余的一

12、些基本性质是非常有用的. 由此定义, 得到了同余的一些基本性质.性质1.1 . 性质1.2 若, 所以. 性质1.3 若 , , 所以. 性质1.4若, , 则（1）; （2）; （3）; 证明 （3） 因为, 所以 , （均为整数）即 即 推论1.1 若, 则（1）（2）. 特别地, 有推论1.2 若, 则. 性质1.5 若且, 则. 证明 因为 所以, （为整数）, 所以, 即 因为 所以, 所以. 特别的, 若 且 则. 性质1.6 若, 且, 则. 证明 设, 又因为, 所以,由得所以 又因为, 所以得. 性质1.7 若, 且则. 性质1.8 若且, 则. 性质1.9 若 且是的公共正

13、约数, 则. 证明 , 也就是, 因为为的公共正约数, 且是正整数, 则有即 性质 1.10 若 则 证明 因为 也就是这也就是说, 是的公倍数, 因而所以有 即 性质1.11 若, , 则证明 因为所以从而又 即有 .1. 2 同余式性质的应用1.2.1 用于解决某些整除问题整除性是数学研究的一个难点, 要想做到调理清楚的证明, 它的技巧性也是很强的, 而技巧方面的东西又很难掌握, 所以通过同余的思想和方法可以非常有效地处理这个难题, 以下这些就是利用同余的一些特殊的性质来解决整除的问题. 例1.1 求任意的一个自然数被除的余数与它的数字和被除的余数相同. 证明 设这个任意的自然数为所以这些

14、各数位字和就是 因为 所以 所以 故任何一个自然数与它各数位上的数字的和被除的余数比相同. 例1.2 证明: . 证明 因为 所以 例1.3有一个整数的次方被除, 它的余数是多少？即试求的可能值有哪些？ 解 这个题分以下的几种特殊的情况讨论:若, 那么易见若由于 所以 由于当时, 有可得 .1.2.2 用于求余数或末位数问题如求一个整数除以某一个正整数的结果所得的余数问题, 同余是一个解决此类问题的非常有用的工具, 也就是说, 求解末尾数是什么或者末尾数有什么特性的问题就可以转化为求这个数除以的余数问题, 求某一个数的末两位是多少的问题其实也就是求这个数除以的余数是多少的问题4. 例1.4 试

15、求除以的余数. 解 对于模来说, 有所以 例1.5 求的最末两位数字.解 因为 所以 又所以 结果是所求的的最末的两位数是. 1.2.3 用于解一次不定方程设整数是整数且, 方程称为元一次不等式方程, 通常我们只是求这个方程的整数解, 以下如没有特别声明, 解都是指数整数解. 定理1.1 二元一次不定方程 （1-1）有解的充分必要条件是. 证明 定理的必要性是显然的, 我们只证明充分性, 设, 则由裴蜀恒等式, 存在整数和, 使得两边同乘以, 得从而方程有整数解, .定理1.25 设二元一次不定方程 (1-2)有解, 是它的一组解, 那么, 它的所有解是 , (1-3)证明 设是任意的整数,

16、把式（2）代入式（1）, 得 所以为整数时, 式（3）均为式（2）的一组解.反过来说, 设是式（2）的一组解, 由 得 因此 所以 可设 即 从而 这就证明了可表示为式的形式.例1.6 求的全部解. 解 很容易的看出是一组特解, 也就是说全部解是 , 例1.7 求不定方程的全部解. 解 由知方程有解, 且 所以 从而在上式子里, 两边同时上乘得是一组特解. 因此方程的全部解是 , 1.2.4 用于处理进制数的有关问题例1.86 当写成进制时, 它的个位数之和为, 设为的各位数字的和, 求的各位数字之和（和用进制的方式表示）.解 设的各位数字之和为, 因为, 所以.设为任一进制整数时, 有则 这

17、表示任一进制数与它的各位数之和对模同余, 故有因为 故 从而 另一方面 所以4至多有位数字, 则在自然数中, 所有数字之和最大的是, 所以, 或者小于等于, 又或者小于或等于的所以自然数中, 的各位数字之和最大, 即, 因此的各位数字之和多为且关于模同余的自然数中只有, 于是. 1.2.5 用于周期序列例1.9 选择一个整数序列 使得（其中）.假如前面项的和是, 而前面的项的和是, 那么前面的项的和是什么呢？ 解 因为 因此, 该序列每六个为一段循环, 即对任意的, 有, .所以, 而且也非常容易证得这个序列, 每六个相近的项的和为. 注意到故 由式和得, 例1.10 数列以下列定义: 求除以

18、所得的余数是什么? 解 由以及, 考虑关于以为模的同余式, 可得由以上可知除以7, 其余数是以为周期地变化, 因此.1.3 剩余系和完全剩余系自从提出同余的概念, 所有的全体的整数分类也是由整数对某一个模的余数所产生的, 所以剩余类产生了. 定义.24 设是一个正整数, 一个整数用除所得的余数不外乎这种, 把全体整数按其余数的不同分为个类, 余数为的为一类, 记作, 则, 称为模的剩余类, 同一类中任意一个数称为该类中另一个数的余数. 定义1.3 以正整数为模, 则全体整数被分成类, 从每一类中取出一个数, 则这为模的完全剩余系. 例如, 让, 所以有 数组为模的一个完全剩余系, 因为是模它们

19、分别同余于数组, 也是模的一个完全剩余系等.模所包含的的完全剩余系有无穷多个, 其实最常见也就是以下两种情况: 非负最小完全剩余系: 绝对值最小完全剩余系: 它随着奇偶性的不同而稍微有些区别: 若为奇数, 则若为偶数, 则或是模的绝对最小完全剩余系. 从前面的内容进行分析可得到每一个整数在且也仅在一个剩余类中, 在中的整数对模都与同余, 在一点可以给出严格的证明, 这就是定理1.3 每一个整数在且仅在关于模的一个剩余类中, 又两个整数在同一个剩余类中的充要条件是.定理1.4 设为任意的整数, 若是模的一个完全剩余系, 所以也是模的一个完全剩余系. 推论1.3 个连续得整数构成了的一个完全剩余系

20、. 定理1.5 若则. 定义1.3 设是模的一个剩余类, 若对于任意, 有 则称的剩余类与模互素. 定义1.4 和互素的剩余类的个数, 记为它是的函数, 称为欧拉函数. 定义1.5 从与互素的每个剩余类中取一个数, 共得个数: 称之为模的简化剩余系, 也称为模的缩剩余系. 定理1.6 倘若为模的简化剩余系, 所以也是模的简化剩余系. 例1.11 设为整数, 要证明: 倘若走遍了模的完全剩余系, 则表示实数的小部分. 证明 当取遍所有的模的完全剩余系时, 还是模的完全剩余系, 则 第2章 同余方程的解及应用2.1 一次同余式定义2.11 同余式叫做一元次同余式, 其中均为整数. 例如, 是七次同

21、余式. 定义2.2 设是一整系数多项式, 若有一整数, 可使, 则叫做同余式的根或解. 定理2.1 同余式若有一个解, 则必有一类解. 证明 因是的一个解, 所以, 将（为整数）代入原同余式左端, 得即（为整数）也是的解.故都是解. 定理 2.2 若, 则有一个解. 定理2.3 若 为正整数, 则是的唯一解. 定理2.4 若, , 则有解, 且有个解. 例2.1 解同余式解 首先把各个系数用它们关于模的最小的正剩余代替, 有因为 所以有一个解, 先求同余式的解, 由, 又所以.故 即, 是的唯一解. 例2.2 求的整数解. 解 由于 就是有整数的解, 则, 得 所以有.由, 由于 (2-1)

22、所以 (2-2) 由(2-1)和(2-2)得.例2.3 解同余式 (2-3)解 因为, 所以同余式(2-3)有解, 由于得到 所以 (2-4)又由(2-3), 有由于, 所以 (2-5)由式(2-4)和(2-5)得由于, , , , 所以的个不同解是.2.2 一次同余式组下面几个同余式联立, 组成了一次同余式组, 例 一次同余式组的解法与一次不等式的解法差不多, 先把每个同余式求解再合并求解. 如样形式的方程叫做一次同余方程.定理2.5 设 (1)若, 则同余式组无解; (2)倘若, 也就是同余式组里面有以为模的一类剩余解. 例2.4 解同余式组.解 由, 有, 也就是说同余式组有解, 由以上

23、的第一个同余式得代入第二个式子, 得 得 即将代入中, 得即同余式组解为. 推论2.15 若两两互素, 则同余式组一直保持有一个以为模的那么一类剩余解. 例2.5 解同余式组 解 因为所以式（2-8）（2-9）均有解, 且可化这两式的解是 因为, 故又定理2. 5知(2-10)和（2-11）有公共解, 且以为模, 显然, 式(2-10)和（2-11）的公共解就是式（2-8）（2-9）的公共解. 式(2-10)和（2-11）也可以写成 即. 2.3 中国剩余定理及其应用一次同余式组的解的问题早在我国古代就应经有非常显著的研究成果, 在孙子算经里提出了一个非常著名的名叫“物不知数”的问题 6 :“

24、今有物不知其数, 三三数之剩二, 五五数之剩三, 七七数之剩二, 问物几何？ “答曰: 二十三”. 下面将介绍驰名中外的孙子定理, 国外称之为中国剩余定理. 定理2.6（孙子定理）7 若, 且是两两互素的个正整数, 令的整数解是.本题里面的是满足于同余式得正整数解. 例2.6 解同余式组解 其中 . 因为, 所以, 有所以, 于是. 第3章 几个重要的同余定理及其应用3.1 欧拉定理与费马小定理欧拉定理 若, 则有. 证明 假设为模的某一个简化剩余系, 则 即 但, 所以也就是说都可以从同余式中约去, 得.欧拉定理是可以推出以下的几个定理的.费马小定理 若是素数, 是正整数, 则. 推论3.1

25、 若为质数, ,则. 定理3.1(欧拉函数值) 设, 为素数, 则定理3.2(欧拉函数值) 设是的标准分解式, 则 例3.1 求被除的余数. 解 因为质数, 且, 由费马小定理得 所以,即被除余. 例3.2 求证: 当为奇数时, 的十进位数末两位数必为. 证明 令, 只需要证 即只需要证 由费马小定理推论, 得 即有.由此得 所以, 当为奇数, 有 由费马小定理可以直接的推导出威尔逊定理, 它的同余方程理论中比较重要的定理. 威尔逊定理 设是质数, 则 威尔逊定理的逆定理8 若, 则为素数. 证明 设为合数, 所以有为真约数, 所以由 及可得 但因, 所以有, 所以得 而结果这是不可能, 故不

26、能为合数, 即为素数. 3.2 佩尔方程大部分的数论问题直到最后都可以归结到方程叫, 其中是给定的正数, 例如或的都是佩尔方程. 定义3.1 对于给定的和, 形如的方程叫做佩尔方程.实际上, 佩尔方程是由费马提出的, 他说不定方程有无数多个解, 而且也还指出, 对于给出的和, 在什么样的情况下是可以解的, 佩尔方程是由欧拉首先给出的, 一直沿用到现在. 定理3.3 当不是某一自然数的平方时, 有无穷多对整数, 满足 定理3.49 存在一个非零的整数, , 使得不定方程 有无穷多组的整数解. 推论3.210 设正整数不是完全平方数, 则存在整数, , 使得 有无穷多组整数解. 例3.3 求的三组

27、正整数解. 解 先求出最小解.当时, , 所以, 即方程的解由下式给出 当时, 有 所以. 当, 有 所以. 于是不定方程有下列解 , , 结 论同余理论是数论中非常重要的一部分, 它所有的一些特殊的性质, 和它的特殊定理及定理的延拓等都是值得大家牢记的, 本文具体从同余的各方面的应用进行由浅及深的讨论.起初, 给出了同余概念, 并且对同余的性质一一的进行表述, 为了更好地在实际问题中应用同余的各类性质, 分别引用了大量的习题加以了解;后来, 我又归纳了同余方程的解及其应用, 包括了一次同余式、一次同余式组、中国剩余定理及其应用.其中, 一次同余式的解法和同余式组的解法为本章的重点和难点, 论

28、述中采用多种方法多角度证明并结合具体同余问题加以说明, 容易去理解.此外, 也讨论了由同余延伸出的欧拉定理与费马定理问题, 其中包括威尔逊定理及威尔逊的逆定理.最后, 讨论佩尔方程及其应用, 其中包括关于佩尔方程的运算性质及其应用.因为本人知识有限, 本文有许多不足之处, 例如, 没有充分列举同余的其他性质, 对于很多性质也没能进一步优化与创新.敬请谅解.参考文献1 刘和义.谈数论中的同余及其应用J.衡水师专学报, 2002,20(4)38-39. 2 朱翠荣 同余理论J.华中师大数学系, 1997,3(2)10-13.3 陈景润.初等数论（）M.厦门:厦门大学出版社, 2009:14-56.

29、4 南秀全, 刘汉文.同余理论M. 哈尔滨: 哈尔滨工业大学出版社, 2002:2-32. 5 潘承洞,潘承彪.初等数论M.北京:北京大学出版社, 1992, 150-268. 6 M.R.Schroedder:Nember theory in science and communication springerverlagM. 1984, 120-145.7 闵嗣鹤, 严士健.初等数论M.北京:人民教育出版社, 1957.3:106-130. 8 HornRA ,JohnsonCR .ModernAlgebraJ.Cambridge:CambridgeUP .1985,5(1)22-25.

30、9 G.H.Hardy E.M.Wright. 数论导引M.张明尧,张凡译.北京:人民邮电出版社.2008:148-152.10 林晓燕.谈同余理论在初等数学中的几点应用J.怀化师专学报,1995,2(1):102-106.11 龚和林, 舒情.关于同余理论的证明和推广J. 大学数学学报, 2009, 25（6）:126-129. 12 Anderson F W, Fuller K R. Rings and Categories of Modules M. (Second Edition)NY: Springer-Verlag, 1992:251-263. 13 朱永松, 杨策平.同余理论的应

31、用 M. 北京:科学出版社, 2003:170-171. 14 杨迎球.中国剩余定理与同余式组J.安顺学院学报, 2009,3(3)12-15. 16 王迪吉, 张维娟.关于一次同余式的解法J. 新疆师范大学学报(自然科学版), 2007:(4).138-173. 17 张亚芳.同余理论在数学竞赛中的应用J.数学学习与研究（教研版）, 2008,9（4）:5-25. 18 David C. Lay, Linear algebra and its applicationsM. Addison-Wesley,2000:102-105. 19 Tom M. Apostol, a first cour

32、se with applications to differential equationsM. NY: Springer-Verlag, 2010:47-55. 致 谢论文完成了, 我主要是想感谢的是我的论文指导老师*老师, 这个论文同余理论及其应用在搜集有关的资料、整理信息和写作、修改定稿中得到了*老师的悉心得帮助与指导.即使我的开题报告和初稿得写作很乱而且有很多应用及语法上的错误,*老师仍然耐心的帮我检查、教我如何改怎样改才能使论文更加完美, 有很多不懂的知识更是一点一滴的告之于我.经过*老师的指导, 我写论文的思路豁然开朗, 对本课题也是有了更深层次的理解.*老师深厚的知识底蕴、严谨的工作态度深深的让我敬佩.通过这一段时间论文的写作, 使我深有感触. 同时, 也要感谢*同学, 她们指点我如何写论文和打印论文及排版问题, 没有他们的帮助我是不可能在这么短的时间里学习并完成该论文的. 所以我非常感谢她们对我论文的帮助, 总之, 本论文的完主要是*老师的悉心指导,和同学的无私帮助.所以, 我要向老师、同学、朋友致以最衷心的感谢！