1、初中數學興趣班系列講座數論部分 唐一良數學工作室第8講 剩余系及其一次同余方程一、基礎知識：（1）剩余系對于任意正整數n而言，一個整數除以m所得的余數只能是0,1,2, ,n-1中的某一個。依次可將整數分成n個類（例如n2時，就是奇數或偶數），從每一類中各取一個數所組成的集合就稱為模的一個完全剩余系，簡稱為模的完系。定義1：如果一個剩余系中包含了這個正整數所有可能的余數（一般地，對于任意正整數n，有n個余數：0,1,2,.,n-1），那么就被稱為是模n的一個完全剩余系。定義2：剩余系：設模為m,則根據余數可將所有的整數分成m類，分別記成0,1,2,m-1，這m個數0,1,2,m-1稱為一個完全

2、剩余系，每個數稱為相應類的代表元。例如：當m=10則,0,1,2,3,4,5,6,7,8,9 最小非負完全-5,-4,-3,-2,-1,0,1,2,3,4 絕對值最小-4,-3,-2,-1,0,1,2,3,4,5 絕對值最小（一）根據剩余類的概念，很容易得到以下幾條有關剩余類的性質：每一個整數一定包含在而且僅包含在模m的一個剩余類中整數p所屬的模m的剩余類中的每一個數都可以寫成km+p的形式，這里k是整數用符號p mod m表示p所屬的模m的剩余類，這條性質寫成數學表達式就是p mod m= p+km（k是整數）整數p、q在模m的同一個剩余類中的充要條件是p、q對

3、模m同余。這條性質用數學符號就可表示為：p mod m= q mod mpq（mod m）實際上，同余式就是剩余類等式的一個特殊情況，是集合中的一個元素，前面有關同余的一些性質對剩余類仍然成立。這條性質表明，對于模m的兩個剩余類要么相等，要么它們的交集為空集，因此，模m有且僅有m個剩余類，它們是：0modm，1 mod m，2 mod m，（m1）mod m。在解決一些有關模m余數的問題時，我們就可以查看m個數：0，1，2，m1，從而得相應的剩余類的情況，使問題變得異常簡單，具體例子，請看后面的例題。在任意取定的m+1個整數中，必有兩個整數對模m同余。（二）根據同余式的性質，我們很容易得到剩余

4、系的其它一些性質：m個整數x1，x2，xm是模m的一組完全剩余系的充要條件是x1，x2，xm中的任意兩個數對模m都不同余。如果x1，x2，xm是模m的一組完全剩余系，那么對任意的整數c，x1+c，x2+c，xm+c也是模m的一組完全剩余系。設k1，k2，km是m個整數，如果x1，x2，xm是模m的一組完全剩余系，那么x1+k1m，x2+k2m，xm+k1m也是模m的一組完全剩余系。（2）一次同余方程設m | a，則axb（mod m）叫做模m的一次同余方程。如果x= x0是方程ax b（mod m）的一個解，那么x= km+x0也是這個方程的一個解。這是因為，如果ax0 b（mod m），那么

5、一定有akm+ax0b（mod m），即a(km+x0) b（mod m），這說明如果x=x0是方程axb（mod m）的一個解，那么剩余類x0mod m中的任何一個數也是這個方程的解，這些解都看作是相同的，把剩余類x0mod m稱為同余方程axb（mod m）的一個解，記作xx0（mod m）因此，我們在解同余方程的時候，只需在任意取定的模m的一組完全剩余系中求解模m的同余方程，就可獲得這個方程的全部解。二、典型例題：例1求證：一定存在整數n，使4n2+27n12能被5整除，并求出這些數。分析：可以選模5的一個完全剩余系逐個驗算，只要數a使4a2+27a12能被15整除，那么剩余類a mod

