同余的性质及应用.pdf

《同余的性质及应用.pdf》由会员分享，可在线阅读，更多相关《同余的性质及应用.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、22(mod)xbm,(mod)kkxbm这种形式的问题，并且很好地解决了它.宋代大数学家九韶在他的数学九章中提出了同余式1(mod)iixMm,1,2,.,ik,im是k个两两互质的正整数，12.kmm mm,iimm M的一般解法.同余性质在数论中是根底，许多领域中一些著名的问题及难题都是利用同余理论及一些深刻的数学概念，方法，技巧求解.例如，数论不定方程中的费尔马问题，拉格朗日定理的证明堆垒数论中的华林问题，解析数论中，特征函数根本性质的推导等等.在近现代数论研究中，有关质数分布问题，如除数问题，圆格点问题，等差级数问题中的质数分布问题，2anbnc形式的质数个数问题，质数个数问题，质数

3、增大的快慢问题，孪生质数问题都有一定程度的新成果出现，但仍有许多尚未解决的问题.数论的开展以及现代数学开展中提出的一些数论问题，都要求我们对于近代数论的一些方法和根底知识，必须熟练掌握.所以，本文主要介绍了同余理论中同余根本性质的一些简单应用，通过本文的阐述，希望可以为对数论有兴趣的读者，增加学习数论知识的兴趣，并能为他们攻破那些经典的数论难题开展数论课题课题提供一些帮助.2 同余的概念 给定一个正整数m，把它叫做模，如果用m去除任意两个整数a与b所得的余数一样，我们就说对模m同余，记作(mod)abm,如果余数不同，就说对模m不同余.由定义得出同余三条性质：1(mod)aam；2(mod)a

4、bm,则(mod)bam；3(mod)abm,(mod)bcm,则(mod)acm.定义也可描述为:整数a,b对模m同余的充分必要条件是m ab,即abmt,t是整数.3 同余的八条根本性质 由同余的定义和整数的性质得出1：1假设(mod)abm,(mod)cdm,则(mod)acbdm 假设(mod)abcm,则(mod)acbm 2假设(mod)abm,(mod)cdm,则(mod)acbdm 特别地,假设(mod)abm,则(mod)akbkm 3假设11.(mod)kkABm,(mod)iixym,0,1,.,in 则1111.1.1.(mod)kkkkkkAxxByym 4假设1aa

5、 d,1bbd,(,)1d m,(mod)abm,则11(mod)abm 5假设(mod)abm,0k,则(mod)akbkm；假设(mod)abm,d是a,b及m任一正公因数,则(mod)abmddd 6假设(mod)iabm,1,2,.,ik,则12(mod,.,)kabm mm 其中12,.,km mm是12,.,km mm,k个数最小公倍数 7假设(mod)abm,d m,0d,则(mod)abd 8(mod)abm,(,)(,)a mb m,假设d能整除m及a,b两数之一,则d必整除a,b另一个.4 同余性质在算术里的应用 4.1 检查因数的一些方法 例 1 一整数能被 3(9)整除

6、的充要条件是它的十进位数码的和能被3(9)整除.证:按照通常方法,把任意整数a写成十进位数形式,即 1101010.nnnnaaaa,010ia.因101(mod3),所以由同余根本性质,即3 a当且仅当3ia；同法可得9 a当且仅当9ia，0,1,.,in.例 2 设正整数11010001000.nnnnaaaa，01000ia，则 7 或 11 或 13整除a的充要条件是 7或 11 或 13整除0213(.)(.)(1)iiaaaaa，0,1,.,in.证：1000 与-1 对模 7或 11 或 13同余，根据同余性质知，a与(1)iia对模 7或 11 或 13同余 即7 或11 或1

7、3 整除a当且仅当 7 或11 或13 整除(1)iia，0,1,.,in.例 3 a=5874192，则5 874 1 9236ia ，0,1,.,in能被 3，9 整 除，当且仅当a能被 3，9 整除 解：由例 1 证法可知，该结论正确.例 4a=435693，则43 569330ia ，0,1,.,in能被 3 整除，但ia不能被 9 整除当且仅当 3 是a的因数，9 不是a的因数.解：由例 1 的证法可得.例 5 a=637693，则637 1000693a，69363756ia，0,1,.,in能被7 整除而不能被 11 或 13 整除当且仅当 7 是a的因数但 11，13 不是a的

