初等數(shù)論定義、基本定理和應(yīng)用

1、初等數(shù)論定義、基本定理和應(yīng)用 以整數(shù)集為典型代數(shù)系統(tǒng)的數(shù)論知識(shí)一直被認(rèn)為是既神秘又古老。雖然絕大多數(shù)人自小學(xué)生起就開(kāi)始認(rèn)識(shí)它，而一些數(shù)學(xué)家卻一輩子踏著它往皇冠上攀?，F(xiàn)在，計(jì)算機(jī)終于給數(shù)論這門再純潔不過(guò)的數(shù)學(xué)分支揚(yáng)起了應(yīng)用的帆。我們這里介紹的雖然只是初等數(shù)論的基礎(chǔ)知識(shí)，但它們?cè)谟?jì)算機(jī)的數(shù)據(jù)表示、數(shù)據(jù)傳輸以及電子商務(wù)應(yīng)用中的數(shù)據(jù)保密等方面起著非常重要的作用。 第19章 初等數(shù)論 19.1 素?cái)?shù)19.2 最大公約數(shù)與最小公倍數(shù)19.3 同余19.4 一次同余方程19.5 歐拉定理和費(fèi)馬小定理 19.6 初等數(shù)論在計(jì)算機(jī)科學(xué)技術(shù)中的幾個(gè)應(yīng)用19.1 素?cái)?shù) 整除、倍數(shù)和因子帶余除法素?cái)?shù)與合數(shù)算術(shù)基本定理

2、篩法整除、倍數(shù)和因子今后只考慮正整數(shù)的正因子.平凡因子 : 1和自身真因子 : 除1和自身之外的因子例如, 2, 3 是 6 的真因子設(shè)a, b是兩個(gè)整數(shù)，且b0. 如果存在整數(shù)c 使 a=bc，則稱a 被b 整除，或 b 整除a，記作 b|a. 此時(shí), 又稱 a 是b 的倍數(shù)，b是a 的因子. 把 b 不整除 a 記作 b a.例如, 6有8個(gè)因子1, 2, 3和6.整除的性質(zhì)性質(zhì)1 若a |b且a |c, 則 x, y, 有a | xb+yc.性質(zhì)1 若a |b且b |c, 則a |c.性質(zhì)1 設(shè) m0, 則 a |b 當(dāng)且僅當(dāng) ma | mb.性質(zhì)1 若a | b且b | a, 則a=b

3、.性質(zhì)1 若a | b且b0, 則|a|b|. 帶余除法: a=qb+r, 0r 1, p是素?cái)?shù)且d | p, 則d=p.性質(zhì)1設(shè)p是素?cái)?shù)且p | ab, 則必有p | a 或者 p | b. 設(shè)p是素?cái)?shù)且p | a1a2ak, 則必存在1ik, 使得p| ai.性質(zhì)1 a1是合數(shù)當(dāng)且僅當(dāng)a=bc, 其中1ba, 1c1, 則 a= , 其中 p1,p2,pk是不相同的素?cái)?shù), r1,r2,rk是正整數(shù), 并且在不計(jì)順序的情況下, 該表示是惟一的. 該表達(dá)式稱作整數(shù)a的素因子分解. 例如 30=235, 117=3213, 1024=210 推論 設(shè)a= , 其中p1,p2,pk是不相同的素?cái)?shù),