6、 5中的任何一個整數也滿足條件。解：取模5的一個完全剩余系0，1，2，3，4直接計算可知，3和4滿足條件，所以使4n2+2712能被5整除的所有的整數是n3（mod 5）和n4（mod 5）。例2 求使2n-1為7的倍數的所有正整數n解 因為2381(mod 7)，所以對n按模3進行分類討論(1) 若n=3k，則2n-1(23)k-18k-11k-10(mod 7)；(2) 若n=3k1，則2n-1=2·(23)k-1=2·8k-12·1k-11(mod 7)；(3) 若n=3k2，則2n-1=22·(23)k-1=4·8k-14·1

7、k-13(mod 7)所以，當且僅當3n時，2n-1為7的倍數例3m、p、n為自然數，求證：3 | np（n2m+2）分析：對n按模3進行分類討論證明：當n0（mod 3）時，np0（mod 3），np（n2m+2）0（mod 3）當n1（mod 3）時，np1（mod 3），n2m12m1（mod 3），np（n2m+2）1·（1+2）30（mod 3）當n2（mod 3）時，np2 p（mod 3），n2m（n2）m4m1m1（mod 3）np（n2m+2）2 p（1+2）2 p·00（mod 3）所以，對一切自然數n，都有3 | n p（n2m+2）例4.分別求滿足下

8、列條件的最小自然數：（1）用3除余1，用5除余1，用7除余1。（2）用3除余2，用5除余1，用7除余1。（3）用3除余1，用5除余2，用7除余2。（4）用3除余2，用7除余4，用11除余1。思路分析：（1）該數減去1以后，是3，5和7的最小公倍數105，所以該數的是105+1=106（2）該數減去1以后是5和7的公倍數。因此我們可以以5和7的公倍數中去尋找答案。下面列舉一些同時被5除余1，被7除余1的數，即1，36，71，106，141，176，211，246，從以上數中尋找最小的被3除余2的數。360（mod3），712（mod3），符合條件的最小的數是71。（3）我們首先列舉出被5除余2，

9、被7除余2的數，2，37，72，107，142，177，212，247，從以上數中尋找最小的被3除余1的數。2（mod3），37（mod3）、因此符合條件的最小的數是37。（4）我們從被11除余1的數中尋找答案。1，12，23，34，45，56，67，78，89，100，133，144，155，166，177，188，199，210，232，243，1（mod3）； 1（mod7）， 不符合120（mod3）， 125（mod7） 不符合232（mod3）， 232（mod7） 不符合341（mod3）， 346（mod7） 不符合450（mod3）， 453（mod7） 不符合562（mod

10、3）， 560（mod7） 不符合671（mod3）， 674（mod7） 不符合780（mod3）， 781（mod7） 不符合 892（mod3）， 895（mod7） 不符合1001（mod3）， 1002（mod7） 不符合1222（mod3）， 1223（mod7） 不符合1331（mod3）， 1330（mod7） 不符合 1441（mod3）， 1444（mod7） 不符合1552（mod3），1551（mod7） 不符合1661（mod3），1665（mod7） 不符合1770（mod3），1772（mod7） 不符合1882（mod3），1886（mod7） 不符合1991（

11、mod3），1993（mod7） 不符合2100（mod3），2100（mod7） 不符合2212（mod3），2214（mod7） 符合因此符合條件的數是221。例5.現有70個數排成一行，除了兩頭的兩個數以外，每個數的三倍恰好等于它兩邊兩個數的和，這一行最左邊的幾個數是這樣的：0，1，3，8，21，問這一行數最右邊的一個數被6除的余數是幾？分析：如果將這70個數一一列出，得到第70個數后，再用它去除以6得余數，總是可以的，但計算量太大。即然這70個數中：中間的一個數的3倍是它兩邊的數的和，那么它們被6除以后的余數是否有類似的規律呢？0，1，3，8，21，55，144，被6除的余數依次是0，

