1主要內(nèi)容素?cái)?shù)最大公約數(shù)與最小公倍數(shù)同余一次同余方程歐拉定理與費(fèi)馬小定理初等數(shù)論在計(jì)算機(jī)科學(xué)技術(shù)中的幾個(gè)應(yīng)用第六部分初等數(shù)論2第十九章初等數(shù)論主要內(nèi)容素?cái)?shù)最大公約數(shù)與最小公倍數(shù)同余一次同余方程歐拉定理與費(fèi)馬小定理初等數(shù)論在計(jì)算機(jī)科學(xué)技術(shù)中的幾個(gè)應(yīng)用319.1素?cái)?shù)今后只考慮正整數(shù)的正因子.平凡因子

:1和自身真因子

:除1和自身之外的因子例如,2,3是6的真因子設(shè)a,b是兩個(gè)整數(shù)，且b≠0.如果存在整數(shù)c使a=bc，則稱(chēng)a被b整除，或b整除a，記作b|a.此時(shí),又稱(chēng)a是b的倍數(shù)，b是a的因子.把b不整除a記作ba.例如,6有8個(gè)因子±1,±2,±3和±6.4整除的性質(zhì)性質(zhì)19.1

若a|b且a|c,則

x,y,有a|xb+yc.性質(zhì)19.2

若a|b且b|c,則a|c.性質(zhì)19.3

設(shè)m≠0,則a|b當(dāng)且僅當(dāng)ma|mb.性質(zhì)19.4

若a|b且b|a,則a=±b.性質(zhì)19.5

若a|b且b≠0,則|a|≤|b|.帶余除法:a=qb+r,0≤r<|b|,記余數(shù)r=amodb例如,20mod6=2,

13mod4=3,10mod2=0b|a

當(dāng)且僅當(dāng)amodb=05素?cái)?shù)與合數(shù)性質(zhì)19.6

如果d>1,p是素?cái)?shù)且d|p,則d=p.性質(zhì)19.7

設(shè)p是素?cái)?shù)且p|ab,則必有p|a或者p|b.

設(shè)p是素?cái)?shù)且p|a1a2…ak,則必存在1≤i≤k,使得p|ai.

注意:當(dāng)d不是素?cái)?shù)時(shí),d|ab不一定能推出d|a或d|b.性質(zhì)19.8

a>1是合數(shù)當(dāng)且僅當(dāng)a=bc,其中1<b<a,1<c<a.性質(zhì)19.9

合數(shù)必有素?cái)?shù)因子.定義19.1

大于1且只能被1和自身整除的正整數(shù)稱(chēng)為素?cái)?shù)或質(zhì)數(shù).大于1且不是素?cái)?shù)的正整數(shù)稱(chēng)為合數(shù).例如,2,3,5,7,11是素?cái)?shù),4,6,8,9是合數(shù).

6算術(shù)基本定理定理19.1(算術(shù)基本定理)

設(shè)a>1,則

a=,其中p1,p2,…,pk是不相同的素?cái)?shù),r1,r2,…,rk是正整數(shù),并且在不計(jì)順序的情況下,該表示是惟一的.

該表達(dá)式稱(chēng)作整數(shù)a的素因子分解.例如30=2×3×5,117=32×13,1024=210

推論設(shè)a=,其中p1,p2,…,pk是不相同的素?cái)?shù),r1,r2,…,rk是正整數(shù),則正整數(shù)d為a的因子的充分必要條件是d=,其中0≤si≤ri,i=1,2,…,k.7例題例121560有多少個(gè)正因子?解21560=23×5×72×11由推論,21560的正因子的個(gè)數(shù)為4×2×3×2=48.例210!的二進(jìn)制表示中從最低位數(shù)起有多少個(gè)連續(xù)的0?解2,3,4=22,5,6=2×3,7,8=23,9=32,10=2×5.得

10!=28×34×52×7,故10!的二進(jìn)制表示中從最低位數(shù)起有8個(gè)連續(xù)的0.8素?cái)?shù)的分布梅森數(shù)(MarinMersenne):2p

