同余在数学竞赛中的应用

毕业论文题目：同余在数学竞赛中的应用 目 录标题1摘要1引言2161 同余的概念22 同余的基本性质33 同余性质在算术里的应用4 3.1检查因数的一些方法4 3.2弃九法（验证明整数计算结果的方法）5 3.3同余性质的其他应用6 3.3.1利用同余理论求余数6 3.3.2利用同余可以证明整除问题74 利用同余性质求简单同余式的解8 4.1一次同余式、一次同余式解的概念8 4.2 孙子定理解一次同余式组8 4.3 简单高次同余式组及，为质数， 的解数及解法的初步讨论9 4.4简单二次同余式，解的判断11结论13参考文献14致谢15同余在数学竞赛中的应用【摘 要】 同余理论是初等数论的重要组成部分，是研究整数问题的重要工具之一，在处理某些整除性、对整数的分类、解不定方程等方面的问题中有着不可替代的功能。与之相关的数论定理有欧拉定理、费尔马定理、和中国剩余定理。同余是数学竞赛的重要组成部分。本文从数学竞赛这个大范围入手，局限于数论在数学竞赛中的地位和作用，选择同余性质作为切入点，介绍了同余理论的系统知识及同余性质的一些简单应用，并对数学竞赛中有关同余理论的应用作了系统的划分，每一部分都有相关及紧密联系的例题加以举例说明。【关键词】 同余 同余理论 数学竞赛引言数论的一些基础内容的学习，一方面可以加深对数的性质的了解，更深入的理解某些其他邻近学科，另一方面，可以加强数学训练。而整数论知识是学习数论的基础，其中同余理论也是整数论的重要组成部分，所以学好同余理论是非常重要的。在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一固定的数去除所得的余数，例如我们问现在是几点钟，就是用24去除某一个总的时数所得的余数；问现在是星期几，就是问用7去除某一个总的天数所得的余数，假如某月2号是星期一，用7去除这月的号数，余数是2的都是星期一。我国古代孙子算经里已经提出了同余式, 这种形式的问题，并且很好地解决了它。宋代大数学家秦九韶在他的数学九章中提出了同余式, , 是个两两互质的正整数，,的一般解法。同余性质在数论中是基础，许多领域中一些著名的问题及难题都是利用同余理论及一些深刻的数学概念，方法，技巧求解。例如，数论不定方程中的费尔马问题，拉格朗日定理的证明堆垒数论中的华林问题，解析数论中，特征函数基本性质的推导等等。在近现代数论研究中，有关质数分布问题，如除数问题，圆内格点问题，等差级数问题中的质数分布问题，形式的质数个数问题，质数个数问题，质数增大的快慢问题，孪生质数问题都有一定程度的新成果出现，但仍有许多尚未解决的问题。数论的发展以及现代数学发展中提出的一些数论问题，都要求我们对于近代数论的一些方法和基础知识，必须熟练掌握。所以，本文主要介绍了同余理论中同余基本性质的一些简单应用，通过本文的阐述，希望可以为对数论有兴趣的读者，增加学习数论知识的兴趣，并能为他们攻破那些经典的数论难题开展数论课题提供一些帮助。1 同余的概念给定一个正整数，把它叫做模，如果用去除任意两个整数与所得的余数相同，我们就说对模同余，记作,如果余数不同，就说对模不同余。定义（）：如果，则称与关于模 同余；定义（）：若，则称与关于模 同余；显然，若0(mod)，则m。2 同余的基本性质定理1、同余关系是等价关系，因为由同余定义知： ；（反身性）,则；（对称性）,则。 （传递性） 定理2、设（mod）， （mod），则 （1）（mod）；（2）（mod）。证明：（1）（mod），（mod），（）（）（）（），故 （mod）；（2）（）（）， ， 故 （mod）。推论1 若（mod），1，2，则（1）（mod）；（2）（mod）。推论2 若 (mod)，则（mod）。定理3 若（mod），（mod），且（，）1，则 （mod）。证明：（）（），（mod），（）。因（，）1，故，即（mod）。推论 若（mod），且（，）1，则 (mod)。定理4 （欧拉定理）设是大于1的整数，则。 注：若是质数，则。定理5（费尔马定理）设是质数，对于任何整数，都有成立，即证明：（数学归纳法）（1）当时显然成立。（2）假设当时成立，即，则当时，= ，而，（），由归纳法知，即时命题成立，故得证明。推论：是质数，且不能整出，则，即，也成为费尔马小定理。3 同余性质在算术里的应用3.1检查因数的一些方法（1）一整数能被3(9)整除的充要条件是它的十进位数码的和能被3(9)整除。证明：按照通常方法,把任意整数写成十进位数形式,即, 。 因, 所以由同余基本性质,即当且仅当； 同法可得当且仅当，。例1 =5874192，则，36能被3，9整 除，则能被9整除。例2 =435693，则，能被3整除，但不能被9整除当且仅当3是的因数，9不是的因数。（2）设正整数，则7（或11或13）整除的充要条件是7（或11或13）整除，。证明：1000与-1对模7（或11或13）同余根据同余性质知，与对模7（或11或13）同余；即7（或11或13）整除当且仅当7（或11或13）整除，。例3 =637693，则，能被7整除而不能被11或13整除当且仅当7是的因数但11，13不是的因数例4 =75312289，能被13整除，而不能被7，11整除当且仅当13是的因数，而7与11不是的因数（3）应用检查因数的方法求出某个正整数的标准分解式例5 写出1535625的标准分解式解：， ， ， ， ，由例2得， ， 又， ， 。 3.2 弃九法（验证明整数计算结果的方法）我们由普通乘法的运算方法求出整数，的乘积是，并令，如果与对模9不同余，那么所求得的乘积是错误的。特别的，在实际验算中，若，中有9出现，则可去掉（因）。例1 =28997，=39495，按普通计算方法算得，乘积是=1145236515， 按照上述弃九法，。 但与5对模9不同余，所以计算有误。例2 若=28997，=39495，=1145235615，那么。解：按照上述弃九法，。虽然与6对模9同余，但是由通常乘法计算得到，故不成立。注：当使用弃九法时，得出的结果虽然是也还不能完全肯定原计算是正确的。3.3同余性质的其他应用3.3.1利用同余理论求余数利用费尔马定理首先得到，然后利用同余的性质将题中的次数降幂例1 求7除的余数解：由，得 。 即除以7余数为4。例2 试证明：形如的整数不能表为三个平方数之和证明：假定，则，但这不可能。因为对模8而论，每一个整数最小非负余数只能是0，1，2，3，4，5，6，7中的一个数。 而，。 因此，任一整数平方对模8必与0，1，4三个数之一同余，而从0，1，4中任取三个数，其和都不可能与7对模8同余，所以对于任何整数，都有与7对模8不同余。 即形如的整数不能表为三个平方数之和。3.3.2利用同余可以证明整除问题利用，则称与关于模 同余例3 试证明：能被10整除证明：由已知条件有， 又， ，即 也就是说，能被10整除。例4 设且，求证明：证明：对模6来说每一个整数的最小非负数余数为0，1，2，3，4，5 ，即对任何整数， ， 又 故例5 若，证明能被30整除证明：设，则 由， 即， 同理可知 又 故能被30整除。4 利用同余性质求简单同余式的解4.1一次同余式、一次同余式解的概念在代数里面，一个主要问题就是解代数方程。而同余性质在数论中的应用主要体现在同余在方程中的应用，也就是求同余式的解。一次同余式的定义：若用 表示多项式，其中是整数，又设是一个正整数，则 叫做模的同余式。若与0对不同余，则叫做的次数。定义：若是使成立的一个整数，则叫做同余式 的一个解。定理 一次同余式,与0对模不同余,它有解充要条件是。34.2 孙子定理解一次同余式组引例 今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?解：设是所求物数，则依题意有，,孙子算经里介绍用下列方法求解除数余数最小公倍数衍数乘率各 总答 数最 小 答 数32357=1055723522140+63+30=233233-2105=23537312113723511512由表格知，所求物数是23。孙子定理：设,是个两两互质的正整数，,则同余式组, , , 的解是,其中, 4用表格形式概括如下除数余数最小公倍数衍数乘率各 总答 数例1 解同余式组, ，解：此时,，, 。解, 得, , , 即。例2 韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数解：由题意，有，。4.3 简单高次同余式组及 ,为质数，的解数及解法的初步讨论定理1 若, 是个两两互质的正整数, ,则同余式与同余式组,等价。若用 表示,对模的解数, 表示对模的解数，则。例1 解同余式，解： 由定理1知与同余式 , 等价。同余式有两个解，即。同余式有三个解，即。即有六个解，即,。由孙子定理有，即得的解为。定理2 设,即, 是的一解，并且不整除,( 是的导函数),则刚好给出，为质数，的一解, 即, 其中。例2 解同余式解: 由定理1知与,等价。显然，有两解有一解有三解同余式有六个解即,； 由孙子定理得,以,值分别代入，得全部解为。例3 解同余式，解: 有一解，并且3不整除，以 代入得 但，即即因此而是的一解；以代入即即, 即为所求的解。4.4简单二次同余式解的判断二次同余式一般形式为,与0对模不同余，由上面所学知识，经总结，判断一般二次同余式有解与否问题，一定可以转化为判断形如,有解与否问题。先讨论单质数模同余式,有解与否问题若它有解，则叫做模的平方剩余，若它无解，则叫做模的平方非剩余。定理1 若,则是模的平方剩余的充要条件是且有两解；而是模的平方非剩余充要条件是。是勒让得符号，它是一个对于给定单质数定义在一切整数上的函数，它的值规定如下:当时，是模的平方剩余；当时，是模的平方非剩余；当（）=0时，。讨论质数模同余式,有解与否问题 定理2 ,有解的充要条件是，并且在有解情况下，解数是2。讨论合数模同余式,有解与否问题定理3 设,当,时，,有解，且解数是2；当，时，上式有解，解数是4。例 解解: 因故有4个解。把写成代入原同余式，得到， 由此得， 故是适合的一切整数，再代入原同余式得到, 由此得， 故是适合的一切整数,再代入原同余式得到， 由此得出，故是适合的一切整数，因此是所求四个解。结论本文从同余概念及其基本性质出发，通过实例概括总结出同余性质在算术及数论中的一些简单应用。同余性质在算术中的应用主要是通过检查因数和弃九法验算结果的实例作出阐述；数论中同余性质的应用主要体现在简单一次同余式组及高次同余式的求解,以及二次同余式是否有解的判断。 参考文献1闵嗣鹤,严士健编。 初等数论(第二版)M。北京:高等教育出版社,1982。9:37-93。2余元希等。初等代数研究(上)M。北京:高等教育出版社,1988:53-82。3赵振成。中学数学教材教法(修订版)M。上海:华东师范大学出版社,1999。12:53-56。4王书琴，刘晓卫。剩余定理及一次同余式组J。哈尔滨师范大学自然科学学报, 2002-1-17。5法C。布尔勒，朱广才译。 代数M。上海:上海科技出版社,1984。3:72-121。6曹才翰，沈伯英。 初等代数教程M。北京:北京师范大学出版社,1987:76-85。致谢在大学的生活和学习中, 一直得到应用数学系领导和老师们的关心和帮助, 是在他们的谆谆教导下, 我在专业知识的学习中打下了坚实的基础, 在个人修养方面我从他们身上看到了“学高为师、身正为范”的教师风范, 吸取了踏实、严谨、刻苦、认真的治学精神, 以及正直、诚实、守信的人格魅力, 并且在日常生活中身体力行, 以他们为榜样, 加强教师道德修养,