同余的性质与应用

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

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

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

4、d m); a b(mod m)则 b a(mod m);(3) a b(modm),b c(modm),则 a c(modm).定义也可描述为：整数a,b对模m同余的充分必要条件是m/a b,即a b mt,t是整数.3同余的八条基本性质由同余的定义和整数的性质得出1：(1) 若 a b(modm),c d(modm),则 a c b d(mod m)若 a b c(modm),贝U a c b(mod m)若a b(modm),c d (mod m),贝 U ac bd(modm)特别地，若 a b(mod m),则 ak bk(mod m)(3)若 Ai卜 B i. k(mod m),为

5、 y/modm), i 0,1,.,n则 Ai.卜为二& k Bi. kM 1.诙 k(modm)(4)若 a a1d , b bid , (d, m) 1, a b(mod m) ,WJ a bi (mod m)(5) 若 a b(mod m), k 0,贝U ak bk(mod m);若a b(mod m), d 是a,b及 m 任一正公因数，则旦 (mod m)d d d(6)若 a b(mod mi) ,i 1,2,., k,则 a b(mod m1, m2,., mk)其中m1, m2,., mk是m1,m2,., mk, k个数最小公倍数若a b(mod m), d/m,d

6、 0,贝 Ua b(modd)(8) a b(mod m), (a, m) (b,m)若d能整除m及a , b两数之一，则d必整除a ,b另一 个.4同余性质在算术里的应用4.1检查因数的一些方法例1 一整数能被3(9)整除的充要条件是它的十进位数码的和能被3(9)整除.证:按照通常方法，把任意整数a写成十进位数形式，即 nn 1a an10 an110. a0, 0 ai 10.因10 1(mod3),所以由同余基本性质，即3/a当且仅当3 ai ;同法可得9/a当且仅当9/ ai , i 0,1,.,n.例 2 设正整数 a 烝1000n an 11000 n 1 . a。，0 ai 10

7、00,则 7(或 11 或 13)整除a的充要条件是7(或11或13)整除a2 .) ® a3 .)(1)ia,i 0,1,.,n.证：1000与-1对模7 (或11或13)同余，根据同余性质知，a与 (1)ia对模7 (或11或13)同余即7(或11或13)整除a当且仅当7(或11或13)整除 (1)iai,i 0,1,., n.例 3 a=5874192,贝Uai5 8 7 4 1 9 2 36, i 0,1,.,n 能被 3, 9 整除，当且仅当a能被3, 9整除解：由例1证法可知，该结论正确.例 4 a =435693,则 ai 4 3 5 6 9 3 30 , i 0,1,

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

9、下列各数标准分解式15356251158066一 三654321解： 1535625 1 10 5 10 3 10 5 106 10 2 10 5,2 1 5 3 5 6 2 5 27 , 9/279/1535625, 2 一1535625 1 1000535 1000 625,(a0 a2) a1 625 1 535 91,由例 2 得 13/91, 7/91,7/1535625, 13/1535625,又 5/1535625, 9 5 13 74095,15356254095375,5/375, 37575 , 25/75,Word文档-541535625 3 5 13 7.6, 1158

10、066 1 106 1 105 5 104 8 103 6 101a 1 1 5 8 6 6 27 , 9/27 9/1158066, 2_1158066 1 1000158 1000 66 ,(a。a2) a1 66 1 15891 ,由例 2 得 7,91 , 13917/1158066, 13/1158066,又 2/1158066, 9 7 13 2 1638, 1158066 707, 7/707, 16381158066 2 9 72 13 101 .4.2 弃九法(验证整数计算结果的方法) 我们由普通乘法的运算方法求出整数 a, b的乘积是P,并令nn 1aan10an i10.

