數(shù)論算法講義 2章（同余運(yùn)算）

1、第 2 章 同余運(yùn)算（一） 內(nèi)容l 同余概念l 性質(zhì)l 剩余類整數(shù)分類l 模冪運(yùn)算（二） 重點(diǎn)l 同余及其計(jì)算（三） 應(yīng)用：l 密碼學(xué)l 公鑰密碼學(xué)【例】RSA公鑰算法：準(zhǔn)備：選大素?cái)?shù)p、q，記npq，(n)(p1)(q1)，再選正整數(shù)e，滿足（e，(n)）1（mod n）并求d，滿足 ed1（mod (n)）加密：明文串P編碼為數(shù)字M，則密文C（mod n）解密： M（mod n），再將數(shù)字M解碼得明文串P2.1 同余的概念及基本性質(zhì)(一) 同余概念【定義2.1.1】給定一個(gè)正整數(shù)m，兩個(gè)整數(shù)a、b叫做模m同余，如果ab被m整除，或，記作；否則叫做模m不同余，記作ab（mod m）【注】由于

2、等價(jià)于，所以同余式等價(jià)于，故以后總假定模。判斷同余的方法一：利用定義【例1】728291，故291（mod 7）；721276，故276（mod 7）；72823（5），故235（mod 7）；(二) 性質(zhì)【性質(zhì)1】（定理1）設(shè)m是一個(gè)正整數(shù)，a、b是兩個(gè)整數(shù)，則ab（mod m）存在整數(shù)k，使得abkm。（證）ab（mod m） 存在k，使得 abkm，即abkm【性質(zhì)2】（定理2）同余是一種等價(jià)關(guān)系。即（i） 自反性：aa m（ii） 對(duì)稱性：ab （mod m） ba （mod m）（iii） 傳遞性：ab mod m且bc （mod m） ac （mod m）（證）（i）m0aa aa

3、 m （ii）ab （mod m） mab mba(ab) ba （mod m）（iii）ab （mod m），bc （mod m） mab，mbc m(ab) (bc)ac ac （mod m）【例3】【性質(zhì)3】（等價(jià)定義）（定理3）整數(shù)a、b模m同余a、b被m除的余數(shù)相同。（證）由歐幾里得除法，存在q，r，使得qmr，bm即 ab(q)m(r)或 （r）(ab) (q)m故 m(ab) m(r)但 0rm且m(r) r0故 m(ab) r0，即r【性質(zhì)4】（定理4）設(shè)m為正整數(shù)，a、b、c、d為整數(shù)，若ab （mod m）， cd （mod m）則（i） acbd （mod m）；（ii）

4、 acbd （mod m）。（證）已知ab （mod m）且 cd （mod m） abhm且cdkm ac(bhm)( dkm)bd(hk)m，ac(bhm)( dkm)bd(hdkbhkm)m 由性質(zhì)1即得結(jié)論。一般情形：（mod m）（i1,2,k），則（i） （mod m）（ii） （mod m）【推論1】 ab （mod m） nanb （mod m），其中n為正整數(shù)?！就普?】 ab （mod m）（mod m），其中n為正整數(shù)。【推論3】（定理5）xy （mod m），（mod m）（i1,2,k），則（mod m）【例6】（例6）2003年5月9日是星期五，問(wèn)此后的第22003

5、是星期幾？（解） 2200355 mod 75 mod 79 mod 72 mod 7【例】（定理6）設(shè)十進(jìn)制整數(shù)n，則3n 39n 9（證）因nmod 3n mod 9【例】（定理7）設(shè)整數(shù)n的1000進(jìn)制表示式為n則7（或11，或13）n 7（或11，或13）（證）因n mod 7n mod 11n mod 13例如，判斷n1234567能否被7整除：1234567812×10002+345×1000+678而 (12+678)345345不能被7、11、13整除故1234567不能被這3個(gè)數(shù)整除?！纠浚ㄑa(bǔ)）設(shè)十進(jìn)制整數(shù)n，則11n 112n 24n 4 48n 8

6、8n 例如，判斷n981234576能否被11、2、4、8、16整除。因?yàn)椋?+5+3+1+9）（7+4+2+8）3，故n不能被11整除因26，故2n476或42×7+622，故4n84×5+2×7+640，故8n因8×4+4×5+10×7+60 mod 16，故16n應(yīng)用： 求值ab （mod m）（a （mod m）（b（mod m）（mod m）ab （mod m）（a （mod m）（b（mod m）（mod m）na（mod m）n(a （mod m）) （mod m）（mod m）（mod m）【性質(zhì)5】（定理8）消去律：

7、設(shè)adbd （mod m）。若（d，m）1，則ab （mod m）。（證）adbd（mod m） mad bd(ab)d而（d，m）1，故m(ab)，即 ab （mod m）【例】（例11）9525 mod 7，且（5，7）1，故195 mod 7【反例】（補(bǔ)）11525 mod 15，即23×55×5 mod 15，但235 mod 15。因?yàn)椋?，15）51【性質(zhì)6】（定理9）ab （mod m）且k0，則akbk （mod mk）（證）ab （mod m） ma b mk(ab)kakbk akbk （mod mk）【例】（例 12）195 mod 7，k40，所以7

