離散數(shù)學(xué)（數(shù)論基礎(chǔ)篇二）

1、第二章 同余與同余式,同余的概念與基本性質(zhì)同余方程組的求解方法線性同余方程、高次同余方程的求解原根和指數(shù)應(yīng)用,第二章 同余與同余式,在日常生活中,有時我們注意的常常不是某些整數(shù),而是這些整數(shù)用某一個固定的整數(shù)去除所得到的余數(shù).例如本月2日是星期3,那么9日,16日,…都是星期3,這是因為它們用7除后得到的余數(shù)都是2在我國古代的干支紀(jì)年也是這樣的,它是以60作為除數(shù)的紀(jì)年法.這樣,在數(shù)學(xué)中就產(chǎn)生了同余的概念.同余概念是

2、Gauss在1800年前后創(chuàng)立的.,2.0 同余定義和基本性質(zhì),定義1 給定一正整數(shù)m, 若用m去除兩個整數(shù)a和b所得余數(shù)相同, 則稱a與b為對模m同余, 記作a?b(mod m); 若余數(shù)不同, 則稱 a與b為對模m不同余。a?b(mod m) iff m|(a-b).a?0(mod m) iff m| a.性質(zhì): ①自反性: a?a (mod m). ②對稱性: 若a?b(mod m),

3、則 b?a(mod m). ③傳遞性: 若a?b(mod m), b?c(mod m), 則: a?c(mod m).可見, 同余關(guān)系是等價關(guān)系.,2.0同余式定義和基本性質(zhì),定理1 若a?b(mod m), c?d(mod m), 則:① ax+cy ? bx+dy(mod m), 其中x和y為任給整數(shù).② ac ? bd(mod m). 1)

4、 設(shè)a ≡ b (modm), c是任意整數(shù).則 ac ≡bc(modm). 2) 設(shè)ai≡ bi (modm)(i =1,2,…,n, n>2),則 a1a2…an ≡b1b2…bn (modm).③ an ? bn(mod m), 其中 n＞0.④ f(a) ?f(b)(mod m), 其中f(x)為任意的一個整系數(shù)多項式.,同余在算術(shù)里的兩個應(yīng)用：,應(yīng)用1——檢查因數(shù)的一些方法 一整數(shù)能

5、被3(9)整除 iff 它的十進(jìn)位數(shù)碼的和能被 3(9)整除.正整數(shù)a=an1000n+an-11000n-1+ … +a0 , 0≤ai<1000, 則7(或11,或13)整除a iff 7(或11,或13)整除(a0 + a2 + …)-(a1 + a3 + …).,* 正整數(shù)a能被9整除 iff 9整除a的十進(jìn)制表示各數(shù)字的和．證明 若 ,

6、 則由 10i?1(mod 9) (i=1,2,…,n)和定理 1④可得: 注：因為10≡1(mod3)，同理, 一個整數(shù)能被3整除的必要充分條件是它的10進(jìn)位數(shù)碼的和能被3整除.,同余的算術(shù)應(yīng)用1,同余的算術(shù)應(yīng)用1,** 正整數(shù)a能被7(或11，或13)整除 iff 7(或11，或13) 整除a的定理十進(jìn)制表示各數(shù)字的交錯和 ．證明：因為1

7、000與-1對模7(或11，或13)同余， 由同余性質(zhì)， (或mod11，或mod13). 所以 ，結(jié)論得證。???,同余的算術(shù)應(yīng)用2 ——棄九法,*證明了“棄九法”（棄九驗算法）：把一個數(shù)的各位數(shù)字相加，直到和是一個一位數(shù)（和是9，要減去9得0），這個數(shù)就叫做原來數(shù)的棄九數(shù)．且一個數(shù)的棄九數(shù)與其模9的余數(shù)相等。利用這種方法可以驗

8、算較大整數(shù)的加法、減法、乘法運算的結(jié)果是否正確，也可驗算除法，但需轉(zhuǎn)化成乘法。,棄九法,例1 驗算 851+346=1198．解： 先分別求出兩個加數(shù)的棄九數(shù)與和的棄九數(shù)． 851、346的棄九數(shù)分別是5，4，1198的棄九數(shù)1． 兩個加數(shù)的棄九數(shù)相加得4+5=9，棄掉9后是0，而題目中和的棄九數(shù)是1，可以說這道題一定錯誤。注：利用棄九法檢驗運算的結(jié)果是否正確時， 如果等號兩邊的九余數(shù)不相等，那么這個算式肯定不