4、 r1,r2,rk是正整數(shù), 則正整數(shù)d為a的因子的充分必要條件是d= , 其中0siri, i=1,2,k.例題例1 21560有多少個(gè)正因子?解 21560=2357211由推論, 21560的正因子的個(gè)數(shù)為4232=48.例2 10!的二進(jìn)制表示中從最低位數(shù)起有多少個(gè)連續(xù)的0?解 2, 3, 4=22, 5, 6=23, 7, 8=23, 9=32, 10=25.得 10!=2834527,故10!的二進(jìn)制表示中從最低位數(shù)起有8個(gè)連續(xù)的0.素?cái)?shù)的分布梅森數(shù)(Marin Mersenne): 2p1, 其中p為素?cái)?shù) 當(dāng)n是合數(shù)時(shí), 2n1一定是合數(shù), 2ab1=(2a1)(2a(b1)+2

5、a(b2)+2a+1).梅森數(shù)可能是素?cái)?shù), 也可能是合數(shù): 221=3, 231=7, 251=31, 271=127都是素?cái)?shù), 而2111=2047=2389是合數(shù).到2002年找到的最大梅森素?cái)?shù)是21, 有4百萬(wàn)位. 定理19.2 有無(wú)窮多個(gè)素?cái)?shù).證 用反證法. 假設(shè)只有有窮多個(gè)素?cái)?shù), 設(shè)為p1,p2,pn,令m=p1p2pn+1. 顯然, pi m, 1in. 因此, 要么m本身是素?cái)?shù)，要么存在大于pn的素?cái)?shù)整除m, 矛盾.素?cái)?shù)的分布(續(xù))(n): 小于等于n的素?cái)?shù)個(gè)數(shù). 例如 (0)=(1)=0, (2)=1, (3)=(4)=2, (5)=3. n 103 104 105 106 1

6、07(n)n/ln n(n)n/ln n 168 1229 9592 78498 664579 145 1086 8686 72382 6204211.159 1.132 1.104 1.085 1.071素?cái)?shù)的分布(續(xù))補(bǔ)充定理 當(dāng)n67時(shí),定理19.3 (素?cái)?shù)定理) 素?cái)?shù)測(cè)試定理19.4 如果a是合數(shù), 則a必有小于等于 的真因子.證 由性質(zhì)19.8, a=bc, 其中1ba, 1c( )2=a, 矛盾.推論 如果a是合數(shù), 則a必有小于等于 的素因子.證 由定理19.4, a有小于等于 的真因子b. 如果b是素?cái)?shù), 則結(jié)論成立. 如果b是合數(shù), 由性質(zhì)19.9和性質(zhì)19.5, b有素因子

7、pb . 根據(jù)性質(zhì)19.2, p也是a 的因子, 結(jié)論也成立.實(shí)例例3 判斷157和161是否是素?cái)?shù).解 , 都小于13, 小于13的素?cái)?shù)有: 2, 3, 5, 7, 11.檢查結(jié)果如下: 2 157, 3 157, 5 157, 7 157, 11 157 結(jié)論: 157是素?cái)?shù). 2 161, 3 161, 5 161, 7|161（161=723）結(jié)論：161是合數(shù).埃拉托斯特尼(Eratosthene)篩法 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 11 12 1

8、3 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

9、16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

10、 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2

11、1 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

12、24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10019.2 最大公約數(shù)與最小公倍數(shù) 公約數(shù)、最大公約數(shù)公倍數(shù)、最小公倍數(shù)輾轉(zhuǎn)相除法互素最大公約數(shù)與最小公倍數(shù)d是a與b的公因子(公約數(shù)):

13、d |a且d |bm是a與b的公倍數(shù): a | m且b | m 設(shè)a和b是兩個(gè)不全為0的整數(shù), 稱a與b的公因子中最大的為a與b的最大公因子, 或最大公約數(shù), 記作gcd(a,b). 設(shè)a和b是兩個(gè)非零整數(shù), 稱a與b最小的正公倍數(shù)為a與b的最小公倍數(shù), 記作lcm(a,b). 例如 gcd(12,18)=6, lcm(12,18)=36. 對(duì)任意的正整數(shù)a, gcd(0,a)=a, gcd(1,a)=1, lcm(1,a)=a. 最大公約數(shù)與最小公倍數(shù)(續(xù))定理1 (1) 若a | m, b | m, 則 lcm(a,b)| m. (2) 若d |a, d |b, 則d | gcd(a,b)