1,其中p為素?cái)?shù)當(dāng)n是合數(shù)時(shí),2n

1一定是合數(shù),2ab

1=(2a

1)(2a(b

1)+2a(b

2)+…+2a+1).梅森數(shù)可能是素?cái)?shù),也可能是合數(shù):22

1=3,23

1=7,25

1=31,27

1=127都是素?cái)?shù),而211

1=2047=23×89是合數(shù).到2002年找到的最大梅森素?cái)?shù)是213466917

1,有4百萬(wàn)位.定理19.2

有無(wú)窮多個(gè)素?cái)?shù).證用反證法.假設(shè)只有有窮多個(gè)素?cái)?shù),設(shè)為p1,p2,…,pn,令m=p1p2…pn+1.顯然,pi

m,1≤i≤n.因此,要么m本身是素?cái)?shù)，要么存在大于pn的素?cái)?shù)整除m,矛盾.9素?cái)?shù)的分布(續(xù))

(n):

小于等于n的素?cái)?shù)個(gè)數(shù).例如

(0)=

(1)=0,

(2)=1,

(3)=

(4)=2,

(5)=3.168122995927849866457914510868686723826204211.1591.1321.1041.0851.071

(n)n/lnn

(n)n/lnn103104105106107n定理19.3(素?cái)?shù)定理)10素?cái)?shù)測(cè)試定理11.4

如果a是合數(shù),則a必有小于等于的真因子.證由性質(zhì)19.8,a=bc,其中1<b<a,1<c<a.顯然,b和c中必有一個(gè)小于等于.否則,bc>()2=a,矛盾.推論如果a是合數(shù),則a必有小于等于的素因子.證由定理,a有小于等于的真因子b.如果b是素?cái)?shù),則結(jié)論成立.如果b是合數(shù),由性質(zhì)19.9和性質(zhì)19.5,b有素因子p<b≤.根據(jù)性質(zhì)11.2,p也是a的因子,結(jié)論也成立.11例3

判斷157和161是否是素?cái)?shù).解,都小于13,小于13的素?cái)?shù)有:2,3,5,7,11.檢查結(jié)果如下:2157,3157,5157,7157,11157結(jié)論:157是素?cái)?shù).2161,3161,5161,7|161（161=7×23）結(jié)論：161是合數(shù).例題12

12345678910

12345678910

12345678910

12345678

9

10

1112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

12345678

9

10

11121314151617181920212223242526272829303132333435363738394041424344454647484950

51525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

12345678

9

10

11121314

15

1617181920

21

2223242526

27

2829303132

33

3435363738

39

4041424344

45

4647484950

515253545556575859606162

63

6465666768

69

7071727374

75

7677787980

81

8283848586

87

8889909192

93

9495969798

99

100

12345678

9

10

11121314

15

1617181920

21

222324

25

26

27

2829303132

33

34

35

363738

39

4041424344

45

4647484950515253545556575859606162

63

64

65

666768

69

7071727374

75

7677787980

81

828384

85

86

87

8889909192

93

94

95

969798

99

100

12345678

9

10

11121314

15

1617181920

21

222324

25

26

27

2829303132

33

34

35

363738

39

4041424344

45

464748

49

50515253545556575859606162

63

64

65

666768

69

7071727374

75

76

77

787980

81

828384

85

86

87

888990

91

92

93

94

95

969798

99

100埃拉托斯特尼(Eratosthene)篩法13d是a與b的公因子(公約數(shù)):d|a且d|bm是a與b的公倍數(shù):a|m且b|m定義19.3

設(shè)a和b是兩個(gè)不全為0的整數(shù),稱(chēng)a與b的公因子中最大的為a與b的最大公因子,或最大公約數(shù),記作gcd(a,b).設(shè)a和b是兩個(gè)非零整數(shù),稱(chēng)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.19.2