8、因数.解：由例 2 的证法可知，该结论正确.例 6 a=75312289，275 1000312 1000289a 2893127552ia，0,1,.,in能被 13 整除，而不能被 7，11 整除当且仅当 13 是a的因数，而 7 与.11 不是a的因数.解：由例 2 的证法可知.例 7 应用检查因数的方法求出以下各数标准分解式 1535625 1158066 解：65432115356251 105 103 105 106 102 105 ，1 53 562527ia ，9 279 1535625，215356251 1000535 1000625，021()6251 53591aaa，

9、由例 2 得13 91，7 91，7 1535625，13 1535625，又5 1535625，9 5 13 74095，15356253754095，5 375，375755，25 75，5415356253513 7.6543111580661 101 105 108 106 106 ，1 1 5 86627ia ，9 279 1158066，211580661 1000158 100066，021()661 15891aaa ，由例 2 得7 91，13 91 7 1158066，13 1158066，又2 1158066，9 7 13 21638，11580667071638，7 7

10、07，211580662 9 713 101.4.2 弃九法验证整数计算结果的方法 我们由普通乘法的运算方法求出整数a，b的乘积是P，并令 1101010.nnnnaaaa，010ia 1101010.nnnnbbbb，010ib，.1101010.nnnnPccc，010ic，如果()()ijab与kc对模 9 不同余，则所求得的乘积是错误的.特别的，在实际验算中，假设ia，jb，kc中有 9 出现，则可去掉因90(mod9).例 1 a=28997，b=39495，按普通计算方法算得a，b乘积是P=1145236515，按照上述弃九法8(mod9)a，3(mod9)b，5(mod9)P.但

11、8 3与 5 对模 9 不同余，所以计算有误.例 2 假设a=28997，b=39495，P=1145235615，则Pa b？解：按照上述弃九法，8(mod9)a，3(mod9)b，6(mod9)P.虽然8 3与 6 对模 9 同余，但是由通常乘法计算得到1145236515a b，故Pa b不成立.注：当使用弃九法时，得出的结果虽然是()()ijab(mod9)kc也还不能完全肯定原计算是正确的.4.3 同余性质的其他应用 例 1 求 7 除5047的余数.解：由147(2)2(mod7)，2247(2)4(mod7)，5547(2)1(mod 7)，505 16247(47)471 44

12、(mod 7)，即5047除以 7 余数为 4.例 2 试证：形如87()kkN的整数不能表为三个平方数之和.证：假定22287(,)Nkabca b cZ，则2227(mod8)abc，但这不可能.因为对模 8 而论.每一个整数最小非负余数只能是 0，1，2，3，4，5，6，7 中的一个数.而200(mod8)，211(mod8)，224(mod8)，231(mod8)，240(mod8)，251(mod8)，264(mod8)，271(mod8).因此，任一整数平方对模 8 必与 0，1，4 三个数之一同余，而从0，1，4.中任取三个数，其和都不可能与 7 对模 8 同余，所以对于任何整数

13、a，b，c都有222abc与 7 对模 8 不同余.即形如87()kkN的整数不能表为三个平方数之和.例 3 试证：53335333能被 10 整除.证：由 条 件 有533(mod10)，225339(mod10)，555337(mod10)，445331(mod10)，又333(mod10)，223339(mod10)，553337(mod10)，443331(mod10)，53335333(mod10)，即533310(5333)也就是说，53335333能被 10 整除.例 4 设,a b cN且6()abc，求证：3336()abc 证：对模 6 来说每一个整数的最小非负数余数为 0

14、，1，2，3，4，5 300(mod6)，311(mod 6)，322(mod6)，333(mod6)，344(mod6)，355(mod6)，即对任何整数k，3(mod6)kk 3(mod6)aa，3(mod6)bb，3(mod6)cc 又()0(mod 6)abc333()0(mod 6)abc 故3336()abc 例 5 假设(5,)1n，证明5nn能被 30 整除.证：设nN，(mod6)nk则0,1,2,3,4,5k 由500(mod6)，511(mod 6)，522(mod6)，533(mod6)，544(mod6)，555(mod6)，5(mod6)kk即55(mod6)nkk

