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結論本文從同余概念及其基本性質出發，通過實例概括總結出同余性質在算術 及數論中的一些簡單應用.同余性質在算術中的應用主要是通過檢查因數和棄九法驗算結果的實例作 出闡述;數論中同余性質的應用主要體現在簡單一次同余式組及高次同余式的求