8、620 mod 28【性質(zhì)7】（定理10）ab （mod m）且d(a，b，m)，則 mod （證）d(a，b，m) 存在整數(shù)，使得d， bd，md又ab （mod m）存在整數(shù)k，使得bmk d d dkk mod mod 【例】（例13）19050 mod 70，取d10，則195 mod 7說(shuō)明：性質(zhì)6、7結(jié)合，得設(shè)d(a，b，m)，則ab （mod m） mod 或者：設(shè)k0，則ab （mod m） akbk （mod mk）【性質(zhì)8】（定理11）ab （mod m）且dm，則ab mod d（證）ab （mod m） mab又 dm dab即 ab mod d【例】（例14）1905

9、0 mod 70，取d7，則19050 mod 7【性質(zhì)9】（定理12改）ab mod （i1,2,k）的充分必要條件是ab mod （證）ab mod ab ab ab mod 【例】（例15）19050 mod 7，19050 mod 10 以及7，1070，19050 mod 70【例】（補(bǔ)）19050 mod 28，19050 mod 35以及28，35140,19050 mod 140【推論】（例16）p，q為不同的素?cái)?shù)，則ab （mod p） 且 ab （mod q） ab mod pq （證）因?yàn)?p，qpq【性質(zhì)10】（定理13）ab （mod m），則（a，m）（b，m）（證

10、）ab （mod m）存在k，使得abmkmkb（a，m）（m，b）（§1.3性質(zhì)（8）：abqc，q為整數(shù)，則（a，b）（b，c）【例】（例17）設(shè)m，n，a均為正整數(shù)，若na0，1 （mod m）則存在n的素因數(shù)p，滿足pa0，1 （mod m） （證） 反證法。若存在n的一個(gè)素因數(shù)p，使得pa0 mod m mpa又p是n的因數(shù) pn pana mna， na0 （mod m），與假設(shè)矛盾。（即na0 （mod m）時(shí)，對(duì)n的每個(gè)素因子，都有pa0 （mod m）其次，若對(duì)n的每個(gè)素因數(shù)，都有1 （mod m）， i1,2,t則由性質(zhì)4的一般情形（附：性質(zhì)4一般情形： mod

11、m（i1,2,k），則 mod m）1 （mod m）所以na（mod m）（mod m）1 （mod m）與假設(shè)矛盾。（即na1 （mod m）時(shí)，對(duì)n的每個(gè)素因子p，不一定都滿足pa1 （mod m），但必至少有一個(gè)p，使得pa1 （mod m）因此，結(jié)論成立。2.2 剩余類及完全剩余系(一) 剩余類和完全剩余系設(shè)m為正整數(shù)，記非空，至少a【定理2.2.1】（定理1）設(shè)m是一個(gè)正整數(shù)，則（i） 任一整數(shù)必包含在某個(gè)中，0rm1（ii） ab （mod m）（iii） ab （mod m）（證）利用歐幾里德除法和同余的等價(jià)性【定義2.2.1】（定義1）叫做模m的a的剩余類。一個(gè)剩余類中的任一

12、個(gè)數(shù)叫做該類的剩余或代表。若是m個(gè)整數(shù)，且其中任何兩個(gè)都不在同一個(gè)剩余類中，則稱為模m的一個(gè)完全剩余系?！咀ⅰ棵總€(gè)剩余類中都包含了無(wú)窮多個(gè)整數(shù)，而完全剩余系則恰好由m個(gè)數(shù)組成。模m的剩余類共有m個(gè)，例如【例1】（例1）設(shè)m10，則是模m10的剩余類。模10的剩余系舉例：（1）0，1，2，9（2）1，2，3，10（3）0，1，2，9（4）0，3，6，9，27（5）10，11，22，33，44，99（6）20，1，18，13，64，55，94，3，18，9(二) 性質(zhì)【定理2.2.2】（定理2）整數(shù)為m的一個(gè)完全剩余系mod m。（證）由定理2.2.1的（ii）（iii）即得結(jié)論?！纠?】（例2）

13、m的典型完全剩余系：(i) 最小非負(fù)完全剩余系：0，1，m1(ii) 最小正完全剩余系：1，2，m(iii) 最大非正完全剩余系：0，1，(m1)(iv) 最大負(fù)完全剩余系：1，2，m(v) 絕對(duì)（值）最小完全剩余系m為偶數(shù)：m2，(m2)2，(m2)2或： (m2)2，(m2)2，m2，m為奇數(shù)：(m1)2，(m3)2，(m1)2【定理2.2.3】（定理3）設(shè)a是滿足(a，m)1的整數(shù)，b為任意整數(shù)。若x遍歷模m的一個(gè)完全剩余系，則axb遍歷模m的一個(gè)完全剩余系。（證）設(shè)為m的一個(gè)完全剩余系。由定理2.2.2知，（mod m） （0ijm1）又(a，m)1，故 （mod m）從而 （mod