14、.證 (1) 記M=lcm(a,b), 設(shè)m=qM+r, 0rD, 注意到d |a, D|a, 由(1), 得m |a. 同理, m |b. 即, m是a和b的公因子, 與D是a和b的最大公約數(shù)矛盾. 最大公約數(shù)與最小公倍數(shù)(續(xù))例4 求150和220的最大公約數(shù)和最小公倍數(shù).解 150=2352, 168=2337. gcd(150,168)=21315070=6, lcm(150,168)=23315271=4200. 利用整數(shù)的素因子分解, 求最大公約數(shù)和最小公倍數(shù). 設(shè) 其中p1,p2,pk是不同的素?cái)?shù), r1,r2,rk,s1,s2,sk是非負(fù)整數(shù). 則 gcd(a,b)= lcm(

15、a,b)=輾轉(zhuǎn)相除法定理1 設(shè)a=qb+r, 其中a, b, q, r 都是整數(shù), 則 gcd(a,b) = gcd(b,r).證 只需證a與b和b與r有相同的公因子. 設(shè)d是a與b的公因子, 即d |a且d |b. 注意到, r=aqb, 由性質(zhì)11.1.1, 有d |r. 從而, d |b且d |r, 即d也是b與r的公因子. 反之一樣, 設(shè)d是b與r的公因子, 即d |b且d |r. 注意到, a=qb+r, 故有d |a. 從而, d |a且d |b, 即d也是a與b的公因子. 輾轉(zhuǎn)相除法歐幾里得(Euclid)算法設(shè)整數(shù)a, b, 且b0, 求gcd(a,b).做帶余除法 a=qb+

16、r, 0r0, 再對(duì)b和r做帶余除法 b=qr+r, 0r0是a和b的公因子, 有 d |xa+yb, 即 d |1. 從而 d=1, 得證a和b互素. a和b互素: gcd(a,b)=1兩兩互素: 任意兩個(gè)都互素 例如, 8和15互素,而8和12不互素.4, 9, 11, 35兩兩互素.實(shí)例例6 設(shè)a |c, b |c, 且a與b互素, 則ab |c.證 根據(jù)定理11.8, 存在整數(shù)x,y,使xa+yb=1. 兩邊同乘以c,得cxa+cyb=c. 又由a |xa和b |c, 可得ab |cxa. 同理, ab |cyb. 于是, 有ab |cxa+cyb, 即ab|c. 11.3 同余同余模

17、算術(shù)運(yùn)算模m等價(jià)類同余定義19.3 設(shè)m是正整數(shù), a和b是整數(shù). 如果m|ab, 則稱a模m同余于b, 或a與b模m同余, 記作ab(mod m). 如果a與b模m不同余, 則記作a b(mod m).例如, 153(mod 4), 160(mod 4), 14 2(mod 4), 15 16(mod 4). 下述兩條都是a與b模m同余的充分必要條件:(1) a mod m = b mod m.(2) a=b+km, 其中k是整數(shù).同余(續(xù))性質(zhì) 同余關(guān)系是等價(jià)關(guān)系, 即同余關(guān)系具有 自反性. aa(mod m) 傳遞性. ab(mod m)bc(mod m) ac(mod m). 對(duì)稱性.

18、 ab(mod m) ba(mod m). 縮寫 a1a2ak (mod m). 性質(zhì)19.11 (模算術(shù)運(yùn)算) 若ab(mod m), cd(mod m), 則 acbd(mod m), acbd(mod m), akbk(mod m), 其中k是非負(fù)整數(shù). 性質(zhì)1 設(shè)d1, d | m, 則ab(mod m) ab(mod d).性質(zhì)1 設(shè)d1, 則ab(mod m) dadb(mod dm).性質(zhì)1 設(shè)c,m互素, 則ab(mod m) cacb(mod m).模m等價(jià)類模m等價(jià)類: 在模m同余關(guān)系下的等價(jià)類. am, 簡(jiǎn)記作a. Zm: Z在模m同余關(guān)系下的商集在Zm上定義加法和乘法如

19、下: a, b, a+b=a+b, ab=ab. + 0 1 2 30123 0 1 2 30123 例1 寫出Z4的全部元素以及Z4上的加法表和乘法表.解 Z4=0,1,2,3, 其中i=4k+i |kZ, i=0,1,2,3.0 1 2 31 2 3 02 3 0 13 0 1 2 0 0 0 0 0 1 2 3 0 2 0 2 0 3 2 1實(shí)例例2 3455的個(gè)位數(shù)是多少?解 設(shè)3455的個(gè)位數(shù)為x,則3455x(mod10).由341(mod 10), 有 3455=34113+3337(mod 10),故3455的個(gè)位數(shù)是7.例3 日期的星期數(shù) y年m月d日星期數(shù)的計(jì)算公式:其中M

