同余理論及其應(yīng)用

1、智浪教育普惠英才文庫 PAGE 9同余理論及其應(yīng)用基礎(chǔ)知識(shí)一. 定義定義1. 設(shè)m為正整數(shù)，整數(shù)a和b之差可被m整除時(shí)，稱為a和b關(guān)于模m 同余，記作 定義2. 被正整數(shù)m除余數(shù)相等的所有整數(shù)的集合稱為模m的剩余類。模m的剩余類共有m個(gè)。定義3. 在模m的m個(gè)剩余類中各取一個(gè)整數(shù)作為代表，這些代表的集合稱為模m的完全剩余系。定義4. 絕對(duì)值不超過的模m的完全剩余系稱為模m的絕對(duì)最小剩余系。定義5. 當(dāng)模m的某一剩余類的所有整數(shù)均與m互素時(shí)，則稱此剩余類是模m的簡(jiǎn)化類。模m的簡(jiǎn)化類共有個(gè)。定義6. 在模m的個(gè)簡(jiǎn)化類中各取一個(gè)整數(shù)作為代表，這些代表的集合稱為模m的簡(jiǎn)化剩余系。定義7. 歐拉函數(shù)：設(shè)

2、為正整數(shù)，從1到的整數(shù)中與互素的整數(shù)的個(gè)數(shù)用表示，稱為歐拉函數(shù)。當(dāng)時(shí)，有二. 定理定理1. 的必要充分條件是a和b被m除的余數(shù)相等。定理2. = 1 * ROMAN I. = 2 * ROMAN II.若則 = 3 * ROMAN III.若則定理3. 若，則 = 1 * ROMAN I.； = 2 * ROMAN II.； = 3 * ROMAN III.定理4. 如果，則 = 1 * ROMAN I.； = 2 * ROMAN II.推論. 如果n為任意正整數(shù)，則定理5. 如果則推論. 如果，則定理6. 如果則定理7. a和b屬于模m的同一剩余類的充要條件是定理8. m個(gè)整數(shù)是模m的完全剩

3、余系的充要條件是關(guān)于模m兩兩互不同余。定理9. 設(shè)f是正整數(shù)m的正因數(shù)。在模f的屬于c的剩余類中取整數(shù)，則它們是模m的個(gè)剩余類。定理10. 與m互素的個(gè)整數(shù)是模m的簡(jiǎn)化剩余系的充要條件是這個(gè)整數(shù)關(guān)于模m兩兩互不同余。又設(shè)是模m的簡(jiǎn)化剩余系，如果，則也是模m的簡(jiǎn)化剩余系。定理11. 歐拉定理：如果，則定理12. 費(fèi)馬小定理：如果，則，其中為素?cái)?shù)。它也常寫作：，這里不要求互素。定理13. 裴蜀定理：設(shè)是整數(shù)，則的充要條件是，存在整數(shù)使得推論1. 的充要條件是，存在整數(shù)使得推論2. 均為正整數(shù)，的充要條件是，存在正整數(shù)使得典型例題：一. 同余與完全平方數(shù)例1. 設(shè)素?cái)?shù)p滿足，證明p必不能表作三個(gè)平方

4、數(shù)之和。分析 我們利用平方數(shù)模8的性質(zhì)進(jìn)行處理。 證明：設(shè)存在三個(gè)整數(shù)使其中或?yàn)榕紨?shù)，或?yàn)槠鏀?shù)。因此下式必居其一。事實(shí)上，當(dāng)a是奇數(shù)或時(shí)，有當(dāng)a是偶數(shù)或時(shí)，有或同樣b和c也必居下式之一：將所有可能滿足的式子任意組合，只能得到而得不到因此形如的素?cái)?shù)不能表作三個(gè)平方數(shù)之和。評(píng)注 選擇合適的模是處理平方數(shù)問題的技巧之一。例2. （2003年越南數(shù)學(xué)奧林匹克）求最大的正整數(shù)n，使得方程組有整數(shù)解分析 我們利用平方數(shù)的性質(zhì)處理問題。解：當(dāng)時(shí)，易知所給的方程組有整數(shù)解，當(dāng)時(shí)，則奇偶交替出現(xiàn)，則且若為奇數(shù)，則 矛盾。同理：若為偶數(shù)，則為奇數(shù)。后面式子又矛盾，所以無解。顯然無解。評(píng)注 選擇適當(dāng)?shù)哪?，利用平方?shù)