14、m）由定理2.2.2，是模m的一個(gè)完全剩余系?！纠?】（例3）設(shè)m10，原剩余系為0，1，9。當(dāng)a7，b5時(shí)，新的剩余系為：5，12，17，68 當(dāng)a3，b6時(shí)，新的剩余系為：6，9，12，33【定理2.2.4】（定理4）設(shè)是兩個(gè)互素的正整數(shù)，若分別遍歷的完全剩余系，則遍歷模的完全剩余系。（證）當(dāng)分別遍歷個(gè)整數(shù)時(shí)，則遍歷模個(gè)整數(shù)。問(wèn)題轉(zhuǎn)化為：證明個(gè)整數(shù)模兩兩不同余。用反證法：若存在和滿足 mod 則由2.1節(jié)性質(zhì)8或性質(zhì)9知 mod 即 mod 而（m1,m2）1，故由同余的性質(zhì)知 mod 同理可證， mod ?！纠?】（例4）設(shè)p、q是兩個(gè)不同的素?cái)?shù)，npq，則對(duì)任意整數(shù)c，存在唯一的一對(duì)數(shù)

15、x和y，滿足xpyc （mod n）， 0xp，0yq（證）首先知p、q互素。再由定理2.2.4，當(dāng)x、y分別遍歷模p、q的完全剩余系時(shí)，qxpy遍歷模npq的完全剩余系。故存在唯一的一對(duì)整數(shù)x、y，滿足上式。2.3 簡(jiǎn)化剩余系與歐拉函數(shù)(一) 歐拉函數(shù)（1） 定義【定義2.3.1】（定義1）設(shè)n為正整數(shù)，則1,2,n中與n互素的整數(shù)的個(gè)數(shù)，記作(n)，叫做歐拉（Euler）函數(shù)?！纠?】（例1）設(shè)n10，則1,2,10中與10互素的數(shù)為 1,2,7,9，故(10)4【例】（補(bǔ)）(1)1，(2)1，(3)2，(4)2，(6)2，即1,2,6中與6互素的數(shù)為1，5(20)8，即1,2,20中與2

16、0互素的數(shù)為1,3,7,9,11,13,17,19（2） 性質(zhì)【性質(zhì)1】（補(bǔ)）設(shè)p為素?cái)?shù)，則(p)p1。 （證）由定義，顯然。【性質(zhì)2】（補(bǔ)）設(shè)p為素?cái)?shù)，且整數(shù)1，則()（證）1,2,中與p 不互素的數(shù)共有個(gè)，這些數(shù)是p，2p，3p，4p，由此即得結(jié)論?！拘再|(zhì)3】（推論）設(shè)整數(shù)npq，其中p，q為不同的素?cái)?shù)，則(n)(pq)(p)(q)(p1)(q1)（證）設(shè)整數(shù)a滿足1an，若(a，n)d1，則必有sp或dtq （因?yàn)閚的因數(shù)只有1，p，q，pqn）即必有 pd或qd，從而有pa或qa這說(shuō)明與n不互素的數(shù)a必為asp或atq.這樣的 a為p，2p，3p，4p，(q1)p，qp和q，2q，3q

17、，4q，(p1)q，pq共有pq1個(gè) (n)(pq)pq(pq1)(p1)(q1) (p)(q)【例】（補(bǔ)）(143)(11·13)(11)(13)10·12120 【性質(zhì)4】（補(bǔ)）設(shè)整數(shù)n，其中p，q為不同的素?cái)?shù)，則(n)()()()（證）在1n中與n不互素的數(shù)必為sp或tq形式的數(shù)，即能被p或q整除的數(shù)：p，2p，3p，4p，(1)p，pn（有個(gè)）和q，2q，3q，4q，(1)q，qn（有個(gè)）其中能同時(shí)被p和q整除的數(shù)有q，2pq，3pq，n （有個(gè)） (n)n【推論】（補(bǔ)）設(shè)整數(shù)n有標(biāo)準(zhǔn)分解式，則(n)（證）用歸納法?！纠?100)(22·52)10040

18、(360)(23·32·5)36096【性質(zhì)5】（定理6）歐拉函數(shù)是乘性函數(shù)（或稱積性函數(shù)）。即若正整數(shù)m，n互素，則(mn)(m)(n)。（證）記m、n的標(biāo)準(zhǔn)分解式分別為，n則(mn)(m)(n)【例】（補(bǔ)）設(shè)m33，n32，求(33·32)。（解）(33，32)1，故(33·32)(33)(32) 33·32160【例】（補(bǔ)）歐拉函數(shù)不是完全積性函數(shù)（即對(duì)任何正整數(shù)m，n，都有(mn)(m)(n)）。反例：設(shè)m36，n16，則(36)12，(16)8，(36)(16)96但 (36·16)(576)(25·32)5761