20、=(m3)mod12 +1, Y=y M/11=100C+XY年M月:3月下一年2月, C:Y年的世紀(jì)數(shù))7(mod12/2/)7/(224/4/dmMMMCCXXw+-+實(shí)例例3(續(xù)) 例如, 中華人民共和國(guó)成立日1949年10月1日, C=19, X=49, M=8, d=1,是星期六.中國(guó)人民抗日戰(zhàn)爭(zhēng)勝利日1945年8月15日, C=19, X=45, M=6, d=15,是星期三. 11.4 一次同余方程 一次同余方程模m逆一次同余方程定理1 方程axc(mod m)有解的充要條件是gcd(a,m)|c.證 充分性. 記d=gcd(a,m), a =da1, m =dm1, c =dc

21、1, 其中a1與m1互素. 由定理11.8, 存在x1和y1使得a1x1+m1y1=1. 令x=c1x1, y=c1y1, 得a1x+m1y=c1. 等式兩邊同乘d, 得ax+my=c. 所以, axc(mod m).必要性. 設(shè)x是方程的解, 則存在y使得ax+my=c. 由性質(zhì)11.1.1, 有d | c. 一次同余方程: axc(mod m), 其中m0.一次同余方程的解: 使方程成立的整數(shù)例如, 2x0(mod 4)的解為x0(mod 2), 2x1(mod 4)無(wú)解實(shí)例例1 解一次同余方程 6x3(mod 9).解 gcd(6,9)=3 | 3, 方程有解.取模9等價(jià)類的代表x= 4

22、, 3, 2, 1, 0, 1, 2, 3, 4, 檢查它們是否是方程的解, 計(jì)算結(jié)果如下: 6(4)6(1)623(mod 9), 6(3)60630(mod 9), 6(2)61646(mod 9),得方程的解 x= 4, 1, 2(mod 9), 方程的最小正整數(shù)解是2. 模m逆定理1 (1) a的模m逆存在的充要條件是a與m互素.(2)設(shè)a與m互素, 則在模m下a的模m逆是惟一的.證 (1) 這是定理11.9的直接推論.(2) 設(shè)ab11(mod m), ab21(mod m).得a(b1b2)0(mod m). 由a與m互素, b1b20(mod m),得證b1b2(mod m).

23、定義1 如果ab1(mod m), 則稱b是a的模m逆, 記作a1(mod m)或a1.a1(mod m)是方程ax1(mod m)的解.實(shí)例例2 求5的模7逆.解 5與7互素, 故5的模7逆存在.方法1. 解方程5x1(mod7).檢查x= 3,2,1,0,1,2,3, 得到 513(mod7).方法2. 做輾轉(zhuǎn)相除法, 求得整數(shù)b,k使得 5b+7k=1, 則b是5的模7逆.計(jì)算如下: 7=5+2, 5=22+1.回代 1=522=52(75)= 3527,得 5 13(mod7).實(shí)例例2 (續(xù))方法3. 直接觀察53=15, 15 1(mod 7), 得 513(mod7). 歐拉定理

24、和費(fèi)馬小定理 歐拉函數(shù)歐拉定理費(fèi)馬小定理歐拉(Eular)定理歐拉函數(shù)(n): 0, 1, n1中與n互素的數(shù)的個(gè)數(shù) 例如 (1)= (2)=1, (3)= (4)=2.當(dāng)n為素?cái)?shù)時(shí)(n)=n1; 當(dāng)n為合數(shù)時(shí)(n)n1. 定理19.11(歐拉定理) 設(shè)a與n互素, 則 a(n)1(mod n). 歐拉定理的證明證 設(shè)r1, r2, r(n)是0, 1, n1中與n互素的(n)個(gè)數(shù). 由于a與n互素, 對(duì)每一個(gè)1i (n), ari也與n互素, 故存在1(i) (n) 使得 arir(i)(mod n). 是1,2, (n)上的映射. 要證 是一個(gè)單射.a的模n逆a1存在, a1也與n互素.

