同余的性质与应用教学内容

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

2、2(modm2),xbk(modmk)这种形式的问题，并且很好地解决了它.宋代大数学家秦九韶在他的数学九章中提出了同余式x Mi1(modmi), i 1,2,., k , mj是k个两两互质的正整数，m 口口:口).，m mMj的一般解法.同余性质在数论中是基础，许多领域中一些著名的问题及难题都是利用同余理论 及一些深刻的数学概念，方法，技巧求解.例如，数论不定方程中的费尔马问题，拉 格朗日定理的证明堆垒数论中的华林问题，解析数论中，特征函数基本性质的推导等 等.在近现代数论研究中，有关质数分布问题，如除数问题，圆内格点问题，等差级 数问题中的质数分布问题，an2 bn c形式的质数个数问题

3、，质数个数问题，质数增 大的快慢问题，孪生质数问题都有一定程度的新成果出现，但仍有许多尚未解决的问 题.数论的发展以及现代数学发展中提出的一些数论问题，都要求我们对于近代数论 的一些方法和基础知识，必须熟练掌握.所以，本文主要介绍了同余理论中同余基本 性质的一些简单应用，通过本文的阐述，希望可以为对数论有兴趣的读者，增加学习 数论知识的兴趣，并能为他们攻破那些经典的数论难题开展数论课题课题提供一些帮 助.仅供学习与交流，如有侵权请联系网站删除谢谢0精品资料2同余的概念给定一个正整数m，把它叫做模，如果用m去除任意两个整数a与b所得的余数 相同，我们就说对模m同余，记作a b(modm),如果余

4、数不同，就说对模 m不同余. 由定义得出同余三条性质：(1) a a(mod m)；(2) a b(mod m),贝U b a(mod m)；(3) a b(mod m), b c(mod m),贝U a c(modm).定义也可描述为：整数a , b对模m同余的充分必要条件是 ma b ,即a b mt, t是整 数.3同余的八条基本性质由同余的定义和整数的性质得出:(1)若 ab(mod m), cd (mod m),贝U a c b d (mod m)若ab c(mod m),则a cb(mod m)(2)若ab(mod m), cd (mod m),贝U ac bd(mod m)特别地

5、,若 a b(mod m),贝U ak bk(mod m)(3)若Ai.kB i. k(mod m), Xjyi (mod m), i 0,1,., n则Ai.kXi 1.Xk kBi1.yk k (mod m)(4)若aa1d ,bb1d ,(d,m)1, a b(mod m),贝U ab1 (mod m)(5)若ab(mod m), k0,则 akbk(mod m);若ab(mod m), d是a , b及m任一正公因数,则-d-(mod m)dd(6) 右 a b(mod mi) , i 1,2,., k ,则 a b(mod mm?,., mk)其中m1, m2,., mk是gm,.,

6、 mk, k个数最小公倍数(7) 若 a b(mod m), d.m,d 0 ,则 a b(mod d)(8) a b(modm), (a,m)(b, m),若d能整除m及a , b两数之一，则d必整除a , b另一个.4同余性质在算术里的应用4.1 检查因数的一些方法例1 一整数能被3(9)整除的充要条件是它的十进位数码的和能被3(9)整除.证：按照通常方法，把任意整数a写成十进位数形式，即nn 1a an10an 110. a。，0 ai 10.因101(mod3),所以由同余基本性质，即3a当且仅当3;同法可得9 a当且仅当9ai，i 0,1,., n.例 2 设正整数 a an1000

7、n a. 11000n 1 . a。，0 ai 1000，则 7 (或 11 或13)整除a的充要条件是7 (或11或13)整除2 a ao0,1,., n .证：1000与-1对模7 (或11或13)同余，根据同余性质知，a与 (1)i ai对模7 (或11或13)同余即7 (或11或13)整除a当且仅当7 (或11或13)整除 (1)iai ,i 0,1,., n.例 3 a =5874192,则 ai 5 8 7 4 1 9 2 36，i 0,1,., n 能被 3，9 整除，当且仅当a能被3, 9整除解:由例1证法可知，该结论正确.仅供学习与交流，如有侵权请联系网站删除谢谢1精品资料例