最大公約數(shù)與最小公倍數(shù)14定理19.5(1)若a|m,b|m,則lcm(a,b)|m.(2)若d|a,d|b,則d|gcd(a,b).證(1)記M=lcm(a,b),設(shè)m=qM+r,0≤r<M.由a|m,a|M,及r=m

qM,可推出a|r.同理,有b|r.即,r是a和b的公倍數(shù).根據(jù)最小公倍數(shù)的定義,必有r=0.得證M|m.(2)記D=gcd(a,b),令m=lcm(d,D).若m=D,自然有d|D,結(jié)論成立.否則m>D,注意到d|a,D|a,由(1),得m|a.同理,m|b.即,m是a和b的公因子,與D是a和b的最大公約數(shù)矛盾.最大公約數(shù)與最小公倍數(shù)的性質(zhì)15最大公約數(shù)與最小公倍數(shù)(續(xù))例4

求150和220的最大公約數(shù)和最小公倍數(shù).利用整數(shù)的素因子分解,求最大公約數(shù)和最小公倍數(shù).設(shè)

其中p1,p2,…,pk是不同的素?cái)?shù),r1,r2,…,rk,s1,s2,…,sk是非負(fù)整數(shù).則

gcd(a,b)=lcm(a,b)=解150=2×3×52,168=23×3×7.gcd(150,168)=21×31×50×70=6,lcm(150,168)=23×31×52×71=4200.16輾轉(zhuǎn)相除法定理19.6

設(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=a

qb,由性質(zhì)19.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的公因子.17輾轉(zhuǎn)相除法—?dú)W幾里得(Euclid)算法輾轉(zhuǎn)相除法設(shè)整數(shù)a,b,且b≠0,求gcd(a,b).做帶余除法a=qb+r,0≤r<|b|.若r=0,則gcd(a,b)=b;若r>0,再對(duì)b和r做帶余除法b=q

r+r

,0≤r

<r.若r=0,則gcd(a,b)=gcd(b,r)=r;否則重復(fù)上述過(guò)程,直至余數(shù)等于0為止.例5

求210與715的最大公因子解715=3×210+85,210=2×85+40,85=2×40+5,40=8×5.得

gcd(715,210)=5.18關(guān)于最大公因子的一個(gè)定理定理19.7

設(shè)a和b不全為0,則存在整數(shù)x和y使得

gcd(a,b)=xa+yb.證記a=r0,b=r1,做輾轉(zhuǎn)相除法

ri=qi+1ri+1+ri+2,i=0,1,…,k

2,rk

1=qkrk,gcd(a,b)=rk.把上式改寫(xiě)成ri+2=ri

qi+1ri+1,i=k

2,k

3,…,0從后向前逐個(gè)回代,就可將rk表成a和b的線性組合.19例題例5

(續(xù))gcd(715,210)=5715=3×210+85,210=2×85+40,85=2×40+5,40=8×5.于是,有

5=85－2×40=85－2×(210－2×85)=5×85－2×210=5×(715－3×210)－2×210=5×715－17×210.20互素定理19.8

整數(shù)a和b互素的充分必要條件是存在整數(shù)x和y使得

xa+yb=1證必要性可由定理19.7得到.充分性.設(shè)xa+yb=1,x和y是整數(shù).又設(shè)d>0是a和b的公因子,有

d|xa+yb,即d|1.從而d=1,得證a和b互素.定義19.2

如果gcd(a,b)=1,則稱(chēng)a和b互素.如果a1,a2,,an中的任意兩個(gè)都互素,則稱(chēng)它們兩兩互素.例如,8和15互素,而8和12不互素.4,9,11,35兩兩互素.21例題例6

設(shè)a|c,b|c,且a與b互素,則ab|c.證根據(jù)定理19.8,存在整數(shù)x,y,使xa+yb=1.兩邊同乘以c,得cxa+cyb=c.又由a|xa和b|c,可得ab|cxa.同理,ab|cyb.于是,有ab|cxa+cyb,即ab|c.2219.3同余定義19.3