25、假設(shè)ij, (i)= (j), 則有ariarj(mod n). 兩邊同乘a1, 得rirj(mod n), 矛盾. 得證 是1, 2,(n)上的單射, 當(dāng)然也是1, 2, (n)上的雙射. 從而,有而 與n互素, 故a(n)1(mod n). 費(fèi)馬(Fermat)小定理定理19.12(費(fèi)馬小定理) 設(shè)p是素?cái)?shù), a與p互素, 則 ap-11(mod p).另一種形式是, 設(shè)p是素?cái)?shù), 則對(duì)任意的整數(shù)a, apa(mod p). 費(fèi)馬小定理提供了一種不用因子分解就能斷定一個(gè)數(shù)是合數(shù)的新途徑. 例如, 2914 (mod 9), 可以斷定9是合數(shù). 19.6 初等數(shù)論在計(jì)算機(jī)科學(xué)技術(shù)中的幾個(gè)應(yīng)用

26、19.6.1 產(chǎn)生均勻偽隨機(jī)數(shù)的方法隨機(jī)數(shù)與偽隨機(jī)數(shù)線性同余法與乘同余法線性同余法隨機(jī)數(shù):隨機(jī)變量的觀察值偽隨機(jī)數(shù)(0,1)上的均勻分布U(0,1): a(0a1), P0Xa=a 線性同余法選擇4個(gè)非負(fù)整數(shù): 模數(shù)m, 乘數(shù)a, 常數(shù)c和種子數(shù)x0, 其中2am, 0cm, 0 x0m, 用遞推公式產(chǎn)生偽隨機(jī)數(shù)序列: xn=(axn1+c) mod m, n=1,2,取 un=xn/m, n=1,2,作為U(0,1)偽隨機(jī)數(shù). 線性同余法(續(xù))線性同余法產(chǎn)生的序列的質(zhì)量取決于m, a和c. 例如m=8, a=3, c=1, x0=2, 得到7,6,3,2,7,6,周期為4 m=8, a=5,

27、 c=1, x0=2, 得到3,0,1,6,7,4,5,2,3,0,1, 周期為8. a=0, 得到c, c, c,a=1, 得到x0+c, x0+2c, x0+3c, 乘同余法: c=0(x00)的線性同余法, 即 xn=axn1 mod m, n=1,2,.最常用的均勻偽隨機(jī)數(shù)發(fā)生器:m=2311, a=75的乘同余法,它的周期是2312.19.6.2 密碼學(xué) 1愷撒密碼明文, 密文, 加密, 解密, 密鑰19.6.2 RSA公鑰密碼私鑰密碼與公鑰密碼密碼學(xué)是研究信息隱藏的科學(xué)，一開(kāi)始主要用于軍事目的，兩次世界大戰(zhàn)期間，都起到了關(guān)鍵的作用?，F(xiàn)在由于計(jì)算機(jī)廣泛應(yīng)用于商業(yè)目的，信息安全是電子商

28、務(wù)的關(guān)鍵核心，而密碼學(xué)是信息和網(wǎng)絡(luò)安全的核心。同余理論可以用于非常簡(jiǎn)單的信息保密目的。比如一個(gè)英文字母可以用另一個(gè)英文字母來(lái)代替，如最早的Caesar加密技術(shù)愷撒(Caesar)密碼加密方法: ABCDEFGH I J KLMNOPQRS TUVWXYZ DEFGH I JKLMNO PQRS TUVWXYZ ABC明文: SEE YOU TOMORROW密文: VHH BRX WRPRUURZ 18 4 4 24 14 20 19 14 12 14 17 17 14 22 21 7 7 1 17 23 22 17 15 17 20 20 17 25加密算法 E(i)=(i+k)mod 26, i=0, 1,25,解密算法 D(i)=(ik)mod 26, i=0, 1,25其中密鑰k是一取定的整數(shù), 這里取k=3. 加密算法線性同余加密算法 E(i)=(ai+b)mod 26, i=0, 1,25,其中a與26互素. 維吉利亞(Vigenere)密碼把明文分成若干段, 每一段有n個(gè)數(shù)字, 密鑰k=k1k2kn,加密算法 E(i1i2in)=c1c2cn,其中cj=(ij+kj)mod 26, ij=0,1,25, j=1, 2, n. RSA公鑰密碼 私鑰