11、a0 ,0ai10bbn10nbn 110n 1.bo,0b10,PCn10nCn 110n 1.C0,0ci10 , 如果(ai)( bj)与 金对模9不同余，那么所求得的乘积是错误的 特别的，在实际验算中，若ai , bj , Ck中有9出现，则可去掉(因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

12、 a b?解：按照上述弃九法，a 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的余数.12255解：由 47 ( 2) 2(mod 7) , 47( 2) 4(mod 7) , 47( 2)1(mod7),505 16247(47 5)472 1 4 4(mod 7),即4750除以7余数为4.例2试证：形如8k 7(k N)的

13、整数不能表为三个平方数之和证：假定 N 8k 7 a2 b2 c2(a,b,c Z),则 a2 b2 c2 7(mod8),但这不可 能.因为对模8而论.每一个整数最小非负余数只能是 0, 1, 2, 3, 4, 5, 6, 7中的一个数.而 02 0(mod8) , 12 1(mod8) , 22 4(mod8) , 32 1(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

14、都有a2 b2 c2与7对模8不同余.即形如8k 7(k N)的整数不能表为三个平方数之和.例3试证：5353 3333能被10整除.证：由已知条件有 53 3(mod10) , 532 32 9(mod10) , 535 35 7(mod10),_44534 34 1(mod10),5353 (534)15 53 (34)15 3 1 3 3(mod10)又 33 3(mod10),332 32 9(mod10),335 35 7(mod10),334 34 1(mod10), _33_48_48_3333 (334)8 33 (34)8 3 1 3 3(mod10)5353 3333(mo

15、d10),即 10/(5353 3333)也就是说，5353 3333能被10整除.例 4 设 a, b,c N 且 6/(a b c),求证：6/(a3 b3 c3)证：对模6来说每一个整数的最小非负数余数为0, 1, 2, 3, 4, 503 0(mod 6) , 13 1(mod6) , 23 2(mod 6) , 33 3(mod 6) , 43 4(mod 6),53 5(mod 6),即对任何整数 k , k3 k(mod 6)a3 a(mod6) , b3 b(mod 6) , c3 c(mod 6)333(a b c ) (a b c)(mod 6)又(a b c) 0(mod

16、 6)(a3 b3 c3) 0(mod 6)故 6/(a3 b3 c3)例5若(5, n) 1 ,证明n5 n能被30整除.证：设 n N, n k(mod6)则 k 0,1,2,3,4,5 5 一_5_5_ 5 一一 5一由 05 0(mod 6) , 15 1(mod6) , 25 2(mod 6), 35 3(mod 6) , 45 4(mod 6),_5 一 一一5 5(mod 6),k5 k(mod6)即 n5 k5 k n(mod 6), 6/(n5 n)同理可知5. (n5 n)又(5,6) 130. (n5 n)故n5 n能被30整除.5同余性质在数论中的应用：求简单同余式的解

17、5.1 一次同余式、一次同余式解的概念在代数里面，一个主要问题就是解代数方程.而同余性质在数论中的应用主要体现在同余在方程中的应用，也就是求同余式的解.一次同余式的定义：若用f(x)表示多项式anXn an 1Xn 1 . a0,其中ai是整数，又设m是一个正整数，则f(x) 0(mod m)叫做模m的同余式.若an与0对m不同余，则n叫做f(x) 0(modm)的次数.定义：若a是使f(a) 0(mod m)成立的一个整数，则x a(mod m)叫做同余式f(x) 0(mod m)的一个解.定理 一次同余式ax b(modm),a与0对*m m不同余，它有解充要条件是(a,m)/b.35.2

18、 孙子定理解一次同余式组引例今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？解:设x是所求物数，则依题意有，x 2(mod3) ,x 3(mod5) ,x 2(mod7)孙子算经里介绍用下列方法求解除数余数最小公倍数衍数乘率各总答数最小答数323 5 7=1055 7235 2 2140+63233-2 105=23537 3121 1 3+30=23723 5115 1 23由表格知，所求物数是23.孙子定理：设m1 ,m2，是k个两两互质的正整数，m m1m2.mk, m miM i ,i 1,2,., k ,则同余式组 x ”(mod.), x b2(mod m2),

19、.,x bk(modmk)的解是 x M11M 1bl M 12M 2b2 M 1kM kbk(mod m),其 中 M 1iMi 1(mod mi) , i 1,2,., k用表格形式概括如下除数余数最小公倍数衍数乘率各总答数m1b1Mm1m2.mkMiM111, M 1M 1b1k 1 ,，,、xM iMibi(mod m)i 1m2b2M2M12 1 M 2 M 2 b2mkbkMkM1k1,M kMkbk例 1 解同余式组 x b1(mod 5), x b2(mod 6) , x b3(mod 7) , x b4(mod11).解：止匕时 m 5 6 7 11 2310,M1 6 7

20、11 462 ,M 2 5 7 11 385,M3 5 6 11 330, M4 5 6 7 210. 11111解 M iMi 1(modmi), i 1,2,3,4 得 M 1 3, M 2 1, M 3 1, M 4 1即 x 1386bl 385b2 330b3 210b4(mod 2310).例2韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末 行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人，求兵数？解:由题意，有 x 1(mod5) , x 5(mod6) , x 4(mod7) , x 10(mod11)x 3 462 385 5 330 4 210 1

21、0 6731 2111(mod 2310).5.3 简单高次同余式组 f (x) 0(modmi), i 1,2,.,k 及 f(x) 0(mod p )印为质数， 0的解数及解法的初步讨论定理1若m1,m2，mk是k个两两互质的正整数，m m1m2.mk，则同余式f(x) 0(mod m)与同余式组 f (x) 0(modmi),i 1,2,., k 等价.若用T表示f (x) 0(modmi),i 1,2,., k ,对模mi的解数,T表示f(x) 0(mod m)对模 m 的解数，则 T TT2.T . 5例 1 解同余式 f(x) 0(mod35) , f(x) x4 2x3 8x 9

22、.解：由定理 1 知 f (x) 0(mod35)与同余式 f (x) 0(mod5) , f (x) 0(mod 7)等价.同余式f (x) 0(mod5)有两个解，即x 1,4(mod5)同余式f (x) 0(mod7)有三个解,即x 3,5,6(mod 7)即 f (x) 0(mod35)有六个解，即 x b1(mod 5) ,x b2(mod 7)由孙子定理有，x 21b1 15b2(mod 35)即得 f(x) 0(mod35)的解为 x 31,26,6,24,19,34(mod35).定理 2 设x x(mod p)Wx Xi pt1，t1 0, 1, 2,.是 f(x) 0(mo

23、d p)的一解，并且p不整除f1(x),( f 1(x)是f (x)的导函数)，则x Xi pti刚好给出f(x) 0(mod p ) , p 为质数，0 的一解 x x p t ,t 0, 1,2，即x x (mod p ),其中 xxi(mod p).6例 2 解同余式 6x3 27x2 17x 20 0(mod30).解：由定理 1 知 f (x) 0(mod30)与 f (x) 0(mod 2), f (x) 0(mod3) , f(x) 0(mod5) 价.显然，f(x) 0(mod2)有两解 x 0,1(mod2)f (x) 0(mod3)有一解 x 2(mod3)f (x) 0(

24、mod5)有三解 x 0,1,2(mod5)同余式f(x) 0(mod30)有六个解即 x bi (mod 2) ,x b2 (mod 3) ,x b3(mod 5), bi 0,1 ; b2 2 ; b3 0,1,2由孙子定理得x 15b1 10b2 6b3(mod30)，以bih值分别代入，得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 不整除 f1(1),以 x 1 3tl 代入 f(x) 0(mod9)

25、得 f(1) 351(1) 0(mod9)但 f(1) 3(mod9) , f1(1) 2(mod 9)即 3 3t1 2 0(mod 9)即 2t1 1 0(mod 3)因此 t1 1 3t2 而 x 1 3(1 3t2) 4 9t2是 f(x) 0(mod9)的一解；1以 x 4 9t2 代入 f(x) 0(mod 27)即 f(4) 9t2 f (4) 0(mod 27),18 9t2 20 0(mod27)即 2t2 2 0(mod3) , t2 2 3t3即x 4 9(2 3t3) 22 27t3为所求的解.5.4 简单二次同余式x2 a(mod p ),0,(a, p) 1解的判断

26、二次同余式一般形式为ax2 bx c 0(mod m) ,a与0对模m不同余，由上面 所学知识，经总结，判断一般二次同余式有解与否问题，一定可以转化为判断形如x2 a(mod p ),0有解与否问题.先讨论单质数模同余式x2 a(mod p), (a, p) 1有解与否问题若它有解，则a叫做模p的平方剩余，若它无解，则a叫做模p的平方非剩 余.p i定理1若(a,p) 1,则a是模p的平方剩余的充要条件是a 2 1(modp)且有两 p i解；而a是模p的平方非剩余充要条件是a 2 1(mod p) .7(a)是勒让得符号，它是一个对于给定单质数p定义在一切整数a上的函数，它p的值规定如下：当

27、()1时，a是模p的平方剩余； p当(亘)1时，a是模p的平方非剩余； p当(亘)=0时，p/a网 p讨论质数模同余式x2 a(mod p ),0,(a, p) 1有解与否问题定理2 x2 a(mod p ) ,0,(a, p) 1有解的充要条件是(旦)1,并且在有解情p况下，解数是2.9讨论合数模同余式x2 a(mod 2 ),0, (2, a) 1有解与否问题定理 3 设 1,当 2,a 1(mod4)时，x2 a(mod 2 ),0,(2, a) 1 有解，且解数是2;当 3, a 1(mod8)时，上式有解，解数是4.10例 解 x2 57(mod 64).解：因57 1(mod8)故

28、有4个解.把x写成x (1 4t3)代入原同余式，得到(1 4t3)2 57(mod16),由此得t3 1(mod2),故 x 1 4(1 2t4)(5 8t4)是适合 x2 57(mod16)的一切整数,再代入原同余式得到(5 %)2 57(mod32),由此得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 2t6)(21 32t6)是适合 x2 57(mod 64)的一切整数，因此x 21,53, 21, 53(mod64)是所求四个解.6结论本文从同余概念及其基本性质出发，通