您好,欢迎访问三七文档
同余的性质及应用1引言数论的一些基础内容的学习,一方面可以加深对数的性质的了解,更深入的理解某些其他邻近学科,另一方面,可以加强数学训练.而整数论知识是学习数论的基础,其中同余理论有时整数论的重要组成部分,所以学好同余理论是非常重要的.在日常生活中,我们所要注意的常常不是某些整数,而是这些数用某一固定的数去除所得的余数,例如我们问现在是几点钟,就是用24去除某一个总的时数所得的余数;问现在是星期几,就是问用7去除某一个总的天数所得的余数,假如某月2号是星期一,用7去除这月的号数,余数是2的都是星期一.我国古代孙子算经里已经提出了同余式11(mod)xbm,22(mod)xbm,…,(mod)kkxbm这种形式的问题,并且很好地解决了它.宋代大数学家秦九韶在他的《数学九章》中提出了同余式1(mod)iixMm,1,2,...,ik,im是k个两两互质的正整数,12...kmmmm,iimmM的一般解法.同余性质在数论中是基础,许多领域中一些著名的问题及难题都是利用同余理论及一些深刻的数学概念,方法,技巧求解.例如,数论不定方程中的费尔马问题,拉格朗日定理的证明堆垒数论中的华林问题,解析数论中,特征函数基本性质的推导等等.在近现代数论研究中,有关质数分布问题,如除数问题,圆内格点问题,等差级数问题中的质数分布问题,2anbnc形式的质数个数问题,质数个数问题,质数增大的快慢问题,孪生质数问题都有一定程度的新成果出现,但仍有许多尚未解决的问题.数论的发展以及现代数学发展中提出的一些数论问题,都要求我们对于近代数论的一些方法和基础知识,必须熟练掌握.所以,本文主要介绍了同余理论中同余基本性质的一些简单应用,通过本文的阐述,希望可以为对数论有兴趣的读者,增加学习数论知识的兴趣,并能为他们攻破那些经典的数论难题开展数论课题课题提供一些帮助.12同余的概念给定一个正整数m,把它叫做模,如果用m去除任意两个整数a与b所得的余数相同,我们就说对模m同余,记作(mod)abm,如果余数不同,就说对模m不同余.由定义得出同余三条性质:(1)(mod)aam;(2)(mod)abm,则(mod)bam;(3)(mod)abm,(mod)bcm,则(mod)acm.定义也可描述为:整数a,b对模m同余的充分必要条件是mab,即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)若1aad,1bbd,(,)1dm,(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[,,...,])kabmmm2其中12[,,...,]kmmm是12,,...,kmmm,k个数最小公倍数(7)若(mod)abm,dm,0d,则(mod)abd(8)(mod)abm,(,)(,)ambm,若d能整除m及a,b两数之一,则d必整除a,b另一个.4同余性质在算术里的应用4.1检查因数的一些方法例1一整数能被3(9)整除的充要条件是它的十进位数码的和能被3(9)整除.证:按照通常方法,把任意整数a写成十进位数形式,即1101010...nnnnaaaa,010ia.因101(mod3),所以由同余基本性质,即3a当且仅当3ia;同法可得9a当且仅当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或13)整除a当且仅当7(或11或13)整除(1)iia,0,1,...,in.例3a=5874192,则587419236ia,0,1,...,in能被3,9整除,当且仅当a能被3,9整除解:由例1证法可知,该结论正确.例4a=435693,则43569330ia,0,1,...,in能被3整除,但ia不能被9整除当且仅当3是a的因数,9不是a的因数.解:由例1的证法可得.3例5a=637693,则6371000693a,69363756ia,0,1,...,in能被7整除而不能被11或13整除当且仅当7是a的因数但11,13不是a的因数.解:由例2的证法可知,该结论正确.例6a=75312289,27510003121000289a2893127552ia,0,1,...,in能被13整除,而不能被7,11整除当且仅当13是a的因数,而7与11不是a的因数.解:由例2的证法可知.例7应用检查因数的方法求出下列各数标准分解式①1535625②1158066解:①65432115356251105103105106102105,153562527ia,92791535625,21535625110005351000625,021()625153591aaa,由例2得1391,791,71535625,131535625,又51535625,951374095,15356253754095,5375,375755,2575,54153562535137.②6543111580661101105108106106,11586627ia,92791158066,2115806611000158100066,021()66115891aaa,由例2得791,139171158066,131158066,4又21158066,971321638,11580667071638,7707,2115806629713101.4.2弃九法(验证整数计算结果的方法)我们由普通乘法的运算方法求出整数a,b的乘积是P,并令1101010...nnnnaaaa,010ia1101010...nnnnbbbb,010ib,1101010...nnnnPccc,010ic,如果()()ijab与kc对模9不同余,那么所求得的乘积是错误的.特别的,在实际验算中,若ia,jb,kc中有9出现,则可去掉(因90(mod9)).例1a=28997,b=39495,按普通计算方法算得a,b乘积是P=1145236515,按照上述弃九法8(mod9)a,3(mod9)b,5(mod9)P.但83与5对模9不同余,所以计算有误.例2若a=28997,b=39495,P=1145235615,那么Pab?解:按照上述弃九法,8(mod9)a,3(mod9)b,6(mod9)P.虽然83与6对模9同余,但是由通常乘法计算得到1145236515ab,故Pab不成立.注:当使用弃九法时,得出的结果虽然是()()ijab(mod9)kc也还不能完全肯定原计算是正确的.4.3同余性质的其他应用例1求7除5047的余数.解:由147(2)2(mod7),2247(2)4(mod7),5547(2)1(mod7),550516247(47)47144(mod7),即5047除以7余数为4.例2试证:形如87()kkN的整数不能表为三个平方数之和.证:假定22287(,,)NkabcabcZ,则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同余,所以对于任何整数a,b,c都有222abc与7对模8不同余.即形如87()kkN的整数不能表为三个平方数之和.例3试证:53335333能被10整除.证:由已知条件有533(mod10),225339(mod10),555337(mod10),445331(mod10),5341541553(53)53(3)3133(mod10)又333(mod10),223339(mod10),553337(mod10),443331(mod10),33484833(33)33(3)3133(mod10)53335333(mod10),即533310(5333)也就是说,53335333能被10整除.例4设,,abcN且6()abc,求证:3336()abc6证:对模6来说每一个整数的最小非负数余数为0,1,2,3,4,5300(mod6),311(mod6),322(mod6),333(mod6),344(mod6),355(mod6),即对任何整数k,3(mod6)kk3(mod6)aa,3(mod6)bb,3(mod6)cc333()()(mod6)abcabc又()0(mod6)abc333()0(mod6)abc故3336()abc例5若(5,)1n,证明5nn能被30整除.证:设nN,(mod6)nk则0,1,2,3,4,5k由500(mod6),511(mod6),522(mod6),533(mod6),544(mod6),555(mod6),5(mod6)kk即55(mod6)nkkn,56()nn同理可知55()nn又(5,6)1530()nn故5nn能被30整除.5同余性质在数论中的应用:求简单同余式的解5.1一次同余式、一次同余式解的概念在代数里面,一个主要问题就是解代数方程.而同余性质在数论中的应用主要体现在同余在方程中的应用,也就是求同余式的解.一次同余式的定义:若用()fx表示多项式110...nnnnaxaxa,其中ia是整数,又设m是一个正整数,则()0(mod)fxm叫做模m的同余式.若na与07对m不同余,则n叫做()0(mod)fxm的次数.定义:若a是使()0(mod)fam成立的一个整数,则(mod)xam叫做同余式()0(mod)fxm的一个解.定理一次同余式(mod)axbm,a与0对模m不同余,它有解充要条件是(,)amb.[3]5.2孙子定理解一次同余式组引例今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?解:设x是所求物数,则依题意有,2(mod3)x,3(mod5)x,2(mod7)x孙子算经里介绍用下列方法求解除数余数最小公倍数衍数乘率各总答数最小答数32357=105572
本文标题:同余的性质与应用
链接地址:https://www.777doc.com/doc-6304332 .html