同余的性質(zhì)與應(yīng)用教學(xué)內(nèi)容

1、同余的性質(zhì)與應(yīng)用精品資料同余的性質(zhì)及應(yīng)用1引言數(shù)論的一些基礎(chǔ)內(nèi)容的學(xué)習(xí)，一方面可以加深對(duì)數(shù)的性質(zhì)的了解，更深入的理解 某些其他鄰近學(xué)科，另一方面，可以加強(qiáng)數(shù)學(xué)訓(xùn)練 .而整數(shù)論知識(shí)是學(xué)習(xí)數(shù)論的基 礎(chǔ)，其中同余理論有時(shí)整數(shù)論的重要組成部分，所以學(xué)好同余理論是非常重要的.在日常生活中，我們所要注意的常常不是某些整數(shù)，而是這些數(shù)用某一固定的數(shù) 去除所得的余數(shù)，例如我們問(wèn)現(xiàn)在是幾點(diǎn)鐘，就是用24去除某一個(gè)總的時(shí)數(shù)所得的余數(shù)；問(wèn)現(xiàn)在是星期幾，就是問(wèn)用 7去除某一個(gè)總的天數(shù)所得的余數(shù)，假如某月2號(hào)是星期一，用7去除這月的號(hào)數(shù)，余數(shù)是2的都是星期一.我國(guó)古代孫子算經(jīng)里已經(jīng)提出了同余式 xbdmodmj, xb

2、2(modm2),xbk(modmk)這種形式的問(wèn)題，并且很好地解決了它.宋代大數(shù)學(xué)家秦九韶在他的數(shù)學(xué)九章中提出了同余式x Mi1(modmi), i 1,2,., k , mj是k個(gè)兩兩互質(zhì)的正整數(shù)，m 口口:口).，m mMj的一般解法.同余性質(zhì)在數(shù)論中是基礎(chǔ)，許多領(lǐng)域中一些著名的問(wèn)題及難題都是利用同余理論 及一些深刻的數(shù)學(xué)概念，方法，技巧求解.例如，數(shù)論不定方程中的費(fèi)爾馬問(wèn)題，拉 格朗日定理的證明堆壘數(shù)論中的華林問(wèn)題，解析數(shù)論中，特征函數(shù)基本性質(zhì)的推導(dǎo)等 等.在近現(xiàn)代數(shù)論研究中，有關(guān)質(zhì)數(shù)分布問(wèn)題，如除數(shù)問(wèn)題，圓內(nèi)格點(diǎn)問(wèn)題，等差級(jí) 數(shù)問(wèn)題中的質(zhì)數(shù)分布問(wèn)題，an2 bn c形式的質(zhì)數(shù)個(gè)數(shù)問(wèn)題

3、，質(zhì)數(shù)個(gè)數(shù)問(wèn)題，質(zhì)數(shù)增 大的快慢問(wèn)題，孿生質(zhì)數(shù)問(wèn)題都有一定程度的新成果出現(xiàn)，但仍有許多尚未解決的問(wèn) 題.數(shù)論的發(fā)展以及現(xiàn)代數(shù)學(xué)發(fā)展中提出的一些數(shù)論問(wèn)題，都要求我們對(duì)于近代數(shù)論 的一些方法和基礎(chǔ)知識(shí)，必須熟練掌握.所以，本文主要介紹了同余理論中同余基本 性質(zhì)的一些簡(jiǎn)單應(yīng)用，通過(guò)本文的闡述，希望可以為對(duì)數(shù)論有興趣的讀者，增加學(xué)習(xí) 數(shù)論知識(shí)的興趣，并能為他們攻破那些經(jīng)典的數(shù)論難題開(kāi)展數(shù)論課題課題提供一些幫 助.僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝0精品資料2同余的概念給定一個(gè)正整數(shù)m，把它叫做模，如果用m去除任意兩個(gè)整數(shù)a與b所得的余數(shù) 相同，我們就說(shuō)對(duì)模m同余，記作a b(modm),如果余