19、92又設(shè)m12，n20，則(12)4，(20)8，(12)(20)32但 (12·20) (240)(24·3·5)24064【例13】（例13）設(shè)npq，p,q均為素?cái)?shù)，則可由n和(n)得到p,q（解）由npq和(n)npq1即得關(guān)于p、q的方程組由韋達(dá)定理知，p、q是方程0的兩個(gè)根?！拘再|(zhì)6】設(shè)(m，n)d，則(mn)(m)(n)（證）設(shè)n，由(n)知 【例】設(shè)m220·5·11，n2102·3·5·7，則mn220·21046200·3··7·11，(220,

20、 210)10而 所以兩邊同乘以46240得(46240) (220) (210) 【例】設(shè)m36，n16，則 (36，16)4(36)12，(16)8，(4)2故(36·16)(36)(16)·4(4)12·8·42192【例】求(20 000)。（解）20 000100·200，且(100，200)100(100)40，(200)80故 (20 000)(100)(200)·100(100)100(200)100·808 000【推論】若ab，則(ab)a(b)。因?yàn)閍b，故(a,b)a，從而由性質(zhì)知(ab)(a)(b)

21、a(b)【性質(zhì)7】若ab，則(a)(b)。（證）設(shè)a，b（將兩者相同的素因子排在前面），則1（i1,2,k）且kt，并有(a)a(b)b從而 整數(shù)【性質(zhì)8】（定理8）設(shè)n為正整數(shù)，則n或n（證）對(duì)n個(gè)數(shù)C1，2，n按照與n的最大公因數(shù)分類，記 x1xn，(x, n)d， dn即（在1n之間與n的最大公因子都是d的數(shù)構(gòu)成的C的子集） xdk1k，(k, )1 中元素個(gè)數(shù)又因?yàn)镃中每個(gè)整數(shù)恰好只屬于一個(gè)類，所以，構(gòu)成集合C的一個(gè)劃分，即C從而 或 而當(dāng)d遍歷n的所有正因數(shù)時(shí)，nd也遍歷n的所有正因數(shù)。即【例14】（例14）設(shè)n50，求。（解）d1，2，5，10，25，501,3,7,9,，47,4

22、9，202,4,6,8,12,14,46,48，205,15,35,45，410,20,30,40，4 25 ，1 50 ，1 +1+1+4+4+20+205050(二) 簡(jiǎn)化剩余系【定義2.3.2】（定義2）一個(gè)模m的剩余類叫做簡(jiǎn)化剩余類（或互素剩余類、既約剩余類、不可約剩余類），如果該類中存在一個(gè)與m互素的剩余。注：本定義與剩余的選取無(wú)關(guān)。【例】m=20，=【定理2.3.1】（定理1）設(shè)、是同一剩余類中的兩個(gè)剩余，則與m互素的充分必要條件是與m互素。（證）由題設(shè)知 km再由最大公因子性質(zhì)知（，m）（，m） （，m）1 （，m）1【定義2.3.3】（定義3）設(shè)m為正整數(shù)，在模m的所有不同簡(jiǎn)化

23、剩余類中，從每個(gè)類任取一個(gè)數(shù)組成的整數(shù)集合，叫做模m的一個(gè)簡(jiǎn)化剩余系（或稱為縮系、互素剩余系、既約剩余系、不可約剩余系）?！纠浚ㄑa(bǔ)）模6的簡(jiǎn)化剩余系為1，5 模20的簡(jiǎn)化剩余系為1,3,7,9,11,13,17,19【定理】（補(bǔ)）m的簡(jiǎn)化剩余系的元素個(gè)數(shù)為。（證）顯然?！纠?】（例2）模m的典型簡(jiǎn)化剩余系：(i) 最小非負(fù)簡(jiǎn)化剩余系：0，1，m1中與m互素的所有整數(shù)(ii) 最小正簡(jiǎn)化剩余系：1，2，m中與m互素的所有整數(shù)(iii) 最大非正簡(jiǎn)化剩余系：0，1，(m1) 中與m互素的所有整數(shù)(iv) 最大負(fù)簡(jiǎn)化剩余系：1，2，m中與m互素的所有整數(shù)(v) 絕對(duì)（值）最小簡(jiǎn)化剩余系m為偶數(shù)時(shí)指

24、m2，(m2)2，(m2)2或： (m2)2，(m2)2，m2中與m互素的所有整數(shù)m為奇數(shù)時(shí)指(m1)2，(m3)2，(m1)2中與m互素的所有整數(shù)【例】（補(bǔ)）模14的典型簡(jiǎn)化剩余系為（6）： (i) 最小非負(fù)簡(jiǎn)化剩余系：1，3，5，9，11，13 (ii) 最小正簡(jiǎn)化剩余系：1，3，5，9，11，13(iii) 最大非正簡(jiǎn)化剩余系：1,3,5,9,11,13(iv) 最大負(fù)簡(jiǎn)化剩余系：1，3，5，9，11，13(v) 絕對(duì)（值）最小簡(jiǎn)化剩余系：5，3,1，1，3，5模15的典型簡(jiǎn)化剩余系為（8）：(i) 最小非負(fù)簡(jiǎn)化剩余系：1，2，4，7，8，11，13，14 (ii) 最小正簡(jiǎn)化剩余系：1

