同余的性质及应用

《同余的性质及应用》由会员分享，可在线阅读，更多相关《同余的性质及应用（13页珍藏版）》请在装配图网上搜索。

1、.同余的性质及应用1 引言数论的一些根底容的学习，一方面可以加深对数的性质的了解，更深入的理解*些其他邻近学科，另一方面，可以加强数学训练.而整数论知识是学习数论的根底，其中同余理论有时整数论的重要组成局部，所以学好同余理论是非常重要的.在日常生活中，我们所要注意的常常不是*些整数，而是这些数用*一固定的数去除所得的余数，例如我们问现在是几点钟，就是用24去除*一个总的时数所得的余数；问现在是星期几，就是问用7去除*一个总的天数所得的余数，假设*月2号是星期一，用7去除这月的号数，余数是2的都是星期一.我国古代子算经里已经提出了同余式,这种形式的问题，并且很好地解决了它.宋代大数学家九韶在他的

2、数学九章中提出了同余式,是个两两互质的正整数，,的一般解法.同余性质在数论中是根底，许多领域中一些著名的问题及难题都是利用同余理论及一些深刻的数学概念，方法，技巧求解.例如，数论不定方程中的费尔马问题，拉格朗日定理的证明堆垒数论中的华林问题，解析数论中，特征函数根本性质的推导等等.在近现代数论研究中，有关质数分布问题，如除数问题，圆格点问题，等差级数问题中的质数分布问题，形式的质数个数问题，质数个数问题，质数增大的快慢问题，孪生质数问题都有一定程度的新成果出现，但仍有许多尚未解决的问题.数论的开展以及现代数学开展中提出的一些数论问题，都要求我们对于近代数论的一些方法和根底知识，必须熟练掌握.所

3、以，本文主要介绍了同余理论中同余根本性质的一些简单应用，通过本文的阐述，希望可以为对数论有兴趣的读者，增加学习数论知识的兴趣，并能为他们攻破那些经典的数论难题开展数论课题课题提供一些帮助.2 同余的概念给定一个正整数，把它叫做模，如果用去除任意两个整数与所得的余数一样，我们就说对模同余，记作,如果余数不同，就说对模不同余.由定义得出同余三条性质：1；2,则；3,则.定义也可描述为:整数,对模同余的充分必要条件是,即,是整数.3 同余的八条根本性质由同余的定义和整数的性质得出1：1假设,则 假设, 则2假设, 则特别地,假设,则3假设,则4假设,则5假设, 则；假设,是,及任一正公因数,则6假设

4、,则其中是, 个数最小公倍数7假设,则8,假设能整除及,两数之一,则必整除,另一个.4 同余性质在算术里的应用4.1检查因数的一些方法例1 一整数能被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 =5874192，则，能被3，9整 除，当且仅当能被3，9整除解：由例

5、1证法可知，该结论正确.例4=435693，则，能被3整除，但不能被9整除当且仅当3是的因数，9不是的因数.解：由例1的证法可得.例5 =637693，则，能被7整除而不能被11或13整除当且仅当7是的因数但11，13不是的因数.解：由例2的证法可知，该结论正确.例6 =75312289，能被13整除，而不能被7，11整除当且仅当13是的因数，而7与11不是的因数.解：由例2的证法可知.例7 应用检查因数的方法求出以下各数标准分解式1535625 1158066解：，由例2得， 又，.，由例2得， 又，.4.2 弃九法验证整数计算结果的方法我们由普通乘法的运算方法求出整数，的乘积是，并令，如果

6、与对模9不同余，则所求得的乘积是错误的.特别的，在实际验算中，假设，中有9出现，则可去掉因.例1 =28997，=39495，按普通计算方法算得，乘积是=1145236515， 按照上述弃九法，. 但与5对模9不同余，所以计算有误.例2 假设=28997，=39495，=1145235615，则？解：按照上述弃九法，.虽然与6对模9同余，但是由通常乘法计算得到，故不成立.注：当使用弃九法时，得出的结果虽然是也还不能完全肯定原计算是正确的.4.3 同余性质的其他应用例1 求7除的余数.解：由， 即除以7余数为4.例2 试证：形如的整数不能表为三个平方数之和.证：假定，则，但这不可能.因为对模8而

7、论.每一个整数最小非负余数只能是0，1，2，3，4，5，6，7中的一个数.而，. 因此，任一整数平方对模8必与0，1，4三个数之一同余，而从0，1，4中任取三个数，其和都不可能与7对模8同余，所以对于任何整数，都有与7对模8不同余. 即形如的整数不能表为三个平方数之和.例3 试证：能被10整除.证：由条件有， 又，即 也就是说，能被10整除.例4 设且，求证：证：对模6来说每一个整数的最小非负数余数为0，1，2，3，4，5，即对任何整数， 又 故例5 假设，证明能被30整除.证：设，则由，即， 同理可知 又 故能被30整除.5 同余性质在数论中的应用：求简单同余式的解5.1一次同余式、一次同余