8、 4 a =435693,则 a 4 3 5 6 9 3 30 , i 0,1,., n 能被 3 整除，但ai不能被9整除当且仅当3是a的因数，9不是a的因数.解：由例1的证法可得.例 5 a =637693,则 a 637 1000 693， q 693 637 56，i 0,1,., n 能被7整除而不能被11或13整除当且仅当7是a的因数但11，13不是a的因数. 解：由例2的证法可知，该结论正确.例 6 a =75312289, a 75 10002 312 1000 289ai 289 312 75 52，i 0,1,., n能被13整除，而不能被7，11整除当且仅当13是a的因数

9、，而7与 11不是a的因数.解：由例2的证法可知.例7应用检查因数的方法求出下列各数标准分解式15356251158066解：51053 104 5 1036 1022 1015，a 153 56 2 5 27，9 2791535625 ，1535625121000535 1000 625，（a。 a2）a16251 53591，由例 2得 1391，791，71535625，131535625，1535625又 51535625，9 5 13 7 4095，375，40953755 375，75，25 75，5153562535 54 13 7. 115806611

10、0611055 1048 1036 1016，a 1 1 5 8 6 627，9/279/1158066，11580661100021581000 66，(a0 a2) a1 66 1 15891，由例 2 得 7, 91 , 13 917 1158066 , 13 1158066 ,又 2.1158066 , 9 7 13 2 1638, 1158066 707 , 7 707 , 1638211580662 9 713 101 .4.2 弃九法(验证整数计算结果的方法)我们由普通乘法的运算方法求出整数 a , b的乘积是P，并令aan10nn 1an 110.a0 ,0ai10bbn10n