25、，2，4，7，8，11，13，14(iii) 最大非正簡(jiǎn)化剩余系：1,2,4,7,8,11，13，14(iv) 最大負(fù)簡(jiǎn)化剩余系：1,2,4,7,8,11，13，14(v) 絕對(duì)（值）最小簡(jiǎn)化剩余系：7，4,2，1，1，2，4，7【例6】（例6）素?cái)?shù)p的簡(jiǎn)化剩余系為 1，2，p1，即p1【定理】（定理2）設(shè)整數(shù)，均與m互素，且兩兩模m不同余，則它們構(gòu)成模m的一個(gè)簡(jiǎn)化剩余系。（證）由題意知，是來(lái)自模m的不同簡(jiǎn)化剩余類的剩余，故是m的一個(gè)簡(jiǎn)化剩余系。【定理】（補(bǔ)）設(shè)整數(shù)，均與m互素，若它們構(gòu)成模m的一個(gè)簡(jiǎn)化剩余系，則這些必兩兩模m不同余。（證）由題意知，是來(lái)自模m的不同簡(jiǎn)化剩余類的剩余，而不同剩余

26、類中的數(shù)必互不同余?！就普摗浚ㄑa(bǔ)）設(shè)整數(shù)，均與m互素，則它們構(gòu)成模m的簡(jiǎn)化剩余系的充分必要條件是這些兩兩模m不同余?！径ɡ怼浚ǘɡ?）設(shè)m為正整數(shù)，a是滿足(a，m)1的整數(shù)。那么，若x遍歷模m的一個(gè)簡(jiǎn)化剩余系，則ax也遍歷模m的一個(gè)簡(jiǎn)化剩余系。（證）首先，由(a，m)1及(x，m)1知(ax，m)1，即ax是簡(jiǎn)化剩余類的剩余。其次，若（mod m），則必有（mod m）（否則，由（mod m）及(a，m)1可得（mod m），矛盾）因此x遍歷模m的一個(gè)簡(jiǎn)化剩余系時(shí)，ax遍歷個(gè)數(shù)，且它們兩兩m不同余。由定理知ax也遍歷模m的一個(gè)簡(jiǎn)化剩余系?！纠?】（例7）已知1，7，11，13，17，19，2

27、3，29是模30的簡(jiǎn)化剩余系，(7，30)1，則7，19，17，1，29，13，11，23也是模30的簡(jiǎn)化剩余系?！纠?】設(shè)m7，a1，2，3，4，5，6，則ax為：x 123456112345622461353362514441526355316426654321【定理】（補(bǔ)）當(dāng)x遍歷m的簡(jiǎn)化剩余系時(shí)，x±km也遍歷m的簡(jiǎn)化剩余系。（證）首先，由(x，m)1知(x±km，m)1，即二者互素。其次，當(dāng) mod m，必有 ±km±km（mod m）【推論】（補(bǔ)）設(shè)m為正整數(shù)，a是滿足(a，m)1的整數(shù)，則當(dāng)x遍歷m的簡(jiǎn)化剩余系時(shí)，m±ax也遍歷m

28、的簡(jiǎn)化剩余系?！径ɡ怼浚ǘɡ?）設(shè)m為正整數(shù)，a是滿足(a，m)1的整數(shù)。則存在整數(shù)（1m）使得a1 （mod m）（證）（構(gòu)造性證明）由(a，m)1知存在整數(shù)s，t，使得satm(a，m)1即sa1(t)m因此，所求s?！纠?0】（例10）設(shè)m737，a635，求，滿足aa1 （mod m）（解）利用廣義歐幾里得除法，可找到s224，t193，使得(224) ·635193·7371 a224513 mod 737即 635·(224) 1 mod 737【定理】（定理5）設(shè)，是兩個(gè)互素的正整數(shù)，若分別遍歷模，的簡(jiǎn)化剩余系，則遍歷模的簡(jiǎn)化剩余系。（證）先證屬于模

29、的某個(gè)簡(jiǎn)化剩余類，即證（，）1事實(shí)上，由（，）1及（，）1和（，）1知（，）（，）（，）1（，）（，）（，）1 （，）1其次，證明：當(dāng) mod ， mod 時(shí)，有 mod 事實(shí)上，完全剩余系包含簡(jiǎn)化剩余系，故完全剩余系的性質(zhì)適用于簡(jiǎn)化剩余系。【應(yīng)用】利用小的數(shù)的簡(jiǎn)化剩余系構(gòu)造大的數(shù)的簡(jiǎn)化剩余系?！纠浚ㄑa(bǔ)）設(shè)m777·11，利用7和11的簡(jiǎn)化剩余系構(gòu)造77的簡(jiǎn)化剩余系。（解）取7的最小正簡(jiǎn)化剩余系為 x1，2，3，4，5，6 取11的最小正簡(jiǎn)化剩余系 y1，2，3，10則77的一個(gè)簡(jiǎn)化剩余系為11x7y即 18，25，32，39，46，53，60，67，74，81（x1）29，36，