8、式解的概念在代数里面，一个主要问题就是解代数方程.而同余性质在数论中的应用主要表达在同余在方程中的应用，也就是求同余式的解.一次同余式的定义：假设用 表示多项式，其中是整数，又设是一个正整数，则 叫做模的同余式.假设与0对不同余，则叫做的次数.定义：假设是使成立的一个整数，则叫做同余式 的一个解.定理 一次同余式,与0对模不同余,它有解充要条件是.35.2 子定理解一次同余式组引例 今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何解:设是所求物数，则依题意有，,子算经里介绍用以下方法求解除数余数最小公倍数衍数乘率各 总答 数最 小 答 数32357=1055723522140

9、+63+30=233233-2105=23537312113723511512由表格知，所求物数是23.子定理：设,是个两两互质的正整数，,则同余式组, , 的解是,其中,4用表格形式概括如下除数余数最小公倍数衍数乘率各 总答 数例1 解同余式组, ，.解：此时,，, .解, 得,即.例2 信点兵：有兵一队，假设列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数？解:由题意，有，.5.3 简单高次同余式组, 及,为质数，的解数及解法的初步讨论定理1 假设,是个两两互质的正整数,则同余式与同余式组,等价.假设用表示,对模的解数, 表示对模的

10、解数，则.5例1 解同余式，.解: 由定理1知与同余式 ,等价.同余式有两个解，即同余式有三个解，即即有六个解，即,由子定理有，即得的解为.定理2 设,即,是的一解，并且不整除,(是的导函数),则刚好给出，为质数，的一解, 即, 其中.6例2 解同余式.解: 由定理1知与,等价.显然，有两解有一解有三解同余式有六个解即,； 由子定理得,以,值分别代入，得全部解为.例3 解同余式，.解:有一解，并且3不整除，以 代入得 但，即即因此而是的一解；以代入即,即, 即为所求的解.5.4 简单二次同余式,解的判断二次同余式一般形式为,与0对模不同余，由上面所学知识，经总结，判断一般二次同余式有解与否问题

11、，一定可以转化为判断形如,有解与否问题.先讨论单质数模同余式,有解与否问题假设它有解，则叫做模的平方剩余，假设它无解，则叫做模的平方非剩余.定理1 假设,则是模的平方剩余的充要条件是且有两解；而是模的平方非剩余充要条件是.7是勒让得符号，它是一个对于给定单质数定义在一切整数上的函数，它的值规定如下:当时，是模的平方剩余；当时，是模的平方非剩余；当=0时，.8讨论质数模同余式,有解与否问题 定理2,有解的充要条件是，并且在有解情况下，解数是2.9讨论合数模同余式,有解与否问题定理3 设,当,时，,有解，且解数是2；当，时，上式有解，解数是4.10例 解.解: 因故有4个解.把写成代入原同余式,得

12、到, 由此得, 故是适合的一切整数，再代入原同余式得到, 由此得, 故是适合的一切整数,再代入原同余式得到, 由此得, 故是适合的一切整数，因此是所求四个解.6 结论本文从同余概念及其根本性质出发，通过实例概括总结出同余性质在算术及数论中的一些简单应用.同余性质在算术中的应用主要是通过检查因数和弃九法验算结果的实例作出阐述;数论中同余性质的应用主要表达在简单一次同余式组及高次同余式的求解,以及二次同余式是否有解的判断. 参考文献1闵嗣鹤,严士健编. 初等数论(第二版)M.:高等教育,1982.9:37-93.2余元希等.初等代数研究(上)M.:高等教育,1988:53-82.3振成.中学数学教

13、材教法(修订版)M.:华东师大学,1999.12:53-56.4王书琴，晓卫.剩余定理及一次同余式组J.师大学自然科学学报, 2002-1-17.5法C.布尔勒，朱广才译. 代数M.:科技,1984.3:72-121.6才翰，伯英. 初等代数教程M.:师大学,1987:76-85.7合义.谈数论中的同余及其应用J.学院学报,2007:2-6.8H.B.勃罗斯库列亚柯夫，吴品三译. 数与多项式M.:高等教育,1980:42.9林国泰,司徒永显. 初等代数研究教程M.:暨南大学,1996:81-96.10林六十. 初等代数研究M.:中国地质大学,1989:145-158.致 在大学的生活和学习中,

14、 一直得到应用数学系领导和教师们的关心和帮助, 是在他们的谆谆教导下, 我在专业知识的学习中打下了坚实的根底, 在个人修养方面我从他们身上看到了学高为师、身正为的教师风, 吸取了踏实、严谨、刻苦、认真的治学精神, 以及正直、老实、守信的人格魅力, 并且在日常生活中身体力行, 以他们为典范, 加强教师道德修养, 努力丰富自己、完善自己.我在大学期间取得的所有成绩都是和系领导以及教师们的帮助和教导分不开的, 在此向他们致以衷心的感和良好的祝愿.在这学期撰写毕业论文的过程中, 得到了善辉教师的悉心指导, 熟悉了撰写论文的一般格式和许多考前须知, 这对于我以后的学习和生活都具有很好的示作用. 感善辉教师的帮助和指导！在我论文的撰写和校对过程中, 还得到了许多同学的帮助, 是他们帮助我发现论文里的*些小小的错误, 这使我节省了时间去完成其他的工作, 在此向他们表示感.最后, 再次感善辉教师的辛勤指导！.