9、正確； 如果等號兩邊的九余數(shù)相等，那么還不能確定算式是否正確，因為九余數(shù)只有0，1，2，…，8九種情況，不同的數(shù)可能有相同的九余數(shù)。所以用棄九法檢驗運算的正確性，只是一種粗略的檢驗。,棄九法,例2 求證 1997×57≠113828.證明 由于1997?1＋9＋9＋7?8 (mod 9) 57? 5＋7 ? 3(mod 9) 113828 ? l+1+3

10、+8+2+8 ? 5(mod 9)但是, 8×3=24, 而24≠5(mod 9), 得證.,同余的應(yīng)用舉例,例1 已知2001年的國慶節(jié)是星期一，求2010年的國慶節(jié)是星期幾？,分析： 一星期有7天，要求2010年的國慶節(jié)是星期幾，就要求從2001年到2010年的國慶節(jié)的總天數(shù)被7除的余數(shù)就行了。但在計算中，如果我們能充分利用同余性質(zhì)，就可以不必算出這個總天數(shù)。,解： 2001年國慶節(jié)到2010年國慶節(jié)之間共有2個閏年

11、 7個平年，即有“366×2+365×7”天?！?366×2≡2×2≡4（mod 7）， 365×7≡1×7≡0（mod 7），∴366×2+365×7≡2×2+1×7≡4+0≡4（mod 7） 答：2010年的國慶節(jié)是星期五。,同余的應(yīng)用舉例,例2 　判定21991 + 1 、 21998 + 1

12、 是否為質(zhì)數(shù)。,分析： 期望找到正整數(shù)m ,使 21991 + 1 ≡0 (mod m) , 即　 21991 ≡- 1 (mod m) .,解： 因為2 ≡- 1 (mod 3) ,所以, 21991 + 1 ≡ (-1)1991 + 1≡ (- 1) + 1 = 0 (mod 3) . 從而, 21991 + 1 為合數(shù). 因為4 ≡- 1 (mod 5) ,所以, 2