4、數(shù)不同，就說(shuō)對(duì)模 m不同余. 由定義得出同余三條性質(zhì)：(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).定義也可描述為：整數(shù)a , b對(duì)模m同余的充分必要條件是 ma b ,即a b mt, t是整 數(shù).3同余的八條基本性質(zhì)由同余的定義和整數(shù)的性質(zhì)得出:(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任一正公因數(shù),則-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個(gè)數(shù)最小公倍數(shù)(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兩數(shù)之一，則d必整除a , b另一個(gè).4同余性質(zhì)在算術(shù)里的應(yīng)用4.1 檢查因數(shù)的一些方法例1 一整數(shù)能被3(9)整除的充要條件是它的十進(jìn)位數(shù)碼的和能被3(9)整除.證：按照通常方法，把任意整數(shù)a寫(xiě)成十進(jìn)位數(shù)形式，即nn 1a an10an 110. a。，0 ai 10.因101(mod3),所以由同余基本性質(zhì)，即3a當(dāng)且僅當(dāng)3;同法可得9 a當(dāng)且僅當(dāng)9ai，i 0,1,., n.例 2 設(shè)正整數(shù) 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對(duì)模7 (或11或13)同余，根據(jù)同余性質(zhì)知，a與 (1)i ai對(duì)模7 (或11或13)同余即7 (或11或13)整除a當(dāng)且僅當(dāng)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 整除，當(dāng)且僅當(dāng)a能被3, 9整除解:由例1證法可知，該結(jié)論正確.僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝1精品資料例

8、 4 a =435693,則 a 4 3 5 6 9 3 30 , i 0,1,., n 能被 3 整除，但ai不能被9整除當(dāng)且僅當(dāng)3是a的因數(shù)，9不是a的因數(shù).解：由例1的證法可得.例 5 a =637693,則 a 637 1000 693， q 693 637 56，i 0,1,., n 能被7整除而不能被11或13整除當(dāng)且僅當(dāng)7是a的因數(shù)但11，13不是a的因數(shù). 解：由例2的證法可知，該結(jié)論正確.例 6 a =75312289, a 75 10002 312 1000 289ai 289 312 75 52，i 0,1,., n能被13整除，而不能被7，11整除當(dāng)且僅當(dāng)13是a的因數(shù)

9、，而7與 11不是a的因數(shù).解：由例2的證法可知.例7應(yīng)用檢查因數(shù)的方法求出下列各數(shù)標(biāo)準(zhǔn)分解式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 棄九法(驗(yàn)證整數(shù)計(jì)算結(jié)果的方法)我們由普通乘法的運(yùn)算方法求出整數(shù) a , b的乘積是P，并令aan10nn 1an 110.a0 ,0ai10bbn10n

11、n 1bn 110.b0 ,0b10 ,PCn10nn 1Cm10.c0 ,0Ci10,如果(aj( bj)與ck對(duì)模9不同余，那么所求得的乘積是錯(cuò)誤的.特別的，在實(shí)際驗(yàn)算中，若ai , bj , 0.中有9出現(xiàn)，貝U可去掉(因9 0(mod9).例1 a =28997, b =39495，按普通計(jì)算方法算得a , b乘積是P =1145236515,按照上述棄九法 a 8(mod9) , b 3(mod9) , P 5(mod9).但8 3與5對(duì)模9不同余，所以計(jì)算有誤例 2 若 a =28997, b =39495, P =1145235615,那么 P a b ?解：按照上述棄九法，a

12、8(mod9) , b 3(mod9) , P 6(mod9).雖然8 3與6對(duì)模9同余，但是由通常乘法計(jì)算得到 a b 1145236515 ,故P a b不成立.注：當(dāng)使用棄九法時(shí)，得出的結(jié)果雖然是(ai)( bj)ck(mod9)也還不能完全肯定原計(jì)算是正確的.4.3 同余性質(zhì)的其他應(yīng)用例1求7除4750的余數(shù).解：由 47 ( 2)12(mod7) , 472 ( 2)2 4(mod 7),5547( 2)1(mod7),4750(475)16 4721 4 4(mod 7),即4750除以7余數(shù)為4.例2試證：形如8k 7(k N)的整數(shù)不能表為三個(gè)平方數(shù)之和.證：假定 N 8k 7

13、 a2 b2 c2(a,b,c Z)，則 a2 b2 c2 7(mod8)，但這不 可能.因?yàn)閷?duì)模8而論.每一個(gè)整數(shù)最小非負(fù)余數(shù)只能是 0，1, 2, 3, 4, 5，6，7中的一個(gè)數(shù).而 020(mod8)，121(mod8)，224(mod8)，321(mod8)，42 0(mod8)，52 1(mod8)，62 4(mod8)，72 1(mod8).因此，任一整數(shù)平方對(duì)模 8必與0，1, 4三個(gè)數(shù)之一同余，而從 0, 1, 4中任取三個(gè)數(shù)，其和都不可能與 7對(duì)模8同余，所以對(duì)于任何整數(shù)a , b , c都有a2 b2 c2與7對(duì)模8不同余.即形如8k 7(k N)的整數(shù)不能表為三個(gè)平方數(shù)

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)也就是說(shuō)，5353 3333能被10整除.例 4 設(shè) a,b,c N 且6 (a b c

15、)，求證：6 (a3 b3 c3)證：對(duì)模6來(lái)說(shuō)每一個(gè)整數(shù)的最小非負(fù)數(shù)余數(shù)為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)，即對(duì)任何整數(shù) 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整除.證：設(shè)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同余性質(zhì)在數(shù)論中的應(yīng)用：求簡(jiǎn)單同余式的解5.1 一次同余式、一次同余式解的概念僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝7精品資料在代數(shù)里面，一個(gè)主要問(wèn)題就是解代數(shù)方程.而同余性質(zhì)在數(shù)論中的應(yīng)用主要體現(xiàn)在同余在方程中的應(yīng)用，也就是求同余式的解.一次同余式的