5、性質(zhì)是解決平方問題的技巧之一。二. 費(fèi)馬小定理與歐拉定理例3. 證明分析 由原式聯(lián)想到費(fèi)馬小定理。 證明：，由費(fèi)馬小定理, ,而并且，由此可知：，所以原命題成立。評(píng)注 費(fèi)馬小定理是處理此類整除問題的重要工具。例4. （2004年加拿大）為奇素?cái)?shù)，證明： 解：由于為偶數(shù)，則，由二項(xiàng)式定理：右側(cè)除最后兩項(xiàng)外均被整除。因此由于由費(fèi)馬小定理 ， ，則 所以所以，原結(jié)論成立。評(píng)注 二項(xiàng)式定理也是處理數(shù)論問題的重要工具。 三. 同余與不定方程例5. （2004年韓國(guó)數(shù)學(xué)競(jìng)賽）證明：方程沒有正整數(shù)解。分析 我們選擇適當(dāng)?shù)哪?duì)進(jìn)行分類處理問題。證明：（1）當(dāng)時(shí)， 而方程左邊能被3整除，此時(shí)無解。（2）當(dāng)時(shí)，而

6、，均為完全平方數(shù)。而 所以此時(shí)無解。（3）當(dāng)時(shí)，令 則，令，則與（2）類似，均為完全平方數(shù)。設(shè) 則，即，所以 方程無整數(shù)解。綜上所述，原方程無整數(shù)解。評(píng)注 方程右邊可以進(jìn)行因式分解，而左邊系數(shù)為3，因而選擇模3對(duì)進(jìn)行分類處理問題。例6. （2004年巴爾干數(shù)學(xué)奧林匹克）是質(zhì)數(shù)，解：分析 我們要充分利用是質(zhì)數(shù)的條件。 解：若,則無整數(shù)解；若，則 由于是質(zhì)數(shù)，由費(fèi)馬小定理，即， = 1 * GB3 ，再由費(fèi)馬小定理 即1. 若則 = 2 * GB3 ；2. 由 = 1 * GB3 知：； 由 = 2 * GB3 知：即，又為質(zhì)數(shù)。而為奇質(zhì)數(shù)，為偶數(shù)， 與為質(zhì)數(shù)矛盾。所以此時(shí)無解；3. 若，由知 ，

7、無解；4. 若，則當(dāng)時(shí)：易知：時(shí)，無解，當(dāng)時(shí)，兩邊模4，知無解；時(shí)，左邊小于0，無解；當(dāng)時(shí)：兩邊模4， 時(shí)，左邊小于0。當(dāng)時(shí)：同理 無解；時(shí)，左邊小于0。當(dāng)時(shí)：無解；時(shí)，滿足條件。為一組解。當(dāng)時(shí)，無解；時(shí)，無整數(shù)解；當(dāng)時(shí)， ，為一組解。綜上，；為解。評(píng)注 在處理有關(guān)質(zhì)數(shù)的冪的問題中，費(fèi)馬小定理常發(fā)揮重要作用。四. 同余定理例7. 設(shè)p是奇素?cái)?shù)，a是連續(xù)數(shù)列 = 1 * GB3 中的任一數(shù)，則數(shù)列 = 2 * GB3 中必有一個(gè)且只有一個(gè)數(shù)關(guān)于模p與1同余，設(shè)此數(shù)為ia，則i為 = 1 * GB3 中一數(shù)且與a相異。分析 利用為素?cái)?shù)證明：因?yàn)?= 1 * GB3 中各數(shù)均小于p，p為素?cái)?shù)，所以

8、= 1 * GB3 中每一個(gè)數(shù)均與p互素。由于a是 = 1 * GB3 中某數(shù)，故因此，由定理11，數(shù)列與數(shù)列 = 1 * GB3 代表同一類數(shù)，也就是說，數(shù)列 = 2 * GB3 表示模p的除p的倍數(shù)外，其余的一切類數(shù)。因此 = 2 * GB3 中必有一數(shù)，使 。這個(gè)i決不能等于a，事實(shí)上，如果，則有，從而就有。由于p是素?cái)?shù)，且，故或，兩者必居其一。但，即。所以不可能有及。故另外可以證明否則如果就有但，即，所以,因此不可能有所以再次可以證明否則就有，但這與矛盾。這樣就證明了數(shù)列 = 2 * GB3 中必有一數(shù)ia，有，而又，故i必為 = 1 * GB3 中一數(shù)且與a相異。此外，如果 = 1