13、1998 + 1 =4999+ 1 ≡ (-1)999 + 1 ≡ (-1)+ 1 = 0 (mod 5) . 從而, 21998 + 1 為合數(shù).,2.0同余式定義和基本性質(zhì),定理 3 若ac=bc(mod m), (c,m)=d, 則 a ? b(mod (m/d))證明 因為m|c(a-b), 于是(m/d)|((a-b)(c/d)), 又因為(c,m)=d, 則有((c/d,

14、m/d)=1, 因此 (m/d)|(a-b), 即: a ? b(mod (m/d)).顯然, 由本定理可得如下推論.推論 若 ac=bc(mod m), (c,m)=1,則: a?b(mod m).,2.0同余式定義和基本性質(zhì),定理4 ① 若a?b(mod m), 且d|m, 則: a?b(mod m).③ 若a?b(mod m), 則 (a,m)=(b,m).③ a?b(mod mi)

15、, (1≤i≤n), iff a?b (mod [m1,m2,…,mn]).證明 只給出③的證明, ①和②讀者完成. ③必要性:由①知,是成立的. 充分性: 若a ? b(mod mi), 1≤i≤n, 則: mi|(a-b), 1≤i≤n, 即(a-b)是m1,m2,…,mn的公倍數(shù), 從而也是[m1,m2,…,mn]的倍數(shù), 因此: a?b (mod [m1,m2,…,mn]).,2.0同余式定義和基本性質(zhì),

16、下面證明一個重要定理, 從應(yīng)用和理論來說都有非常大的意義. 尤其在理論上,它完全解決了判斷給定的數(shù)是否為素數(shù)的問題.定理 (威爾遜定理) p為素數(shù) iff (p-l)!?-1(mod p).,定理 (威爾遜定理) p為素數(shù) iff (p-l)!?-1(mod p).,證明 必要性: 設(shè)p為一素數(shù), 當(dāng)p=2,3時, 結(jié)論顯然成立. 現(xiàn)設(shè)p>3是一奇素數(shù), S={2, 3, …, p-2}，a?S. 因

17、為(a,p)=1, 存在整數(shù)m和n, 使am+pn=1, 于是am?1(mod p). 設(shè)b=m-pq, 即b是p除m的余數(shù), 易知 b≠1, b≠p-1, 故 b?S, 且 ab?1(mod p). 可以證明 a≠b.,定理 (威爾遜定理) p為素數(shù) iff (p-l)!?-1(mod p).,假設(shè) a=b, 則有(b-1)(b+1)?0(mod p), 而 b≠l, b ≠p-1, 故(b-1)(b+1)?0(

18、mod p)不成立. 可見S中的數(shù)可分成(p-3)/2對, 每一對數(shù)a和b, 滿足 ab?l(mod p), 故得2·3…(p-2) ? (mod p), 即可得(p-1)! ?-1 (mod p).,定理 (威爾遜定理) p為素數(shù) iff (p-l)!?-1(mod p).,充分性: 若(p-1)! = -l (mod p), 則 p為素數(shù). 假設(shè)p是合數(shù), 令 p＝ab, a≠p.

19、 由題設(shè)條件知, p|((p-1)!+l). 又因 a|p, 則有 a|((p-1)!+1). 但由于 a≤p-1可得 a|(p-1)!, 從而 a|(((p-1)!+1)-(p-1)!), 即a|l, 因而p只有因子1和p, 即p為素數(shù).,同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用,同余的應(yīng)用1：國際圖書標(biāo)準(zhǔn)(ISBN編碼) ISBN是intern

20、ational standard of book number 的縮寫，即國際標(biāo)準(zhǔn)圖書編號。ISBN是國際通用的圖書或獨立的出版物(除定期出版的期刊)代碼。出版社可以通過ISBN清晰地辨認(rèn)所有非期刊書籍。一個ISBN只有一個或一份相應(yīng)的出版物與之對應(yīng)。新版本如果在原來舊版的基礎(chǔ)上沒有內(nèi)容上太大的變動，在出版時也不會得到新的ISBN號碼。當(dāng)平裝本改為精裝本出版時，原來相應(yīng)的ISBN號碼也應(yīng)當(dāng)收回。 國際標(biāo)準(zhǔn)圖書編號問世后，

21、很快得到推廣，主要是因為它對出版商、書商的工作有很大的益處，體現(xiàn)在:國際標(biāo)準(zhǔn)書號是機(jī)讀的編碼，從圖書的生產(chǎn)到發(fā)行、銷售始終如一，對圖書的發(fā)行系統(tǒng)起了很大的作用;它的引入使圖書的定購、庫存控制、賬目和輸出過程等任何圖書業(yè)的分支程序都簡化了;國際標(biāo)準(zhǔn)書號也對圖書館和文獻(xiàn)中心的訂購、采選、編目和流通程序都有促進(jìn)作用;ISBN系統(tǒng)的引入也服務(wù)于書目信息的流動和使用，而且為一個國家的圖書生產(chǎn)提供經(jīng)濟(jì)的書目控制;ISBN對圖書市場更有效率，它能確定

22、國際上出版的任何圖書及其出版社。在書業(yè)中習(xí)慣稱ISBN為庫藏碼(Stock Number)，就是因為其被普遍應(yīng)用于書庫管理。,同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用,10位數(shù)ISBN的結(jié)構(gòu)　　現(xiàn)行的ISBN由10位數(shù)字組成，這10位數(shù)字由4組數(shù)字組成，中間用“-”相連，每組數(shù)字都有不同的含義。第一組號碼是地區(qū)號，又叫組號，最短的只有一位數(shù)字，最長的達(dá)五位數(shù)字，大體上兼顧文種、國別和地區(qū)。0、1代表英語，使用這兩個代碼的國家有:澳大利亞、加

23、拿大、愛爾蘭、新西蘭、波多黎各、南非、英國、美國、津巴布韋等;2代表法語，法國、盧森堡以及比利時、加拿大和瑞士的法語區(qū)使用該代碼;3代表德語，德國、奧地利和瑞士德語區(qū)使用該代碼;4是日本出版物的代碼;5是俄羅斯出版物的代碼;7是中國出版物使用的代碼。第二組: 出版社代碼。由國家或地區(qū)的ISBN中心設(shè)置并分給各個出版社。第三組:書序碼。該出版物代碼，是出版者分配給每一個出版物的編號。第四組:計算機(jī)校驗碼。校驗碼是ISBN號的最后一位

24、數(shù)值，它能夠校驗出ISBN號是否正確。校驗碼只能是1位數(shù)，當(dāng)為10時，記為羅馬數(shù)字X。,同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用,左圖是2007實行的新的ISBN標(biāo)準(zhǔn)，從10位升到13位，為了講課方便，我們?nèi)匀挥?007年以前的10位標(biāo)準(zhǔn)來講述：,同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用,同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用,同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用,同余的應(yīng)用2：驗證信用卡的有效性首先注意到不同的信用卡的標(biāo)識碼的長度和前綴都不一樣，本節(jié)只介紹國際上比較

25、流行的Master卡，該卡標(biāo)識碼為16位，以51，52，53，54或者55開頭.比如：5548 3742 7983 0696在Master卡中，具備如下性質(zhì)：1.如果第2位為1，則第2到3位表示銀行號。2.如果第2位為2，則第2到4位表示銀行號。3.如果第2位為3，則第2到5位表示銀行號。4.如果第2位為其他值，則第2到6位表示銀行號。銀行號后面直到第15位為持卡人賬號，最后一位為校驗位。比如剛才的例子中，第2位為5，則