12、1，3，2，3，1，0，結果余數有類似的規律，繼續觀察，可以得到：0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，可以看出余數前12個數一段，將重復出現。70÷2=510，第六段的第十個數為4，這便是原來數中第70個數被6除的余數。例6解下列同余方程3x2（mod 6） 4x6（mod 10）解：當x0（mod 6）時，3x0（mod 6）當x1（mod 6）時，3x3（mod 6）當x2（mod 6）時，3x60（mod 6）當x3（mod 6）時，3x93（mod 6）當x4（mod 6）時，3x120（mod 6）當x5（mod 6）時，3x153（mod

13、6）所以方程3x2（mod 6）無解。與小題類似，取模10的最小完全剩余系0，1，2，3，9直接計算可知，x=4和x=9是方程的解，所以這個同余方程的解為x4（mod 10）或x9（mod 10）說明：解模m的一次同余方程，可以取模m的一個完全剩余系直接計算，這個方法也適用于其它的同余方程。模m的一次同余方程axb（mod m）（m a）有解的充要條件是（a，m）| b。例7. 同余方程2x6（mod 8）的解和方程x3（mod 4）的解是否相同，說明理由。解：設x=x0是方程2x6（mod 8）的一個解，那么2x06（mod 8）2x0=8 k+6，x0= 4k+3，x03（mod

14、 4）即方程2x6（mod 8）的解必是方程x3（mod 4）的解反之，若x=x0是方程x3（mod 4）的一個解，那么x03（mod 4）x0= 4m+3，2x0=8m+6，故2x06（mod 8）即方程x3（mod 4）的解必是方程2x6（mod 8）的解所以，方程2x6（mod 8）和x3（mod 4）的解相同說明：若正整數d | （a，b，m），則方程axb（mod m）的解與方程的解相同，利用這條性質可以將較大模數的同余方程化為較小模數的同余方程。例8解同余方程38x19（mod 95）分析：此題中的模95的剩余數太多，如果選定一個完全剩余系進行直接計算，運算量相當大，因此我們可以運

15、用上題的方法，將模化小一點。解：（38，19，95）=19，38x19（mod 95）的解與2x1（mod 5）的解完全相同，只需求解方程2x1（mod 5）即可。2x1（mod 5），2x4（mod 5）x2（mod 5），原方程的解為x2+5u（u=0，1，2，3，18）（mod 95）例9 證明：在十進制表示下，任意39個連續正整數中，必有一個數的各位數字之和是11的倍數。例10.設n位為正奇數，證明：數2-1，22-1，23-1，2n-1-1中必有一個數是n的倍數。例11.一次圓桌會議共有2012個人參加，中場休息后，他們依不同的次序重新圍著圓桌坐下，證明：至少有兩個人，他們之間的人數

16、在休息前后是相等的。三、模擬訓練1 證明方程x4+y4+2=5z沒有整數解證 對于任一整數x，以5為模，有x0，±1，±2(mod 5)，x20，1，4(mod 5)，x40，1，1(mod 5)，即對任一整數x，x40，1(mod 5)同樣，對于任一整數yy40，1(mod 5)，所以 x4+y4+22，3，4(mod 5)，從而所給方程無整數解說明 同余是處理不定方程的基本方法，但這種方法也非常靈活，關鍵在于確定所取的模(本例我們取模5)，這往往應根據問題的特點來確定 2解同余方程987x610（mod 1597）解：987x610（mod 1597），987x1597

17、x610（mod 1597）610x610（mod 1597），x1（mod 1597）3請看一首歡慶國慶的詩：“十里長街鬧盈盈，慶祝成就萬象新，國慶禮花破長空，新橋紅燈勝繁星，七七數時余兩個，五個一數恰為零，九數之時剩四盞，紅燈幾盞放光明。”解：設有x盞紅燈，那么由得x=7m+2，m=0，1，2，3，代入得，7m+20（mod 5），7m22+5×628（mod 5）m4（mod 5），m5n+4，x=7（5n+4）+2=35n+30代入得，35n+304（mod 9），35n2626+4×910（mod 9）7n2（mod 9），7n2+6×956（mod 9