30、43，50，57，64，71，78，85，92（x2）40，47，54，61，68，75，82，89，96，103（x3）51，58，65，72，79，86，93，100，107，114（x4）62，69，76，83，90，97，104，111，118，125（x5）73，80，87，94，101，108，115，122，129，136（x6）或簡(jiǎn)化剩余系為（取最小非負(fù)簡(jiǎn)化剩余系）11x7y mod 7718，25，32，39，46，53，60，67，74， 4 （x1）29，36，43，50，57，64，71， 1， 8，15 （x2）40，47，54，61，68，75， 5，12，19，2

31、6 （x3）51，58，65，72， 2， 9，16，23，30，37 （x4）62，69，76， 6，13，20，27，34，41，48 （x5）73， 3，10，17，24，31，38，45，52，63 （x6）即 1， 2， 3， 4， 5， 6， 8， 9，10，12，13，15，16，17，18，19，20，23，24，25，26，27，29，30，31，32，34，36，37，38，39，40，41，43，45，46，47，48，50，51，52，53，54，57，58，59，60，61，62，64，65，67，68，69，71，72，73，74，75，76若選絕對(duì)值最小簡(jiǎn)化剩余系

32、，則為-38，-37，-36，-34，-32，-31，-30，-29，-27，-26，-25，-24，-23，-20，-19，-18，-17，-16，-15，-13，-12，-10，-9，-8，-6，-5，-4，-3，-2，-1，1， 2， 3， 4， 5， 6， 8， 9， 10， 12，13， 15， 16， 17， 18， 19， 20，23，24， 25，26， 27， 29， 30， 31， 32， 34，36，37， 38即±1， ±2， ±3， ±4， ±5， ±6， ±8， ±9，±10，

33、±12，±13，±15，±16，±17，±18，±19，±20，±23，±24，±25，±26，±27，±29，±30，±31，±32，±34，±36，±37，±38(三) 整數(shù)a模p的逆（1） 定義【定義】將定理中滿足條件的叫作a（對(duì)模m）的逆，記為。即 a1 mod m實(shí)質(zhì)上，a與互為逆元素?！纠繉?duì)任何模數(shù)m1而言，至少有兩個(gè)數(shù)有逆。即1， m1（mod m）（或1）（2） 性質(zhì)【

34、性質(zhì)1】若a可逆，則（a，m）=1。（證）a可逆，則a的逆存在，且滿足a1 （mod m）即存在整數(shù)k，使得a=1km=km1再由最大公因子的性質(zhì)知（a，m）=（m，1）=1而 （a，m）=1 （a，m）=1且（，m）=1【推論】a是模m的逆的充分必要條件是（a，m）=1?！拘再|(zhì)2】不唯一。即若存在，則km都是a的逆，其中k為任意整數(shù)。（證）只需直接驗(yàn)證：已知是a的逆，即a1 （mod m）那么，對(duì)任意整數(shù)k，有a(km) a akma01 （mod m）【例】設(shè)m7，a2，直接計(jì)算有，2·(3)1 mod 7，2·41 mod 7，2·111 mod 7，2&#

35、183;181 mod 7，即對(duì)模7而言，整數(shù)47k都是2的逆（kz）【性質(zhì)3】若b和c都是a的逆，則有bc （mod m）。（證）已知ab1 （mod m）， ac1 （mod m） 從而 abac （mod m）而(a,m)1，故由消去律知 bc （mod m）?！就普?】設(shè)整數(shù)a有逆，則整數(shù)b是a的逆的充分必要條件是b（mod m）。即b+km（kz）。（證）只要驗(yàn)證當(dāng)b（mod m）時(shí)，b也是a的逆即可。顯然?！纠吭O(shè)m50，3模50的逆為17，那么，只要b17 mod 50。如b，33，67，都是3的逆。反之，2017 mod 50，則20不是3的逆?！就普?】在模m的一個(gè)簡(jiǎn)化剩余系

36、中，a的逆是唯一的?！纠吭O(shè)m7，選模7的最小正簡(jiǎn)化剩余系1，2，6，則a2的逆4且唯一?！拘再|(zhì)4】（1）a。（2）（證）直接驗(yàn)證即可?！就普摗??！纠吭O(shè)m55，求8和24模55的逆。（解）首先可以觀察出2模55的逆為 28所以 7 mod 55·3739（3） 計(jì)算的方法【方法1】利用簡(jiǎn)化剩余類的性質(zhì)枚舉求逆例 m11，a5，則5·15， 5·210， 5·34， 5·53，5·68， 5·91 9 mod 11【方法2】利用輾轉(zhuǎn)相除法（即定理的結(jié)論）【方法3】利用有關(guān)性質(zhì)（求大的數(shù)的逆）【方法4】利用歐拉函數(shù)和歐拉定理的

37、結(jié)論（見(jiàn)后）2.4 歐拉定理 費(fèi)馬小定理(一) 歐拉定理【定理2.4.1】（Euler定理）（定理1）設(shè)m是大于1的整數(shù)，若整數(shù)a滿足(a，m)1，則有1 （mod m）（證）設(shè)為m的最小正簡(jiǎn)化剩余系，則當(dāng)(a，m)1時(shí)，也為模m的一個(gè)簡(jiǎn)化剩余系。故是模m的最小正剩余的某個(gè)排列。所以（mod m）即（mod m）又由(，m)1知，(，m)1，故有1 （mod m）【例1】（例1）設(shè)m7，a2，則(2，7)1 ，(7)6模7的最小正簡(jiǎn)化剩余系為：1，2，3，4，5，6，則2·12，2·24，2·36，2·41，2·53，2·65 mod

