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

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

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

4、數關于模m同余時,就稱多項式f(x)和g(x)對于模m同余,記為定理5 設,k是正整數,則.定理6設,d是正整數,且,則.定理7若,且設,則,特別地,當時,有.證明:因為,所以有,即,由,得.又因為,故,所以. 這一性質說明:在模m不變的情況下,同余式兩邊不能隨便約去相同的因數,如,但.定理8 若,則. 定理8顯然可以推廣到任意k個同余式的情形.例2 求的個位數.解:由,得.三、整除性檢驗利用同余可以導出整數的一些整除特征.設N為正整數,則N可表示為,其中 被2的冪整除的檢驗:; 被5的冪整除的檢驗:; 被3,9整除的檢驗:; 被11整除的檢驗:; 被7,11,13整除的檢驗:.四、 棄九驗算

5、法在公元9世紀,有個印度數學家名叫花拉子米,寫有一本花拉子米算術,他們在計算時通常是在一個鋪有沙子的土版上進行,由于害怕以前的計算結果丟失而經常檢驗加法運算是否正確,他們的檢驗方式就是采用棄九驗算法.實際上,棄九驗算法就是利用同余來驗算正整數進行算術四則運算的計算結果.下面以乘法為例. 設a,b都是正整數,且ab=p, 不妨記則,所以 當上述同余式不成立時,求得的乘積p就是錯誤的結果.在實際計算時,還可以利用同余式進行簡化. 例5 驗算下列算式是否正確 . 解:因為 , , ,而,所以上述算式不正確. 注意:棄九驗算法只能知道原題一定是錯的或有可能正確,但不能保證一定正確. 例如:檢驗算式 時,等式兩邊除以9的余數都是0,但是顯然算式是錯誤的.但是,反過來,如果一個算式一定正確,那么它的等式兩端一定滿足棄九驗算法的規律.這個思想往往可以幫助我們解決一些較復雜的數字謎問題. 另外,可以類似地用此法來檢驗加法、減法、乘方等算式的計算結果.習題2.11.計算m取何值時，下列各式成立:2.計算m取何值時，下列兩式同時成立:一般