26、銀行號為54837，持卡人賬號為427983069,同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用,同余關(guān)系及其在計算機(jī)領(lǐng)域的應(yīng)用,2.1 一次同余式組,本節(jié)介紹一次同余式組的解法及其應(yīng)用舉例．在公元三世紀(jì)前,《孫子算經(jīng)》里已提出了下面的同余式組x?b1(mod m1), x?b2(mod m2),…, x?bk(mod mk) (1)這種形式的問題, 并且很好地解決了它.《孫子算經(jīng)》里所提出的問題之一如下:“今有物不知其數(shù), 三三數(shù)之剩二,

27、五五數(shù)之剩三, 七七數(shù)之剩二. 問物幾何？” “答日二十三.”,15:51:43,2.1 一次同余式組,把這個問題的提法用同余式的式子來表達(dá)，它可表示成解同余式組x?2(mod 3), x?3(mod 5), x?2(mod 7)其中x是所求物數(shù).關(guān)于同余式組:x?a(mod 3), x?b(mod 5), x?b(mod 7) 的一般解為:x ? 70a+21b+15c (mod 105),15:51:43,2.1 一次

28、同余式組,這個解法, 在明朝程大位的《算法統(tǒng)宗》(1593)里有下面一首詩歌:三人同行七十稀，五樹梅花甘一枝，七子團(tuán)圓整半月，除百零五便得知。關(guān)于解同余式組的問題, 在我國古代有極光輝的研究成果. 我國古代數(shù)學(xué)家孫子發(fā)明了下面的中外馳名的定理, 在國外譽為中國剩余定理, 在國內(nèi)稱為孫子定理.,15:51:43,2.1 一次同余式組,定理1 一次同余式組x?b1(mod m1), x?b2(mod m2) (1)有解 i

29、ff (m1,m2)|(b1-b2), 且當(dāng)(1)有解時對模[m1,m2]有唯一解.證明： 設(shè)(1)有解x0, (m1,m2)=d, 則有:x0?b1(mod m1), x0?b2(mod m2)m1=dq1, m2=dq2 于是, x0-b1=dq1m’1, x0-b2=dq2m’2, 因此, d|(b1- b2). 若(m1,m2)|(b1-b2),則因x?b1(mod m1)可表示為: x=b1+m1y, 代入x?

30、b2(mod m2)得: m1y?(b2-b1)(mod m2) (2) 因為(m1,m2)=d, d|(b2-b1), (2)有解, 設(shè)為y0, 且對模m2/d有唯一解:y?y0(mod (m2/d)),,15:51:43,2.1 一次同余式組,證明(續(xù))：即 y=y0+km2/d, k=0,±1, ±2, …. 因此(1)的全部解為: x=b1+m1y0+m1m2k/d, k=0,

31、77;1, ±2, …. 這些解對模[m1,m2]是同余的, 故(1)的解對模[m1,m2]唯一.,定理1 一次同余式組x?b1(mod m1), x?b2(mod m2) (1)有解 iff (m1,m2)|(b1-b2), 且當(dāng)(1)有解時對模[m1,m2]有唯一解.,15:51:43,2.1 一次同余式組,對于一次同余式組: x?b1(mod m1), x?b2(mod m2),…, x?bk(mod mk)

32、, k>3的情形, 可先解前兩個得x?b’1(mod[m1,m2]), 再與x?b3(mod m3)聯(lián)立解出x?b’3(mod[m1,m2,m3]). 如此繼續(xù)下去, 最后可得唯一解x?b’k(mod[m1,m2 ,…,mk]). 注 若中間有一步出現(xiàn)無解, 則同余式組無解.,15:51:43,2.1 一次同余式組,定理2 (孫子定理)設(shè)m1, m2, …, mk是兩兩互素的k個正整數(shù), k＞=2,

33、 并且m＝ m1 m2 … mk , m=miMi, 1≤i≤k, 則同余式組(1)有唯一解x?b1M1’M1+b2M2’M2+…+bkMk’Mk(mod m)(2)其中Mi’Mi?1(mod mi), 1≤i≤k.證明: (mi,mj)=1, i≠j, 即得(Mi,mi)=1. 對每一Mi, 存在M’i, 使得M’iMi ? 1(mod mi) (3)另一方面, 當(dāng)i≠j時, 則由(mi,mj)=1和m＝mjMj得到mi

34、|Mj, 所以有:bjM’jMj ?0(mod mi) (4),15:51:43,2.1 一次同余式組,由(3)和(4)有即(2)是(1)的解.若y也是(1)的解, 則得:x?y(mod mi), 1≤i≤k于是, mi|(x-y), 1≤i≤k. 由于ml, m2, …,mk兩兩互素. 故m|(x-y), 即x?y(mod m). 因此是(1)的唯一解.,15:51:43,2.1 一次同余式組,應(yīng)用孫子定理可