設(shè)m是正整數(shù),a和b是整數(shù).如果m|a

b,則稱(chēng)a模m同余于b,或a與b模m同余,記作a≡b(modm).如果a與b模m不同余,則記作ab(modm).例如,15≡3(mod4),16≡0(mod4),14≡

2(mod4),1516(mod4).下述兩條都是a與b模m同余的充分必要條件:(1)amodm=bmodm.(2)a=b+km,其中k是整數(shù).23同余的性質(zhì)性質(zhì)19.10

同余關(guān)系是等價(jià)關(guān)系,即同余關(guān)系具有①

自反性.a≡a(modm)②

傳遞性.a≡b(modm)∧b≡c(modm)

a≡c(modm).③

對(duì)稱(chēng)性.a≡b(modm)

b≡a(modm).

縮寫(xiě)a1≡a2≡…≡ak(modm).性質(zhì)19.11

模算術(shù)運(yùn)算若a≡b(modm),c≡d(modm),則

a±c≡b±d(modm),ac≡bd(modm),ak≡bk(modm),其中k是非負(fù)整數(shù).性質(zhì)19.12

設(shè)d≥1,d|m,則a≡b(modm)

a≡b(modd).性質(zhì)19.13

設(shè)d≥1,則a≡b(modm)

da≡db(moddm).性質(zhì)19.14

設(shè)c,m互素,則a≡b(modm)

ca≡cb(modm).24模m等價(jià)類(lèi)模m等價(jià)類(lèi):在模m同余關(guān)系下的等價(jià)類(lèi).[a]m,簡(jiǎn)記作[a].Zm:Z在模m同余關(guān)系下的商集在Zm上定義加法和乘法如下:

a,b,[a]+[b]=[a+b],[a]·[b]=[ab].例7

寫(xiě)出Z4的全部元素以及Z4上的加法表和乘法表.解Z4={[0],[1],[2],[3]},其中[i]={4k+i|k∈Z},i=0,1,2,3.

[0][1][2][3][0][1][2][3]+[0][1][2][3][1][2][3][0][2][3][0][1][3][0][1][2]

[0][1][2][3][0][1][2][3]·[0][0][0][0][0][1][2][3][0][2][0][2][0][3][2][1]25例83455的個(gè)位數(shù)是多少?解設(shè)3455的個(gè)位數(shù)為x,則3455≡x(mod10).由34≡1(mod10),有3455=34113+3≡33≡7(mod10),故3455的個(gè)位數(shù)是7.例9

日期的星期數(shù)

y年m月d日星期數(shù)的計(jì)算公式:其中M=(m－3)mod12+1,Y=y