38、 7各等式兩邊相乘，有 mod 7即 mod 7而（，7）1，所以結(jié)論成立?！纠?】（例3）設(shè)m11，a2，則(2，7)1 ，(11)10，故1 mod 11【例4】（例4）設(shè)m23，23a，則(a，23)1 ，(23)22，故1 mod 23（歐拉定理的）另一表示形式：設(shè)m是大于1的整數(shù)，若整數(shù)a滿足(a，m)1，則有a （mod m）(二) 費(fèi)馬定理【定理2.4.2】（Fermat定理）（定理2）設(shè)p為素?cái)?shù)，a為任意正整數(shù)，則a（mod p）（證）(1) ，則有0 （mod p）0 （mod p）即 a （mod p）(2) pa，必有(a,p)1，由定理2.4.11 （mod p）兩邊同

39、乘以a，得 a （mod p）【例】設(shè)p11，a2，則(11)10，故2 mod 11設(shè)p23，a10，則(23)22，故10 mod 23【推論】設(shè)m1，則m為素?cái)?shù)的必要條件是：對(duì)某個(gè)ma的整數(shù)a，有1 （mod m）應(yīng)用：用于否定一個(gè)整數(shù)為素?cái)?shù)。意義：是判斷一個(gè)正整數(shù)為素?cái)?shù)的概率算法的理論基礎(chǔ)。【例】設(shè)m20，a2，則 2·48 mod 20又 3 mod 30 20和30都是合數(shù)。又 1 mod 15，既不能肯定15是素?cái)?shù)，也不能肯定15是合數(shù)。一般情況下要進(jìn)行多次判斷，例如：4 mod 15，所以15是合數(shù)?！纠?】（例5）設(shè)p、q是兩個(gè)不同的奇素?cái)?shù)，npq，a是與n互素的整

40、數(shù)。令整數(shù)e滿足1e(n)且(e，(n)1，存在正整數(shù)d，使得d1 mod (n)， 1d(n)而且，對(duì)于整數(shù)c（mod n）（1cn），有a （mod n）（證）因(e，(n)1 ，故e的逆d存在，滿足d1 mod (n)即存在正整數(shù)k，使ed1k(n)由定理知 1 （mod p），所以aa （mod p）同理可得 a （mod q）從而 a （mod n）即 a （mod n）【例6】（補(bǔ)）設(shè)p、q是兩個(gè)不同的奇素?cái)?shù)，npq，且設(shè)整數(shù)e、d滿足d1 mod (n)， 1d(n)那么，對(duì)于整數(shù)c（mod n）（1cn），有a（modn）。其中為任意整數(shù)。（證）設(shè)(a，n)d若d1，由例5知結(jié)

41、論成立。若dn，則na，即 a0（mod n），從而c0（mod n）0a（modn）若1dn ，不失一般性，設(shè)1an ，則必有akp（1kq）或akq（1kp）設(shè)akq，此時(shí)必有（a，p）1，那么有aa（mod p）和0a（mod q）所以a （mod n）即a （mod n）同理可證當(dāng)akp時(shí)的情況。(三) 求的方法方法四、由Euler定理知（mod m）而當(dāng)mp為素?cái)?shù)時(shí)，（mod m）(四) 威爾遜（Wilson）定理判斷素?cái)?shù)的方法之一【定理2.4.3】（Wilson定理）（定理3+補(bǔ)）p為素?cái)?shù)(p1)!1 （mod p）（證）必要性：當(dāng)p2時(shí)，顯然成立（即1！1 mod 2）。設(shè)p3，

42、由于1ap1時(shí)，(a，p)1，故a的逆（mod p）存在且1,2,p1中任一數(shù)的逆恰好也在中1,2,p1中。又 a （mod p）1 （mod p）即a1或 a11 （mod p）時(shí)其逆為本身。所以，(p2)這p3個(gè)數(shù)兩兩互相為逆。那么，·(p2)(p1)1·(p1) 1 （mod p）充分性：用反證法。已知 (p1)!1 （mod p），由同余性質(zhì)知 (p1)! (1) (p1)!1c1 （*）若pab為合數(shù)，則p，從而由上式知 c1又 1ap（且1bp），那么，必有 (p1)!c (c1)c1 矛盾。故p為素?cái)?shù)?！纠吭O(shè)p7，則 2·41，3·51

43、（mod 7）即4，5，2，3（mod 7）以及1，6（mod 7），從而有 ···6(2·4)(3·5)661 mod 7又設(shè)p11，則2·61， 3·41， 5·91， 7·81（mod 11） ···10(2·6)(3·4)(5·9)(7·8)6101（mod 7）2.5 模重復(fù)平方計(jì)算法目的：快速計(jì)算a（mod m） （1）(一) 問(wèn)題常規(guī)思路，遞歸地計(jì)算（1）式：（mod m）運(yùn)算量：n1次乘法。(二) 模重復(fù)平方計(jì)算法原理表