9、* GB3 中有兩數(shù)使，那么由于，故有，但，從而有，這與假設(shè)矛盾。評(píng)注 本題是最基本的結(jié)論之一。例8. 求證： 這里p為奇素?cái)?shù)。分析 我們利用例1的結(jié)論。 證明：對(duì)任意，都存在唯一的使注意到時(shí)，否則若，即 矛盾。又注意到故可以把中和兩兩配對(duì)，每一對(duì)的乘積同余于1模p，由于有且僅有兩解，所以除了1，和自己配對(duì)外，其余個(gè)數(shù)恰可配成對(duì)。 評(píng)注 本題即威爾遜定理。 五. 同余與其他例9. 已知證明：對(duì)一切正整數(shù)n, 分析 我們只要證明模某一常數(shù)不為0即可。 證明：若某一個(gè)，則對(duì)任意正整數(shù)m有，因此，我們只要找到一個(gè)m，對(duì)任何一個(gè)n 均有即可， 。設(shè)時(shí)，則時(shí)， ，因此對(duì)一切n 均有，從而原命題成立。評(píng)注

10、 同余是處理此類問題的有效方法之一。 例10. （1996年保加利亞）求所有的質(zhì)數(shù)，使得整除解：如果，由費(fèi)馬小定理， ，所以，假設(shè)，則，。不失一般性，我們?cè)O(shè)，則，由裴蜀定理，存在正整數(shù)，使。由費(fèi)馬小定理，所以=，又，所以，矛盾。所以 之一為3 。若，則，所以。類似，因此，解。練習(xí)及參考答案練習(xí)1. 求證：存在無窮多個(gè)這樣的正整數(shù)，它們不能表示成少于十個(gè)奇數(shù)的平方和。分析 對(duì)于否定性問題，我們常利用同余。解：設(shè)正整數(shù)n能夠表示成 = 1 * GB3 ，其中為奇數(shù)，若，則由 = 1 * GB3 及知，即若，則由 = 1 * GB3 及知，從而這說明若，則綜上所述，被8除余2，被9除余3，即具有形式

11、的正整數(shù)便不能表示成 = 1 * GB3 ，故命題得證。評(píng)注 對(duì)于某些問題，常常需要多次選擇不同的模進(jìn)行同余處理。練習(xí)2. 求出大于1的整數(shù)的個(gè)數(shù)，使得對(duì)任意的整數(shù)，都有分析 聯(lián)想例4，猜想的最大值為2730。 解：設(shè)滿足條件的正整數(shù)組成集合S，若，則，因此S 中全部數(shù)的最小公倍數(shù)也屬于S ，即S中的最大數(shù)是其余每個(gè)數(shù)的倍數(shù)。，則的約數(shù)也整除，于是只需確定最大數(shù)，其一切大于1的約數(shù)組成集合S。，并且，由例4，由費(fèi)馬小定理，易證，所以，集合S共有31個(gè)元素。評(píng)注 利用特殊值法確定最大值，再進(jìn)行證明是處理競(jìng)賽問題的典型技巧。練習(xí)3. 但為合數(shù)，則稱341是偽質(zhì)數(shù)，證明：偽質(zhì)數(shù)有無窮多個(gè)。分析 我們

12、想辦法構(gòu)造出具體的表達(dá)或遞推關(guān)系。證明：已知341為偽質(zhì)數(shù)，假設(shè)m是偽質(zhì)數(shù)，下面證明是偽質(zhì)數(shù)，首先，設(shè)，其中為大于1的整數(shù)，則，含有因子，并且，所以為合數(shù)。其次，由于，設(shè)，其中s為大于1的正整數(shù)，而，可被整除，因而，所以是偽質(zhì)數(shù)，并且。由此可知偽質(zhì)數(shù)有無窮多個(gè)。評(píng)注 利用遞推關(guān)系構(gòu)造是解決無窮解問題的重要構(gòu)造方法。練習(xí)4. （第43屆IMO預(yù)選題）求最小的正整數(shù)n，使得：有整數(shù)解。分析 我們先估計(jì)出n的值，在構(gòu)造出一組解。解： ， ，所以 又其中，于是，由于 ，則所以。評(píng)注 選擇適當(dāng)?shù)哪＃猛噙M(jìn)行估計(jì)是重要的方法之一。練習(xí)5. （2003年中國(guó)集訓(xùn)隊(duì)測(cè)試）正整數(shù)n不能被2, 3整除，且不存