M/11=100C+XY年M月:3月~下一年2月,C:Y年的世紀(jì)數(shù)??????????)7(mod12/2/)7/(224/4/dmMMMCCXXw+++++-++o例題26例題例9

(續(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,是星期三.2719.4一次同余方程定理19.9

方程ax≡c(modm)有解的充要條件是gcd(a,m)|c.證充分性.記d=gcd(a,m),a=da1,m=dm1,c=dc1,其中a1與m1互素.由定理11.8,存在x1和y1使得a1x1+m1y1=1.令x=c1x1,y=c1y1,得a1x+m1y=c1.等式兩邊同乘d,得ax+my=c.所以,ax≡c(modm).

必要性.設(shè)x是方程的解,則存在y使得ax+my=c.由性質(zhì)19.1,有d|c.一次同余方程:ax≡c(modm),其中m>0.一次同余方程的解:使方程成立的整數(shù)例如,2x≡0(mod4)的解為x≡0(mod2),2x≡1(mod4)無(wú)解28例題例10

解一次同余方程6x≡3(mod9).解gcd(6,9)=3|3,方程有解.取模9等價(jià)類(lèi)的代表x=

4,

3,

2,

1,0,1,2,3,4,檢查它們是否是方程的解,計(jì)算結(jié)果如下:6×(

4)≡6×(

1)≡6×2≡3(mod9),6×(

3)≡6×0≡6×3≡0(mod9),6×(

2)≡6×1≡6×4≡6(mod9),得方程的解x=

4,

1,2(mod9),方程的最小正整數(shù)解是2.29模m逆定理19.10(1)a的模m逆存在的充要條件是a與m互素.(2)設(shè)a與m互素,則在模m下a的模m逆是惟一的.證(1)這是定理19.9的直接推論.(2)設(shè)ab1≡1(modm),ab2≡1(modm).得a(b1

b2)≡0(modm).由a與m互素,b1

b2≡0(modm),得證b1≡b2(modm).定義19.4

如果ab≡1(modm),則稱(chēng)b是a的模m逆,

記作a

1(modm)或a

1.a

1(modm)是方程ax≡1(modm)的解.30例題例11

求5的模7逆.解5與7互素,故5的模7逆存在.方法1.解方程5x≡1(mod7).檢查x=

3,

2,

1,0,1,2,3,得到5

1≡3(mod7).方法2.做輾轉(zhuǎn)相除法,求得整數(shù)b,k使得5b+7k=1,則b是5的模7逆.計(jì)算如下:7=5+2,5=2×2+1.回代1=5

2×2=5

2×(7

5)=3×5

2×7,得5

1≡3(mod7).方法3.直接觀察5

3=15,151(mod7),得5

1≡3(mod7).31歐拉函數(shù)

(n):{0,1,…,n

1}中與n互素的數(shù)的個(gè)數(shù)例如

(1)=

(2)=1,

(3)=

(4)=2.當(dāng)n為素?cái)?shù)時(shí)

(n)=n

1;當(dāng)n為合數(shù)時(shí)

(n)<n

1.定理19.11(歐拉定理)

設(shè)a與n互素,則

a

(n)≡1(modn).19.5歐拉定理和費(fèi)馬小定理

32歐拉定理的證明證設(shè)r1,r2,…,r

(n)是{0,1,…,n

1}中與n互素的

(n)個(gè)數(shù).由于a與n互素,對(duì)每一個(gè)1≤i≤

(n),ari也與n互素,故存在1≤

(i)≤

(n)使得ari≡r

(i)(modn).

是{1,2,…,

(n)}上的映射.要證

是一個(gè)單射.a的模n逆a

1存在,a

1也與n互素.

假設(shè)i≠j,

(i)=

(j),則有ari≡arj(modn).兩邊同乘a

1,得ri≡rj(modn),矛盾.得證

是{1,2,…,φ(n)}上的單射,當(dāng)然也是{1,2,…,

(n)}上的雙射.從而,有而與n互素,故a

(n)≡1(modn).33費(fèi)馬(Fermat)小定理定理19.12(費(fèi)馬小定理)

設(shè)p是素?cái)?shù),a與p互素,則

ap-1≡1(modp).另一種形式是,設(shè)p是素?cái)?shù),則對(duì)任意的整數(shù)a,ap≡a(modp).

費(fèi)馬小定理提供了一種不用因子分解就能斷定一個(gè)數(shù)是合數(shù)的新途徑.例如,29

1≡4(mod9),可以斷定9是合數(shù).3419.6初等數(shù)論在計(jì)算機(jī)科

學(xué)技術(shù)中的幾個(gè)應(yīng)用主要內(nèi)容產(chǎn)生均勻偽隨機(jī)數(shù)的方法密碼學(xué)35產(chǎn)生均勻偽隨機(jī)數(shù)的方法隨機(jī)數(shù):隨機(jī)變量的觀察值偽隨機(jī)數(shù)(0,1)上的均勻分布U(0,1):

a(0<a<1),P{0<X≤a}=a