35、以證明如下定理.定理 3 設(shè)m1,m2,…,mk是兩兩互素的 k個正整數(shù), m＝m1m2…mk ,則同余式:f(x)?0 (mod m) (1) 有解 iff 同余式組:f(x)?0 (mod mi), 1≤i≤k (2) 的每個同余式有解, 且若用S表示(1)的解數(shù), Si表示(2)的解數(shù), 則: S＝S1S2…Sk.,15:51:43,2.1一次同余式組,證明: 若x0是

36、滿足(1)的整數(shù), 則由f(x0)?0(mod m), 可得f(x0)?0(mod mi), 1≤i≤k. 反之, 若xi滿足(2), 1≤i≤k, 因為1≤i<j≤k, (mi,mj)=1, 由孫子定理, 有唯一的x0, 0≤x0<m, 滿足x0? xi(mod mi), 1≤i≤k, 且f(x0)? f(xi)?0(mod mi), 1≤i≤k. 故f(x0)?0(mod m)

37、.充要條件得證。 現(xiàn)在設(shè)(2)有Si個不同解是x?aiji(mod mi), 0≤aiji< mi, 1≤i≤k , l≤ji≤Si, 對其中任一組a1ji, a2ji,…, akji, 由孫子定理可得唯一的x, 0≤x<m, 是(1)的解, 且不同的組, 得到(1)的解也不同, 故S＝S1S2…Sk.,15:51:43,例1 韓信點兵:有兵一隊, 若列成五行縱隊, 則末行一人; 成六行縱隊, 則末行

38、五人; 成七行縱隊,則末行四人; 成十一行縱隊,則末行十人, 求兵數(shù).解： 設(shè)x是所求兵數(shù), 則依題意:x?1(mod 5), x ?5(mod 6)x?4(mod 7), x ?10(mod 11) 令m1=5,m2=6,m3=7,m4=11,b1=l, b2=5, b3=4, b4=10. 于是m=m1m2m3m4=5×6×7 × 11=2310, M1=2310/5=462, M2

39、=385, M3=330, M4=210. 有M’1M1?1(mod 5), 即1?462 M’1 ?2M’1(mod 5) ,因此M’1=3. 同理可求M’2=1, M’3=1, M’4=1. 故解為:x ?1×3×462+1×5×385+1×4×330 + 1×10×210 ?6731 ?2111(mod 2310). 即 x=2111+23

40、10k, k=0,1,2,….,2.2 剩余類和剩余系,由于同余關(guān)系是等價關(guān)系, 因此對于給定的任一工整數(shù)m, 利用模m同余這個關(guān)系, 可將整數(shù)集劃分成m個等價類, 由于它是一些整數(shù)除m后的余數(shù)形成的, 所以稱它是剩余類或同余類.于是有:定義1 設(shè)m是一給定的正整數(shù), 若 [r] = {i: i?r(mod m), i?Z}, 0≤r≤m-1} 則稱[r]是模m剩余類.設(shè)a是任一整數(shù), 則a＝mq+r

41、, 0≤r<m, 故a恰包含在[r]中. 若a和b是兩整數(shù), 且在[r]中, 則a＝mq1+r, b=mq2+r, 故m|(a-b). 反之, m|(a-b), 則由同余定義即知a和b同在某一類[r]中, 0≤r<m.,2.2 剩余類和剩余系,定義2 在模m剩余類[0], [1], …,[m-1]中各取一數(shù)ar?[r], 0≤r≤m-1, 該m個數(shù)a0,a1,…,am-1稱為模m的一完全剩余系. 若令x={a0,a1,

42、…,am-1}, 則稱x是過模m的完全剩余系.由此定義得以下定理.定理1 m個整數(shù)構(gòu)成模m的一完全剩余系 iff 兩兩對模 m不同余．最常用的完全剩余系0,1,2,…,m-1, 稱為模m的非負(fù)最小完全剩余系．1,2 ,…,m, 稱為模m的最小完全正剩余系．,2.2 剩余類和剩余系,定理2 設(shè)a0,a1,…,am-1是模m的一完全剩余系, b是一整數(shù), 則a0+b,a1+b, …,am-1+b也是模m的一完全剩余系.

43、證明： 假設(shè)(ai+b)?(aj+b)(mod m), 0≤i<j≤m-1, 則 m|(ai-aj), 由定理1和a0,a1,…,am-1是模m的一完全剩余系,知假設(shè)不真,即a0+b,a1+b, …,am-1+b是兩兩對模m不同余. 由定理1知, 它們是模m的一完全剩余系.,2.2 剩余類和剩余系,定理3 若a0,a1,…,am-1是模m的一完全剩余系, (b,m)=1. 則 ba0,ba1,…,