13、在非負(fù)整數(shù)a, b，使得|2 a3 b| = n。求n的最小值。分析 我們先通過具體賦值猜出 n 值，再進(jìn)行證明。解：n = 1時(shí)，|2 13 1| = 1；n = 5時(shí)，|2 23 2| = 5；n = 7時(shí)，|2 13 2| = 7；n = 11時(shí)，|2 43 3| = 11；n = 13時(shí)，|2 43 1| = 13；n = 17時(shí)，|2 63 4| = 17；n = 19時(shí)，|2 33 3| = 19；n = 23時(shí)，|2 53 2| = 23；n = 25時(shí)，|2 13 3| = 25；n = 29時(shí)，|2 53 1| = 29；n = 31時(shí)，|2 53 0| = 31；下證n =

14、 35滿足要求，用反證法，若不然，存在非負(fù)整數(shù)a, b，使得 |2 a3 b| = 35。1若2 a3 b = 35，顯然a 0, 1, 2，故a 3，模8，得3 b 3 mod 8，即3 b 5 mod 8，但3 b 1, 3 mod 8，不可能。2若3 b2 a = 35，易知b 0, 1，模9，得 2 a 1 mod 9， 2 k mod 9：2, 4, 8, 7, 5, 1, 2, 4, ， 2 6k 1, 2 6k + 1 2, 2 6k + 2 4, 2 6k + 3 8, 2 6k + 4 7, 2 6k + 5 5 mod 9，于是a = 6k，k為非負(fù)整數(shù)，所以 3 b8 2

15、k = 35。再模7，得 3 b 1 mod 7， 3 k mod 7：3, 2, 6, 4, 5, 1, 3, 2, ，故b = 6k/，k/為正整數(shù)， 3 6k 2 6k = 35，3 3k 2 3k 3 3k + 2 3k = 35， EQ BLC(AAL( 3 3k 2 3k = 1, 3 3k + 2 3k = 35) 或 EQ BLC(AAL( 3 3k 2 3k = 5, 3 3k + 2 3k = 7) 于是，3 3k = 18或6，不可能。綜上可知，nmin = 35。評(píng)注 對(duì)于不定方程無解的問題常用同余處理。練習(xí)6. （2004年亞太地區(qū)數(shù)學(xué)競(jìng)賽）證明：對(duì)于任意正整數(shù)，是偶

16、數(shù)。分析 當(dāng) n 和 n+1 是合數(shù)時(shí)，容易處理，我們只要處理n 和 n+1 之一是素?cái)?shù)的情況。證明：對(duì)于 n = 1, 2, 3, 4, 5 我們有=0，顯然為偶數(shù)。我們考慮 n 6. 如果n 和 n+1 是合數(shù)，則它們 一定整除 (n-1)!，并且互素。所以它們的乘積整除 (n-1)!. 由于 n, n+1 中只有一個(gè)是偶數(shù)，對(duì)于 m 6, (m-2)! 所含的2的冪指數(shù)大于m所含的冪指數(shù),所以是偶數(shù). 我們最后考慮n+1 = p為一個(gè)素?cái)?shù),和 n = p為一個(gè)素?cái)?shù). 如果 n+1 = p, 則 p-1 是一個(gè)合數(shù),所以 p-1 整除(p-2)!. 令 k = ，由威爾遜定理 (p-2)! = 1（mod p）, 所以 k(p-1) = 1（ mod p），因此 k = -1（mod p）.所以 是一個(gè)整數(shù). 但 k 是偶數(shù), 所以k+1 是奇數(shù)，因此是奇數(shù). 又，所以 是偶數(shù).如果 n = p, 則 k =是偶數(shù)，所以 k+1 是奇數(shù). 由威爾遜定理k(p+1) = -1（mod p）,所以