17、定義：若用f(x)表示多項(xiàng)式anXn an ixn 1 . ao，其中ai 是整數(shù)，又設(shè)m是一個(gè)正整數(shù)，則f (x) 0(mod m)叫做模m的同余式.若an與 0對(duì)m不同余，則n叫做f (x) 0(mod m)的次數(shù).定義：若a是使f(a) 0(mod m)成立的一個(gè)整數(shù)，則x a(mod m)叫做同余式f(x) 0(mod m)的一個(gè)解.定理 一次同余式ax b(modm),a與0對(duì)模m不同余,它有解充要條件是(a,m)b .35.2孫子定理解一次同余式組引例今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？解：設(shè)x是所求物數(shù)，則依題意有，x 2(mod3) , x 3(

18、mod5) , x 2(mod7)孫子算經(jīng)里介紹用下列方法求解除數(shù)余數(shù)最小公倍數(shù)衍數(shù)乘率各總答數(shù)最小答數(shù)325 72352 2140+63+233-533 5 7=1057 31211 330=2332 105=23723 51151 2由表格知，所求物數(shù)是23.孫子定理：設(shè) mj, m2,mk是k個(gè)兩兩互質(zhì)的正整數(shù)， 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、格形式概括如下除數(shù)余數(shù)最小公倍數(shù)衍數(shù)乘率各總答數(shù)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).解：此時(shí) 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韓信點(diǎn)兵：有兵一隊(duì)，若列成五行縱隊(duì)，則末行一人，成六行縱隊(duì)，則末 行五人，成七行縱隊(duì)，則末行四人，成十一行縱隊(duì)，則末行十人，求兵 數(shù)？解：由題意，有 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 簡(jiǎn)單高次同余式組 f (x) 0(mod mi), i 1,2,., k 及 f (x) 0(mod p ) , p 為 質(zhì)數(shù)，0的解數(shù)及解法的初步討論定理1若m1, m2,mk是k個(gè)兩兩