11、n 1bn 110.b0 ,0b10 ,PCn10nn 1Cm10.c0 ,0Ci10,如果(aj( bj)与ck对模9不同余，那么所求得的乘积是错误的.特别的，在实际验算中，若ai , bj , 0.中有9出现，贝U可去掉(因9 0(mod9).例1 a =28997, b =39495，按普通计算方法算得a , b乘积是P =1145236515,按照上述弃九法 a 8(mod9) , b 3(mod9) , P 5(mod9).但8 3与5对模9不同余，所以计算有误例 2 若 a =28997, b =39495, P =1145235615,那么 P a b ?解：按照上述弃九法，a

12、8(mod9) , b 3(mod9) , P 6(mod9).虽然8 3与6对模9同余，但是由通常乘法计算得到 a b 1145236515 ,故P a b不成立.注：当使用弃九法时，得出的结果虽然是(ai)( bj)ck(mod9)也还不能完全肯定原计算是正确的.4.3 同余性质的其他应用例1求7除4750的余数.解：由 47 ( 2)12(mod7) , 472 ( 2)2 4(mod 7),5547( 2)1(mod7),4750(475)16 4721 4 4(mod 7),即4750除以7余数为4.例2试证：形如8k 7(k N)的整数不能表为三个平方数之和.证：假定 N 8k 7

13、 a2 b2 c2(a,b,c Z)，则 a2 b2 c2 7(mod8)，但这不 可能.因为对模8而论.每一个整数最小非负余数只能是 0，1, 2, 3, 4, 5，6，7中的一个数.而 020(mod8)，121(mod8)，224(mod8)，321(mod8)，42 0(mod8)，52 1(mod8)，62 4(mod8)，72 1(mod8).因此，任一整数平方对模 8必与0，1, 4三个数之一同余，而从 0, 1, 4中任取三个数，其和都不可能与 7对模8同余，所以对于任何整数a , b , c都有a2 b2 c2与7对模8不同余.即形如8k 7(k N)的整数不能表为三个平方数

14、之和.例3试证：5353 3333能被10整除.证：由已知条件有 53 3(mod10) , 532 32 9(mod10) , 535 35 7(mod10),445331(mod10),5353(534)15 53(34)15 3 1 33(mod10)2255又 333(mod10) , 3339(mod10) , 3337(mod10),334341(mod10),334 84 833(33 )33 (3 )31 3 3(mod10)5353 3333(mod10)，即 10 (5353 3333)也就是说，5353 3333能被10整除.例 4 设 a,b,c N 且6 (a b c

15、)，求证：6 (a3 b3 c3)证：对模6来说每一个整数的最小非负数余数为0, 1, 2, 3, 4, 533333k k(mod 6)0 0(mod 6) , 1 1(mod 6) , 2 2(mod 6) , 3 3(mod 6),3a (mod 6) , b b(mod 6),43 4(mod 6) , 53 5(mod 6)，即对任何整数 k ,(a3b3c3) (a bc)(mod 6)又(abc)0(mod 6)(a3 b3 c3) 0(mod 6)故6(3 ab3c3)例5若(5, n)1,证明n5n能被30整除.证：设nN ,nk(mod6)贝U k 0,1,2,3,4,53

16、 ac3 c(mod 6)由 05 0(mod 6) , 151(mod6) , 25 2(mod 6), 353(mod6),45 4(mod 6) , 55 5(mod 6),k5 k(mod 6)即 n5 k5 k n(mod 6), 6 (n5 n)同理可知5 (n5 n)又(5,6)130. (n5 n)故n5 n能被30整除.5同余性质在数论中的应用：求简单同余式的解5.1 一次同余式、一次同余式解的概念仅供学习与交流，如有侵权请联系网站删除 谢谢7精品资料在代数里面，一个主要问题就是解代数方程.而同余性质在数论中的应用主要体现在同余在方程中的应用，也就是求同余式的解.一次同余式的

17、定义：若用f(x)表示多项式anXn an ixn 1 . ao，其中ai 是整数，又设m是一个正整数，则f (x) 0(mod m)叫做模m的同余式.若an与 0对m不同余，则n叫做f (x) 0(mod m)的次数.定义：若a是使f(a) 0(mod m)成立的一个整数，则x a(mod m)叫做同余式f(x) 0(mod m)的一个解.定理 一次同余式ax b(modm),a与0对模m不同余,它有解充要条件是(a,m)b .35.2孙子定理解一次同余式组引例今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？解：设x是所求物数，则依题意有，x 2(mod3) , x 3(

18、mod5) , x 2(mod7)孙子算经里介绍用下列方法求解除数余数最小公倍数衍数乘率各总答数最小答数325 72352 2140+63+233-533 5 7=1057 31211 330=2332 105=23723 51151 2由表格知，所求物数是23.孙子定理：设 mj, m2,mk是k个两两互质的正整数， m mm2.mk，mmiMi， i 1,2,., k ,则同余式组 x b/modmj.x b2(mod m2), . , x bk(modmk)的解是x M 11M1b1 MJ2M2b2 . M 1kMkbk(mod m),其中 MM j 1(modm),1,2,., k用表

19、格形式概括如下除数余数最小公倍数衍数乘率各总答数b1Mm1m2.mkM1M111M 1M 1b1k1xM iM ibi(mod m)i 1m2b2m2M121M 2M2b2mkbkMkM1k1M kM k bk例 1 解同余式组 x b)(mod5), x d(mod 6) , x b3(mod 7) , x b4(mod11).解：此时 m 5 6 7 11 2310, M16 7 11462, M 25 7 11385 ,M3 5 6 11 330,M4 5 6 7 210.解 M jMj 1(modmJ, i 1)2,3,4 得 M1 3, M 2 1, M 3 1, M 4 1即 x

20、1386D 3850 330b3210b4(mod 2310).例2韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末 行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵 数？解：由题意，有 x 1(mod5)， x 5(mod6) ， x 4(mod7) ， x 10(mod11)x 3 462 385 5 330 4 210 10 6731 2111(mod 2310).5.3 简单高次同余式组 f (x) 0(mod mi), i 1,2,., k 及 f (x) 0(mod p ) , p 为 质数，0的解数及解法的初步讨论定理1若m1, m2,mk是k个两两

21、互质的正整数，m m1m2.mk,则同余式f (x) 0(mod m)与同余式组 f (x) 0(mod mi), i 1,2,., k 等价. 若用T表示f (x) 0(modmj,i 1,2,.,k ,对模mi的解数，T表示 f(x) 0(mod m)对模m的解数，则T TT2.T .呵例 1 解同余式 f (x)0(mod35)， f(x) x4 2x3 8x 9.仅供学习与交流，如有侵权请联系网站删除 谢谢13解：由定理 1 知 f(x) 0(mod35)与同余式 f(x) 0(mod5) , f(x) O(mod 7)等价同余式f (x)0(mod5)有两个解，即x 1,4(mod5

22、)同余式f(x) O(mod 7)有三个解，即x 3,5,6(mod 7)即 f (x) 0(mod35)有六个解，即 x b|(mod 5), x b>(mod 7)由孙子定理有，x 21b1 15b2(mod 35)即得 f(x) 0(mod35)的解为 x 31,26,6,24,19,34(mod35).定理 2 设 x x/modp),即 x 为 pl, t1 0, 1, 2,.是 f (x) 0(mod p)的一解，并 且p不整除f1(x) ,( f 1(x)是f (x)的导函数),则x x, pt1刚好给出f (x) 0(mod p )， p 为质数， 0 的一解 x x p

23、 t , t 0, 1, 2,.,即x x (mod p ), 其中 xX1(mod p).例 2 解同余式 6x3 27x2 17x 200(mod30).解:由定理 1 知 f (x) 0(mod30)与 f(x) 0(mod 2), f (x)0(mod3) , f (x)0(mod5)等价.显然，f(x) 0(mod 2)有两解 x 0,1(mod2)f (x) 0(mod3)有一解 x 2(mod3)f (x) 0(mod5)有三解 x 0,1,2(mod5)同余式f (x)0(mod30)有六个解即 x b (mod 2) , x b2 (mod 3), x b3(mod 5),

24、b 0,1 ； b2 2 ； d 0,1,2 由孙子定理得x 15b1 10b2 6b3(mod30),以d, b?, b?值分别代入，得f (x)0(mod30)全部解为 x 20,2,26,5,11,17(mod30).例 3 解同余式 f(x) 0(mod 27)，f(x) x4 7x 4.解：f (x)0(mod3)有一解 x 1(mod3)，并且 3 不整除 f 1(1),以 x 1 3t1 代入 f (x) 0(mod9)得 f (1) 3ti f (1) 0(mod9)但 f(1) 3(mod9) , f1(1) 2(mod 9)即 3 3t1 2 0(mod 9)即 2t1 1

25、 0(mod 3)因此 t1 1 3t2 而 x 1 3(1 3t2)4 9t2是 f(x) 0(mod9)的一解;以 x 4 9t2 代入 f(x) 0(mod 27)即 f(4) 9上2衬(4) 0(mod 27),18 9t2 20 0(mod 27)即 2t2 20(mod3) , t22 3t3即x 4 9(2 3t3) 22 27t3为所求的解.5.4 简单二次同余式x2 a(mod p ),0, (a, p) 1解的判断二次同余式一般形式为ax2 bx c 0(mod m), a与0对模m不同余，由上 面所学知识，经总结，判断一般二次同余式有解与否问题，一定可以转化为判 断形如x

26、2 a(mod p ),0有解与否问题.先讨论单质数模同余式x2 a(mod p), (a, p) 1有解与否问题若它有解，则a叫做模p的平方剩余，若它无解，则a叫做模p的平方非剩 余.p 1定理1若(a, p) 1,则a是模p的平方剩余的充要条件是a 2 1(mod p)且有两p 1解；而a是模p的平方非剩余充要条件是a_1(mod p).(a)是勒让得符号，它是一个对于给定单质数p定义在一切整数a上的函数，p它的值规定如下：当(旦)1时，a是模p的平方剩余；p精品资料当(旦)1时，a是模p的平方非剩余;P当(a ) =0时,PP.a讨论质数模同余式x2 a(mod p ),0, (a, p

27、) 1有解与否问题定理 2 x2 a(mod p ),0, (a, p) 1有解的充要条件是(旦)1,并且在有解p情况下，解数是2讨论合数模同余式x2 a(mod 2 ),0, (2,a)1有解与否问题仅供学习与交流，如有侵权请联系网站删除谢谢11定理 3 设 1,当 2, a 1(mod4)时，x2 a(mod2 ) ,0,(2, a) 1 有解，且解数是2;当 3，a 1(mod8)时，上式有解，解数是4.何例 解 x2 57(mod 64).解：因571(mod8)故有4个解.把x写成x (1 4ta)代入原同余式，得到(1 4ta)2 57(mod16),由此得t3 1(mod2),故

28、 x 1 4(1 2t4)(5 8t4)是适合 x2 57(mod16)的一切整数，再代入原同余式得到(5 8t4)2 57(mod 32),由此得t4 0(mod 2),故 x (5 8 2t5)(5 16t5)是适合 x2 57(mod 32)的一切整数,再代入原同余式得到(5 16t5)2 57(mod 64),由此得t5 1(mod2),故 x 5 16(1 玄6)(21 32te)是适合 x2 57(mod 64)的一切整数，因此x 21,53, 21, 53(mod 64)是所求四个解.精品资料6结论本文从同余概念及其基本性质出发，通过实例概括总结出同余性质在算术 及数论中的一些简单应用.同余性质在算术中的应用主要是通过检查因数和弃九法验算结果的实例作 出阐述;数论中同余性质的应用主要体现在简单一次同余式组及高次同余式的求