同余與同余方程.doc

《同余與同余方程.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第2章同余與同余方程在整除的基礎(chǔ)上,我們進(jìn)一步研究同余理論.德國(guó)大數(shù)學(xué)家高斯發(fā)明了同余式語(yǔ)言.這使得我們差不多能像處理等式一樣來(lái)處理整除關(guān)系.在本章中,我們將給出同余的基本性質(zhì),描述如何進(jìn)行同余式的算術(shù)運(yùn)算,還將研究含未知數(shù)的同余方程,例如線性同余方程.引出線性同余方程的一個(gè)例子是這樣的一個(gè)問(wèn)題,求使得7x被11除所得余數(shù)為3的所有整數(shù)x.我們還將研究線性同余方程組,它們來(lái)源于古代中國(guó)難題:求一個(gè)數(shù),它被3,5,7處所得余數(shù)分別為2,3,2.我們將學(xué)習(xí)如何運(yùn)用著名的中國(guó)剩余定理來(lái)解像上一難題那樣的線性同余方程組.2.1同余的概念及其基本性質(zhì)一、同余的概念本章所介紹的同

2、余這一特殊語(yǔ)言在數(shù)論中極為有用,它是由歷史上最著名的數(shù)學(xué)家之一高斯于19世紀(jì)初提出的.同余的語(yǔ)言使得人們能用類(lèi)似處理等式的方式來(lái)處理整除關(guān)系.在引入同余之前,人們研究整除關(guān)系所用的記號(hào)笨拙而且難用.而引入方便的記號(hào)對(duì)加速數(shù)論的發(fā)展起了幫助作用.定義1給定正整數(shù)m,稱(chēng)為模,設(shè)a,b是整數(shù)(1)如果,則稱(chēng)a和b對(duì)模m同余,簡(jiǎn)稱(chēng)同余,記為;(2)如果,則稱(chēng)a和b對(duì)模m不同余,記為.例1下列數(shù)中哪些對(duì)模7同余:421,46,11,6,32,3解:由,得.我們有時(shí)需要將同余式轉(zhuǎn)換為等式.下面的定理能幫助我們做到這一點(diǎn).定理1.證明:若,則,這說(shuō)明存在整數(shù)q,使得qm=a-b,即

3、.反過(guò)來(lái),若存在整數(shù)q,使得,則qm=a-b.于是,,.■小結(jié):二、同余的性質(zhì)定理2設(shè)m是正整數(shù),模m的同余滿(mǎn)足下面的性質(zhì):(i)自反性.若a是整數(shù),則;(ii)對(duì)稱(chēng)性.若a,b是整數(shù),且則;(iii)傳遞性.若a,b,c是整數(shù),且,則.所以同余是整數(shù)間的一種等價(jià)關(guān)系.由定義1知定理2是顯然的.定理3若,則(i)（可加性）;(ii)（可乘性）.定理3很容易證明,另外利用歸納法不難把定理3推廣到n個(gè)同余式的情形,且易推出下述結(jié)論.推論設(shè),k是整數(shù),n是正整數(shù),則(i);(ii).定理4設(shè)是兩個(gè)整系數(shù)多項(xiàng)式,且滿(mǎn)足那么若,則定理4由定理3及其推論即可推出.當(dāng)定理4中條件:

4、同次冪系數(shù)關(guān)于模m同余時(shí),就稱(chēng)多項(xiàng)式f(x)和g(x)對(duì)于模m同余,記為定理5設(shè),k是正整數(shù),則.定理6設(shè),d是正整數(shù),且,則.定理7若,且設(shè),則,特別地,當(dāng)時(shí),有.證明:因?yàn)?所以有,即,由,得.又因?yàn)?故,所以.■這一性質(zhì)說(shuō)明:在模m不變的情況下,同余式兩邊不能隨便約去相同的因數(shù),如,但.定理8若,則.定理8顯然可以推廣到任意k個(gè)同余式的情形.例2求的個(gè)位數(shù).解:由,得.三、整除性檢驗(yàn)利用同余可以導(dǎo)出整數(shù)的一些整除特征.設(shè)N為正整數(shù),則N可表示為,其中①被2的冪整除的檢驗(yàn):;②被5的冪整除的檢驗(yàn):;③被3,9整除的檢驗(yàn):;④被11整除的檢驗(yàn):;⑤被7,11,13整

5、除的檢驗(yàn):.四、棄九驗(yàn)算法在公元9世紀(jì),有個(gè)印度數(shù)學(xué)家名叫花拉子米,寫(xiě)有一本《花拉子米算術(shù)》,他們?cè)谟?jì)算時(shí)通常是在一個(gè)鋪有沙子的土版上進(jìn)行,由于害怕以前的計(jì)算結(jié)果丟失而經(jīng)常檢驗(yàn)加法運(yùn)算是否正確,他們的檢驗(yàn)方式就是采用棄九驗(yàn)算法.實(shí)際上,棄九驗(yàn)算法就是利用同余來(lái)驗(yàn)算正整數(shù)進(jìn)行算術(shù)四則運(yùn)算的計(jì)算結(jié)果.下面以乘法為例.設(shè)a,b都是正整數(shù),且ab=p,不妨記則,,,所以當(dāng)上述同余式不成立時(shí),求得的乘積p就是錯(cuò)誤的結(jié)果.在實(shí)際計(jì)算時(shí),還可以利用同余式進(jìn)行簡(jiǎn)化.例5驗(yàn)算下列算式是否正確.解:因?yàn)?,,而,所以上述算式不正確.注意:棄九驗(yàn)算法只能知道原題一定是錯(cuò)的或有可能正確,但不

6、能保證一定正確.例如:檢驗(yàn)算式時(shí),等式兩邊除以9的余數(shù)都是0,但是顯然算式是錯(cuò)誤的.但是,反過(guò)來(lái),如果一個(gè)算式一定正確,那么它的等式兩端一定滿(mǎn)足棄九驗(yàn)算法的規(guī)律.這個(gè)思想往往可以幫助我們解決一些較復(fù)雜的數(shù)字謎問(wèn)題.另外,可以類(lèi)似地用此法來(lái)檢驗(yàn)加法、減法、乘方等算式的計(jì)算結(jié)果.習(xí)題2.11.計(jì)算m取何值時(shí)，下列各式成立:2.計(jì)算m取何值時(shí)，下列兩式同時(shí)成立:一般地，若同時(shí)成立，則m要滿(mǎn)足什么條件？3.證明對(duì)一切整數(shù)x都有4.證明：.7.用棄九法驗(yàn)算下列算式是否有錯(cuò)：8.在算式中中遺漏了一個(gè)數(shù)字，如果其他數(shù)字都是正確的，求遺漏的數(shù)字。