21、互質(zhì)的正整數(shù)，m m1m2.mk,則同余式f (x) 0(mod m)與同余式組 f (x) 0(mod mi), i 1,2,., k 等價(jià). 若用T表示f (x) 0(modmj,i 1,2,.,k ,對(duì)模mi的解數(shù)，T表示 f(x) 0(mod m)對(duì)模m的解數(shù)，則T TT2.T .呵例 1 解同余式 f (x)0(mod35)， f(x) x4 2x3 8x 9.僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除 謝謝13解：由定理 1 知 f(x) 0(mod35)與同余式 f(x) 0(mod5) , f(x) O(mod 7)等價(jià)同余式f (x)0(mod5)有兩個(gè)解，即x 1,4(mod5

22、)同余式f(x) O(mod 7)有三個(gè)解，即x 3,5,6(mod 7)即 f (x) 0(mod35)有六個(gè)解，即 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 設(shè) x x/modp),即 x 為 pl, t1 0, 1, 2,.是 f (x) 0(mod p)的一解，并 且p不整除f1(x) ,( f 1(x)是f (x)的導(dǎo)函數(shù)),則x x, pt1剛好給出f (x) 0(mod p )， p 為質(zhì)數(shù)， 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)等價(jià).顯然，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)有六個(gè)解即 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 簡(jiǎn)單二次同余式x2 a(mod p ),0, (a, p) 1解的判斷二次同余式一般形式為ax2 bx c 0(mod m), a與0對(duì)模m不同余，由上 面所學(xué)知識(shí)，經(jīng)總結(jié)，判斷一般二次同余式有解與否問(wèn)題，一定可以轉(zhuǎn)化為判 斷形如x

26、2 a(mod p ),0有解與否問(wèn)題.先討論單質(zhì)數(shù)模同余式x2 a(mod p), (a, p) 1有解與否問(wèn)題若它有解，則a叫做模p的平方剩余，若它無(wú)解，則a叫做模p的平方非剩 余.p 1定理1若(a, p) 1,則a是模p的平方剩余的充要條件是a 2 1(mod p)且有兩p 1解；而a是模p的平方非剩余充要條件是a_1(mod p).(a)是勒讓得符號(hào)，它是一個(gè)對(duì)于給定單質(zhì)數(shù)p定義在一切整數(shù)a上的函數(shù)，p它的值規(guī)定如下：當(dāng)(旦)1時(shí)，a是模p的平方剩余；p精品資料當(dāng)(旦)1時(shí)，a是模p的平方非剩余;P當(dāng)(a ) =0時(shí),PP.a討論質(zhì)數(shù)模同余式x2 a(mod p ),0, (a, p

27、) 1有解與否問(wèn)題定理 2 x2 a(mod p ),0, (a, p) 1有解的充要條件是(旦)1,并且在有解p情況下，解數(shù)是2討論合數(shù)模同余式x2 a(mod 2 ),0, (2,a)1有解與否問(wèn)題僅供學(xué)習(xí)與交流，如有侵權(quán)請(qǐng)聯(lián)系網(wǎng)站刪除謝謝11定理 3 設(shè) 1,當(dāng) 2, a 1(mod4)時(shí)，x2 a(mod2 ) ,0,(2, a) 1 有解，且解數(shù)是2;當(dāng) 3，a 1(mod8)時(shí)，上式有解，解數(shù)是4.何例 解 x2 57(mod 64).解：因571(mod8)故有4個(gè)解.把x寫(xiě)成x (1 4ta)代入原同余式，得到(1 4ta)2 57(mod16),由此得t3 1(mod2),故

28、 x 1 4(1 2t4)(5 8t4)是適合 x2 57(mod16)的一切整數(shù)，再代入原同余式得到(5 8t4)2 57(mod 32),由此得t4 0(mod 2),故 x (5 8 2t5)(5 16t5)是適合 x2 57(mod 32)的一切整數(shù),再代入原同余式得到(5 16t5)2 57(mod 64),由此得t5 1(mod2),故 x 5 16(1 玄6)(21 32te)是適合 x2 57(mod 64)的一切整數(shù)，因此x 21,53, 21, 53(mod 64)是所求四個(gè)解.精品資料6結(jié)論本文從同余概念及其基本性質(zhì)出發(fā)，通過(guò)實(shí)例概括總結(jié)出同余性質(zhì)在算術(shù) 及數(shù)論中的一些簡(jiǎn)單應(yīng)用.同余性質(zhì)在算術(shù)中的應(yīng)用主要是通過(guò)檢查因數(shù)和棄九法驗(yàn)算結(jié)果的實(shí)例作 出闡述;數(shù)論中同余性質(zhì)的應(yīng)用主要體現(xiàn)在簡(jiǎn)單一次同余式組及高次同余式的求