18、），n8（mod 9）n=9k+8，k=0，1，2，3，所以x=35（9k+8）+30=315k+310，xmin=310，答：有310盞紅燈。【延伸閱讀】我國南北朝時期有一部著名的算術著作孫子算經，其中有這樣一個“物不知數”問題：“今有物不知其數，三三數之剩2；五五數之剩3；七七數之剩2，問物幾何？”用現在化較通俗的數學語言可以這樣敘述：“求一個數，使它被3除余2；被5除余3；被7除余2。”解：設所求數為x，則由得x=3k+2，k=0，1，2，3代入得，3k+23（mod 5）3k11+56（mod 5），k2（mod 5），即k= 5n+2，n=0，1，2，x=3（5n+2）+2=15n+

19、8，n=0，1，2，3，代入得：15n+82（mod 7），15n66+2115（mod 7）n1（mod 7），故n=7t+1，t=0，1，2，所以，x=15（7t+1）+8=105t+23，t=0，1，2，3，所求數的最小值是23。孫子算經巧妙地解決了“物不知數”問題，但沒有上升到一套完整的計算程序和理論高度，沒有解決一般的一次同余方程的求解問題，南宋時期的數學家秦九韶在他的數學九章中提出了“大衍求一術”的數學方法，系統地論述了一次同余方程組解法的基本原理和一般程序。“求一”就是求一個數的多少倍除以另一個數，所得的余數是一，為了深刻地理解這一方法，我們再回頭研究“物不知數”問題中的幾個關鍵

20、數字71，21、15。70=2×5×71（mod 3）21=3×71（mod 5）15=3×51（mod 7）其中，70是5和7的倍數，但被3除余1，21是3和7的倍數，但被5除1；15是3和5的倍數，但被7除余1，任何一個一次同余方程組，只要類似地求出相應的關鍵數字，就可以得到這個一次同余方程組的解，秦九韶的“大衍求一術”的方法流傳到西方，被稱為“中國剩余定理”。所以，我得到一般一次同余方程組的解法是：設p，q，r是兩面互質的正整數，同余方程組的解是xAa+Bb+Cc（mod pqr）其中 A1（mod p），A0（mod q），A0（mod r）B1

21、（mod q），B0（mod p），B0（mod r）C1（mod r），C0（mod p），C0（modq）下面我們介紹中國剩余定理：【中國剩余定理】設m1，m2，m k是k個兩兩互質的正整數，對任意整數a1，a2，a k，則同余方程組。有且只有一個解x M1Ma1+M2Ma2+M kMa k（mod m）其中m=m1m2m k，m = mjMj（1jk）以及M jM1（mod mj）1jk這個定理本身比較復雜，證明也比較繁，關于證明過程，這里不作介紹，有興趣的同學請自行閱讀有關初等數論的著作，只對定理本身作一些闡述，以幫助大家理解，我們用中國剩余定理再解“物不知數”問題。M1=5×

22、;7=35，M2=3×7=21，M3=3×5=15，35×2=701（mod 3）211（mod 5），151（mod 7）M1M=70，M2M=21，M3M=15x70×2+21×3+15×2（mod 105）23323（mod 105）所以x的最小值是23。下面舉例說明中國剩余定理的運用。例1解同余方程組解：m1=5，m2=7，m3=11M1=7×11=77，M2=5×11=55，M3=5×7=35M17×112×12（mod 5），由1M1M2M1（mod 5）得，可取M=3M25×115×42061（mod 7），由1M1MM（mod 7）得，可取M=6M3352（mod 11），由1M3M2M（mod 11）得，可取M=6由中國剩余定理可知，原同余方程組的解為x77×3×1+55×6×（1）+35×6×（2）×7×11）519（mod 385）251（mod 385）例2解同余方程組