44、bam-1也是模m的一完全剩余系.證明 仿定理2可證.由定理2和3可證如下定理.定理4 若a0,a1,…,am-1是模m的一完全剩余系b和c是任意二整數(shù)且(b,m)=1, 則ba0+c, ba1+c, …,bam-1+c也是模m的一完全剩余系.,2.2 剩余類和剩余系,定理5 設(shè)m1,m2是正整數(shù), (m1,m2)=1, a0,a1,…,am1-1 , b0, b1, bm2-1分別是模m1和模m2的一完全剩余系, 則S={m

45、2ai+m1bj} 0≤i≤m1-1∧0≤j≤m2-1} 是模 m1m2的一完全剩余系．本定理也可簡述如下: 設(shè)m1和m2是大于零的整數(shù), (m1,m2)=1,x1和x2分別是過模m1和m2的完全剩余系, 則m2x1+m1x2是過模m1m2的完全剩余系.,2.2 剩余類和剩余系,證明： 顯然S中有m1m2個整數(shù), 由定理 1知, 只需證明它們對模m1m2兩兩不同余即可. 假設(shè)m2ai1+m1bj1?m2ai2+m1

46、bj2(mod m1m2), 0≤i1, i2≤ m1-1, 0 ≤j1,j2≤m2-1. 得，m2ai1?m2ai2 (mod m1), m1bj1?m1bj2(mod m2), 因為(m1, m2)=1, 故 ai1? ai2(mod m1), bj1? bj2(mod m2). 由于ai1,ai2是模ml的完全剩余系中的數(shù), 故ai1=ai2. 同理bj1=bj2. 因此, 若{ai1,ai2}和{bj1,

47、bj2}不同,則m2ai1+m1bj1≠m2ai2+m1bj2(mod m1m2). 因此 S是模m1m2的一完全剩余系.,2.2 剩余類和剩余系,1948年,喬拉(Chowla)等人證明了如下定理.定理6 設(shè)a1,a2,…,an, b1, b2, bn分別是模n的一完全剩余系, n>2, a1b1,a2b2,…,anbn 則不是模n的一完全剩余系.證明 讀者可參見有關(guān)書籍的證明．,2.2 剩余類和剩余系,下面介紹歐

48、拉函數(shù)與簡化剩余系．定義3 小于或等于m且與m互素的正整數(shù)個數(shù)，記為中?(m), 稱為歐拉(Euler)函數(shù).由定義知, ?(1)=1, ?(2)=1, ?(3)=2, ?(4)=2, ?(5)=4, ?(6)=2, ?(7)=6, ?(8)=4, ?(9)=6,….當(dāng)p是素數(shù)時, ?(p)=p-1.,2.2 剩余類和剩余系,定理7 設(shè)p是一素數(shù), k是一正整數(shù), 則: ?(pk)=pk-1(p

49、-1)證明 因為小于或等于pk且與pk不互素的正整數(shù)恰是p的各個倍數(shù):1·p,2·p,3·p,…,(pk-1)·p顯然共有pk-1個. 而小于或等于pk的正整數(shù)總共有pk個, 于是: ?(pk)= pk – pk-1= pk-1 (p-1).,2.2 剩余類和剩余系,定義4 若模m剩余類中的數(shù)與m互素, 則稱它為與模m互素的剩余類, 在與模m互素的所有剩余類中, 各取一數(shù)所組成的

50、集合, 稱為模m的一個簡化剩余系（縮系）.由上面定義, 顯然有下面二定理:定理8 模m簡化剩余系含有中?(m)個數(shù).定理9 若a1,a2,…,a?(m)是中?(m)個與m互素的整數(shù), a1,a2,…,a?(m)是模m的一簡化剩余系 iff 它們兩兩對模m不同余.,2.2 剩余類和剩余系,定理 10 若(a,m)=1, rl,r2,…,r?(m)是模 m的一簡化剩余系, 則arl,ar2,…,ar?(m)也是模m的一簡化

51、剩余系.證明： 只需證明arl,ar2,…,ar?(m) 互不同余,且都與m互素即可. 假設(shè)ari?arj(mod m), 其中1≤i, j ≤?(m). 由于(a,m)=1, 故有ri?rj(mod m), 這與rl,r2,…,r?(m)是模 m的一簡化剩余系矛盾, 故ari≠arj(mod m), 即: arl,ar2,…,ar?(m)兩兩互不同余. 假設(shè)p是m和某ari的公共素

