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結論本文從同余概念及其基本性質出發，通