44、n為二進(jìn)制n，即n其中 0，1，i0,1,k。則（mod m）運(yùn)算量：乘法次數(shù)(1+2+ k)+k（計(jì)算最多需要i次乘法）。最少運(yùn)算量：乘法次數(shù)k+k2k（利用計(jì)算）(三) 模重復(fù)平方計(jì)算法（0） 令a1，表n為二進(jìn)制n（1） 如果1，計(jì)算 ab （mod m），否則，令 a計(jì)算 （mod m）（2） 如果1，計(jì)算 （mod m），否則，令 計(jì)算 （mod m）（k ）如果1，計(jì)算 （mod m），否則，令 計(jì)算 （mod m）（k1）如果1，計(jì)算 （mod m），否則，令 最后，a（mod m）特點(diǎn)：由n的低位到高位計(jì)算(四) 方法二思路借鑒多項(xiàng)式求值的秦九韶算法：計(jì)算多項(xiàng)式P(x)的值。常

45、規(guī)計(jì)算的乘法運(yùn)算量為L(zhǎng)n(n1)21n(n1)2快速算法：P(x)運(yùn)算量：n次乘法，n次加法。例如，P(x)計(jì)算 P(5)特殊多項(xiàng)式：系數(shù)0，1P(x)計(jì)算特殊值：P(2)23思路：運(yùn)算變換加法乘法， 乘法乘方例(五) 理論基礎(chǔ)r(ab) （mod m）(a （mod m）)(b （mod m）) （mod m）基本乘方：b×b， 用1次乘法×， 用2次乘法×， 用3次乘法，×， 用k次乘法一般乘方：××b， 用4次乘法××， 用6次乘法 用17次乘法更一般情形：為計(jì)算，表n為二進(jìn)制n，則n從而 所以 （mod n

46、）(六) 算法：求表n為二進(jìn)制nx0；y1;for k downto 0 do x2*x;yy*y（mod m）;if 1 then x; yy*b; return y特點(diǎn)：由n的高位到低位計(jì)算【例1】計(jì)算 mod 561（3×11×17），計(jì)算過(guò)程各變量的值如下表i98765432101000110000x1248173570140280560y749157526160241298166671又如n77i65432101001101x1249193877y749157526559196268【例2】 （2次平方，1次乘法）， （3次平方，2次乘法），（從n的二進(jìn)制分解角度

47、，63211次平方，3次乘法）（從算法角度，6次平方，3次乘法）， （實(shí)質(zhì)結(jié)果，不算0的情形且嵌套起來(lái)。即計(jì)算a的64次方項(xiàng)時(shí)利用好a的2、4、8、16、32次方項(xiàng)） （6次平方，2次乘法）， （從算法角度，9次平方，2次乘法） （實(shí)質(zhì)結(jié)果，即不算0的情形且嵌套起來(lái)）2.6 一次不定方程2. 6. 1 二元一次（不定）方程(一) 二元一次（不定）方程的整數(shù)解【定義2.6.1】二元一次（不定）方程是指n （1）其中、n是給定的整數(shù)（0），x,y是變數(shù)（或變量）【例】二元一次（不定）方程5x+8y24直觀求解：窮舉并利用整除性原方程變形5x24-8y，即x(24-8y)/5令y=0，±2

48、，±3，計(jì)算得解(x,y)=， (8,-2)，(0,3)，(-8,8)，(-16,13)，(二) 有解的條件【定理2.6.1】二元一次（不定）方程（1）有解的充分必要條件為(,)n （2）（證）必要性：設(shè)，由整除的性質(zhì)知，對(duì)任何整數(shù)x，y，都有d。已知方程（1）n有解，故dn。充分性：由d=(,)知，存在整數(shù)s,t，使得d而已知 dn，上式兩邊同時(shí)乘以得d即 n亦即方程（1）有解 x=s，y=t。(三) (,)1時(shí)的解首先由有解的條件知，此時(shí)方程（1）一定有解。【定理】設(shè)(,)1，則（1）的全部解可表示為。+t，t t0,±1,±2, （3）其中，為方程（1）的一組（特）解，t為任意整數(shù)。（證）已知和滿足方程（1）n，將（3）式中的x、y直接代入方程中得(+t)+(t)=+=n說(shuō)明：根據(jù)x和y的對(duì)稱性，方程（1）的解也可以表為t，+t t0,±1,±2, （3）(四) (,)>1時(shí)的解【定理2.6.3】設(shè)(,)d>1，則（1）的解與不定方程 （4）的解相同。（證）因?yàn)榈仁剑?）成立的充分必要條件是等式（4）成立?！径ɡ?.6.4】設(shè)(,)d>1，若方程（1）有解，且其一組特解為，則它的所有解為 t0,±1,±2, （4）（證）由定理2.6.2和2.6.3即得。【注】當(dāng)(,)