52、因數(shù), 其中1≤i≤?(m), 因p是素數(shù), 故p|a或p|ri. 因此, p是a和m的公因數(shù), 或是ri和m的公因數(shù), 這與(a,m)=(ri,m)=l矛盾, ∴(ari,m)=l, l≤i＜?(m) .即ari與m互素.,2.2 剩余類和剩余系,定理11 (歐拉定理)設(shè)m＞2, 且(a,m)=1,則:a?(m)?1(mod m).證明: 設(shè)rl,r2,…,r?(m)是模m的一簡化剩余系, 則由定理10知, rl,

53、r2,…,r?(m)也是模m的一簡化剩余系. 故 (arl)(ar2)…(ar?(m))?rlr2…r?(m) (mod m). 即 a?(m) rlr2…r?(m) ?rlr2…r?(m) (mod m). 由于(ri,m)=1, 1<i≤?(m), 故(rlr2…r?(m),m)=1. ∴ a?(m)?1(mod m).,2.2 剩余類和剩余系,注意到, 令m＝p, 且p是素數(shù), 立刻得到如下定理.

54、定理12(費馬定理) 若p是素數(shù), 則: ap-1 ?1(mod m).定理13 設(shè)m1,m2是正整數(shù), (m1,m2)=l, rl,r2,…,r?(m1)和r’l,r’2,…,r’?(m2)分別是模m1和模 m2的一簡化剩余系, 則S={m2ri+m1r’j}1≤i, j ≤?(m)是模m1m2的一簡化剩余系.,定理13 設(shè)m1,m2是正整數(shù), (m1,m2)=l, rl,r2,…,r?(m1)和r’l,r’2,…,r’?(m

55、2)分別是模m1和模 m2的一簡化剩余系, 則S={m2ri+m1r’j}1≤i, j ≤?(m)是模m1m2的一簡化剩余系.,證明: 首先證明(m2ri+m1r’j,m1m2)=1, 其中1≤i≤?(m1), 1≤j≤?(m2), 否則, 有素數(shù)p, p| m2ri+m1r’j, p|m1m2, 若p|m1， 則p|m2r2, 而p不能整除ri, 故 p|m2, 這(m1 ，m2)=1矛盾; 若p|m2, 可得出相

56、同矛盾. 這便證明了?(m1)??(m2)個數(shù)(m2ri+m1rj)均與m2m1互素.其次, 根據(jù)定理 5知 S中任兩數(shù)對模 m2m1不同余. 因此, S是模m2m1的一簡化剩余系. 再次， m2m1的縮系中任一元必是S中的元素。,2.2 剩余類和剩余系,由該定理,立即可得如下推論:推論（歐拉函數(shù)的積性性質(zhì)） 若(m1,m2) =1, 則 ?(m1

57、m2)= ?(m1)?( m2).定理 14 若 , 其中p1,p2,…, pn是素數(shù), ?l,?2,…, ?n是正整數(shù), 則:證明： 由歐拉函數(shù)的積性性質(zhì) 從定理7知, , 1≤i≤n.因此:,2.2 剩余類和剩余系,例1. 求證6,9,12,15,18,2

58、1,24,27是模8的一完全剩余系,而其中9,15,21,27是模8的一簡化剩余系,證明： (1)由于 6?6(mod 8), 9?1(mod 8), 12?4(mod 8), 15?7(mod 8),18?2(mod 8), 21?5(mod 8), 24?0(mod 8), 27?3(mod 8), 6,l,4,7,2,5,0,3和0,1,2,3,4,5,6,7只是次序不同,故6,9,12,15,18, 21,24,2

59、7是模8的一完全剩余系. (2) 9,15,21,27和1,3,5,7只是次序不同,?(8)=4, 因此9,15, 21,27是模8的一簡化剩余系.,2.3 不定方程,不定方程是指未知數(shù)個數(shù)多于方程個數(shù)，且對解有一定限制(比如要求解為正整數(shù)等)的方程．不定方程是數(shù)論中最古老的分支之一．古希臘的丟番圖早在公元3世紀(jì)就開始研究不定方程，因此常稱不定方程為丟番圖方程．中國是研究不定方程最早的國家，宋代數(shù)學(xué)家秦九韶的大衍求一術(shù)將不定方程