15、n，56()nn.同理可知55()nn 又(5,6)1530()nn 故5nn能被 30 整除.5 同余性质在数论中的应用：求简单同余式的解 5.1 一次同余式、一次同余式解的概念 在代数里面，一个主要问题就是解代数方程.而同余性质在数论中的应用主要表达在同余在方程中的应用，也就是求同余式的解.一次同余式的定义：假设用()f x 表示多项式110.nnnna xaxa，其中ia是整数，又设m是一个正整数，则()0(mod)f xm 叫做模m的同余式.假设na与0 对m不同余，则n叫做()0(mod)f xm的次数.定义：假设a是使()0(mod)f am成立的一个整数，则(mod)xam 叫做

16、同余式()0(mod)f xm 的一个解.定理 一次同余式(mod)axbm,a与 0 对模m不同余,它有解充要条件是(,)a mb.3 5.2 子定理解一次同余式组 引例 今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何 解:设x是所求物数，则依题意有，2(mod3)x,3(mod5)x,2(mod7)x 子算经里介绍用以下方法求解 除数 余数 最小公倍数 衍数 乘率 各 总 答 数 最 小 答 数 3 2 357=105 57 2 3522 140+63+30=233 233-2105=23 5 3 73 1 2113 7 2 35 1 1512 由表格知，所求物数是 2

17、3.子定理：设1m,2m,km是k个两两互质的正整数，12.kmm mm，iimm M，1,2,.,ik,则同余式组11(mod)xbm,22(mod)xbm,.,.(mod)kkxbm的解是11111 1222.(mod)kkkxM M bMM bMM bm,其中11(mod)iiiM Mm,1,2,.,ik4 用表格形式概括如下 除数 余数 最小公倍数 衍数 乘率 各 总 答 数 1m 1b 12.kMm mm 1M 11M 1111M M b 11(mod)kiiiixM M bm 2m 2b 2M 12M 1222M M b km kb kM 1kM 1kkkM M b 例 1 解同余

18、式组1(mod5)xb,2(mod6)xb，3(mod7)xb，4(mod11)xb.解：此时5 6 7 112310m ,16 7 11462M ,25 7 11385M ，35 6 11330M ,45 6 7210M .解11(mod)iiiM Mm,1,2,3,4i 得113M,121M,131M,141M 即12341386385330210(mod 2310)xbbbb.例 2 信点兵：有兵一队，假设列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数？解:由题意，有1(mod5)x，5(mod6)x，4(mod7)x，10(m

19、od11)x 3 462385 53304210 1067312111(mod 2310)x .5.3 简单高次同余式组()0(mod)if xm,1,2,.,ik及()0(mod)f xp,p为质数，0 的解数及解法的初步讨论 定理 1 假设1m,2m,km是k个两两互质的正整数,12.kmm mm,则同余式()0(mod)f xm与同余式组()0(mod)if xm,1,2,.,ik等价.假设用iT表示()0(mod)if xm,1,2,.,ik,对模im的解数,T表示()0(mod)f xm对模m的解数，则1 2.kTTTT.5 .例 1 解同余式()0(mod35)f x，43()28

20、9f xxxx.解:由定理 1 知()0(mod35)f x 与同余式()0(mod5)f x ,()0(mod 7)f x 等价.同余式()0(mod5)f x 有两个解，即1,4(mod5)x 同余式()0(mod 7)f x 有三个解，即3,5,6(mod 7)x 即()0(mod35)f x 有六个解，即1(mod5)xb,2(mod7)xb 由子定理有，122115(mod35)xbb 即得()0(mod35)f x 的解为31,26,6,24,19,34(mod35)x.定理 2 设1(mod)xxp,即11xxpt,10,1,2,.t 是()0(mod)f xp的一解，并且p不整