線性同余法選擇4個(gè)非負(fù)整數(shù):模數(shù)m,乘數(shù)a,常數(shù)c和種子數(shù)x0,其中2≤a<m,0≤c<m,0≤x0<m,用遞推公式產(chǎn)生偽隨機(jī)數(shù)序列:xn=(axn

1+c)modm,n=1,2,…取un=xn/m,n=1,2,…作為U(0,1)偽隨機(jī)數(shù).36線性同余法與乘同余法線性同余法產(chǎn)生的序列的質(zhì)量取決于m,a和c.例如m=8,a=3,c=1,x0=2,得到7,6,3,2,7,6,…,周期為4m=8,a=5,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(x0≠0)的線性同余法,即

xn=axn

1modm,n=1,2,….最常用的均勻偽隨機(jī)數(shù)發(fā)生器:m=231

1,a=75的乘同余法,它的周期是231

2.37密碼學(xué)愷撒(Caesar)密碼加密方法:ABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC明文:SEEYOUTOMORROW密文:VHHBRXWRPRUURZ184424142019141214171714222177117232217151720201725加密算法

E(i)=(i+k)mod26,i=0,1,…,25,解密算法

D(i)=(i

k)mod26,i=0,1,…,25其中密鑰k是一取定的整數(shù),這里取k=3.38加密算法線性同余加密算法

E(i)=(ai+b)mod26,i=0,1,…,25,其中a與26互素.維吉利亞(Vigenere)密碼把明文分成若干段,每一段有n個(gè)數(shù)字,密鑰k=k1k2…kn,加密算法

E(i1i2…in)=c1c2…cn,其中cj=(ij+kj)mod26,ij=0,1,…,25,j=1,2,…,n.39RSA公鑰密碼私鑰密碼:加密密鑰和解密密鑰都必須嚴(yán)格保密公鑰密碼

(W.Diffie,M.Hellman,1976):加密密鑰公開(kāi),解密密鑰保密RSA公鑰密碼(R.Rivest,A.Shamir,L.Adleeman,1978)取2個(gè)大素?cái)?shù)p和q(p≠q),記n=pq,

(n)=(p

1)(q

1).選擇正整數(shù)w,w與

(n)互素,設(shè)d=w

1(mod

(n)).將明文數(shù)字化,分成若干段,每一個(gè)明文段m<n.加密算法c=E(m)=mwmodn,解密算法D(c)=cdmodn,其中加密密鑰w和n是公開(kāi)的,而p,q,

(n)和d是保密的.40解密算法正確性證明要證m=cdmodn,即cd≡m(modn),亦即mdw≡m(modn).由dw≡1(mod

(n)),存在k使得dw=k

(n)+1.有兩種可能:(1)m與n互素.由歐拉定理m

(n)≡1(modn),得mdw≡mk

(n)+1

≡m(modn).(2)m與n不互素.不妨設(shè)m=cp且q不整除m.由費(fèi)馬小定理

mq

1≡1(modq).于是,mk

(n)≡mk(p

1)(q

1)≡1k(p

1)≡1(modq).從而存在h使得

mk

(n)=hq+1,兩邊同乘以m,并注意到m=cp,mk

(n)+1=hcpq+m=hcn+m,得證

mk

(n)+1≡m(modn),即

mdw≡m(modn).41模冪乘運(yùn)算

模冪乘運(yùn)算ab(modn)設(shè)b=b0+b1×2+…+br

1×2r

1,其中bi=0或1,于是令A(yù)0=a,Ai≡(Ai

1)2(modn),i=1,2,…,r

1,則有42例題例12

p=43,q=59,n=43×59=2537,

(n)=42×58=2436,w=13.A,B,…,Z依次用00,01,…,25表示,各占2位.設(shè)明文段m=2106,即VG,密文c=210613mod2537.計(jì)算如下:13=(1101)2,即13=1+22+23.A0=2106≡

431(mod2537),A1≡(

431)2≡560(mod2537),A2≡5602≡

988(mod2537),A3≡(

988)2≡

601(mod2537),210613≡(

431)×(

988)×(

601)≡2321(mod2537),得密文c=2321.43例題(續(xù))設(shè)密文c=0981.d=13

1≡937(mod2436),明文m=981937(mod2537).計(jì)算如下:937=(1110101001)2,A0=981,A1