60、與同余理論聯(lián)系起來．研究不定方程要解決三個問題：①判斷何時有解；②有解時確定解的個數(shù)；③求出所有的解．消元化簡：在處理多元的不定方程當(dāng)中，一般通過聯(lián)立各個方程，消去那些暫時不用或者限制條件較少的未知數(shù)，將多元方程組轉(zhuǎn)化成二元的整系數(shù)不定方程進(jìn)行處理。,2.3 不定方程,定理1 如x0和y0為ax+by=c的一組解,則對任何整數(shù)t，x0+bt,y0-at也是ax+by=c的解。定理2 方程ax+by=c有整數(shù)解 iff (

61、a,b)|c。證明: 假定存在x0和y0使ax0+by0=c,因 (a,b)|ax0,(a,b)|by0,所以(a,b)|c. 反之,假定(a,b)|c,則有某一m,使c=m(a,b).存在r和s,使ar+bs=(a,b) 因此a(rm)+b(sm)=m(a,b)=c 從而x=rm,y=sm是一組解。,2.3 不定方程,定理3 假定ab≠0,(a,b)=1,且x0,

62、y0是ax+by=c的一組解,則ax+by=c的所有解可寫為 x=x0+bt , y=y0-at,其中t是整數(shù)。證明： 由定理2,因為(a,b)=1,對任何c,有1|c,方程確實有解. 設(shè)r,s是ax+by=c的任意解.我們要證, r=x0+bt,s=y0-at必對某一整數(shù)t成立. 由ax0+by0=c得 c-c=(ax0+by0)-(ar+bs)即

63、 a(x0-r)+b(y0-s)=0由a|a(x0-r)和a|0,可得a|b(y0-s),由于(a,b)=1,所以a|y0-s。即存在一個整數(shù)t,使at=y0-s。 ∴ s=y0-at,r=x0+bt。,定理3 假定ab≠0,(a,b)=1,且x0,y0是ax+by=c的一組解,則ax+by=c的所有解可寫為 x=x0+bt , y=y0-at,其中t是整數(shù)。,注： 假定ab≠0。若(a,b)不

64、整除c,則線性不定方程ax+by=c無解; 若(a,b)|c,則對a’x+b’y=c’(其中a’=a/(a,b),b’=b/(a,b),c’=c/(a,b))可找到一組解x=r, y=s,且ax+by=c的所有解可寫為 x=r+b’t, y=s-a’t,其中t是任意整數(shù)。,2.3 不定方程,定理4 不定方程有整數(shù)解的充分必要條件是 。

65、證明： 必要性:設(shè)d=(a1,a2,…,an),顯然d|N 充分性:設(shè)計一個算法求解。 算法如下：求解算法(歸納法):基礎(chǔ):二元一次方程有解。歸納:令d2=(a1,a2), 則(d2,a3,a4,…,an)=d|N.由歸納假定,方程d2t2+a3x3+…+anxn=N有解,設(shè)其一解為t2’,x3’,..,xn’.再考慮a1x1+a2x2=d2t2’,用歐幾里得算法可求得一解為x1’,x2’.則 a1

66、x1’+a2x2’+a3x3’+…+anxn’=N,定理4 不定方程有整數(shù)解的充分必要條件是 。,先求最后一個方程的一切解，然后代入倒數(shù)第二個，繼續(xù)求解，往上代入。a1x1+a2x2=d2t2d2t2+a3x3=d3t3……….dn-2tn-2+an-1xn-1=dn-1tn-1dn-1tn-1+anxn=N,2.4 一次同余式,本節(jié)主要討論一次同余式. 先給出同余式及其解的概

67、念.定義1 設(shè) , 其中, m是正整數(shù), n>0, ai是整數(shù), 0≤i≤n, 則f(x)?0(mod m) (1)稱為模 m同余式. 若 an≠0(mod m), 稱n是(1)的次數(shù). 若 x0滿足 f(x)?0(mod m), 則 x?x0(mod m)稱為(1)的解. 注：不同解是指互不同余的解.,2.4 一次同余式,注意, 若x0是(1)的解, 則

68、模m的剩余類[x0], 即全部整數(shù)x0+km, k=0, ±1, ±2,…中每一個都是滿足(1), 而x0是[x0]非負(fù)最小整數(shù), 即是非負(fù)最小剩余.由定義可知, 要求(1)的解, 只要逐個把0,1, 2, …,(m-1)代人(1)中進(jìn)行驗算即可.但當(dāng)m大時, 計算量往往太大.下面就來討論一元一次同余式的解的問題.,2.4 一次同余式,定理 11 設(shè)(a,m)=1, m>0, 則ax?b(mod m)

69、 (2) 恰有一解, 且 x?ba?(m)-1(mod m)證明 因為0,1,…,m-1是模m的一完全剩余系, (a,m)=1, 故0,a,2a,…,(m-1)a也是模m的一完全剩余系, 所以其中恰有一整數(shù), 設(shè)為ka, 滿足ka ?b(mod m), 即k滿足(2)，因而x?k(mod m)是(2)的唯一解.由歐拉定理，立即可得x?ba ?(m)-1(mod m).,2.4 一次同余式,定理2 設(shè)(a,m)=d,