21、除1()fx,(1()fx是()f x的导函数),则11xxpt刚好给出()0(mod)f xp，p为质数，0 的一解xxp t,0,1,2,.t,即(mod)xxp,其中1(mod)xxp.6 例 2 解同余式3262717200(mod30)xxx.解:由定理 1 知()0(mod30)f x 与()0(mod 2)f x,()0(mod3)f x,()0(mod5)f x 等价.显然，()0(mod 2)f x 有两解0,1(mod 2)x ()0(mod3)f x 有一解2(mod3)x ()0(mod5)f x 有三解0,1,2(mod5)x 同余式()0(mod30)f x 有六个

22、解 即1(mod2)xb,2(mod3)xb,3(mod5)xb,10,1b；22b；30,1,2b 由子定理得12315106(mod30)xbbb,以1b,2b,3b值分别代入，得()0(mod30)f x 全部解为20,2,26,5,11,17(mod30)x.例 3 解同余式()0(mod 27)f x，4()74f xxx.解:()0(mod3)f x 有一解1(mod3)x，并且 3 不整除1(1)f，以11 3xt 代入()0(mod9)f x 得11(1)3(1)0(mod9)ft f 但(1)3(mod9)f，1(1)2(mod9)f 即13320(mod9)t即1210(m

23、od3)t 因此121 3tt 而221 3(13)49xtt 是()0(mod9)f x 的一解；以249xt代入()0(mod 27)f x 即12(4)9(4)0(mod 27)ft f,2189200(mod 27)t即2220(mod3)t,2323tt 即3349(23)2227xtt为所求的解.5.4 简单二次同余式2(mod)xap,0,(,)1a p 解的判断 二次同余式一般形式为20(mod)axbxcm,a与 0 对模m不同余，由上面所学知识，经总结，判断一般二次同余式有解与否问题，一定可以转化为判断形如2(mod)xap,0 有解与否问题.先讨论单质数模同余式2(mod

24、)xap,(,)1a p 有解与否问题 假设它有解，则a叫做模p的平方剩余，假设它无解，则a叫做模p的平方非剩余.定理 1 假设(,)1a p,则a是模p的平方剩余的充要条件是121(mod)pap且有两解；而a是模p的平方非剩余充要条件是121(mod)pap.7()ap是勒让得符号，它是一个对于给定单质数p定义在一切整数a上的函数，它的值规定如下:当()1ap时，a是模p的平方剩余；.当()1ap 时，a是模p的平方非剩余；当pa=0 时，p a.8 讨论质数模同余式2(mod)xap,0,(,)1a p 有解与否问题 定理 22(mod)xap,0,(,)1a p 有解的充要条件是()1

25、ap，并且在有解情况下，解数是 2.9 讨论合数模同余式2(mod2)xa,0,(2,)1a 有解与否问题 定理 3 设1,当2,1(mod 4)a 时，2(mod2)xa,0,(2,)1a 有解，且解数是 2；当3，1(mod8)a 时，上式有解，解数是 4.10 例 解257(mod64)x.解:因571(mod8)故有 4 个解.把x写成3(14)xt 代入原同余式,得到23(14)57(mod16)t,由此得 31(mod 2)t,故4414(12)(58)xtt 是适合257(mod16)x 的一切整数，再代入原同余式得到24(58)57(mod32)t,由此得 40(mod2)t,

26、故55(58 2)(5 16)xtt 是适合257(mod32)x 的一切整数,再代入原同余式得到25(5 16)57(mod 64)t,由此得 51(mod 2)t,故665 16(12)(2132)xtt 是适合257(mod64)x 的一切整数，因此21,53,21,53(mod 64)x 是所求四个解.6 结论 本文从同余概念及其根本性质出发，通过实例概括总结出同余性质在算术及数论中的一些简单应用.同余性质在算术中的应用主要是通过检查因数和弃九法验算结果的实例作.出阐述;数论中同余性质的应用主要表达在简单一次同余式组及高次同余式的求解,以及二次同余式是否有解的判断.参考文献 1闵嗣鹤,

27、严士健编.初等数论(第二版)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.7合义.谈数论中的同余及其应用J.学院学报,2007:2-6.8H.B.勃罗斯库列亚柯夫，吴品三译.数与多项式M.:高等教育,1980:42.9林国泰,司徒永显.初等代

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