離散數(shù)學(xué)第十九章省公開課一等獎全國示范課微課金獎

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

:1和本身真因子:除1和本身之外因子比如,2,3是6真因子設(shè)a,b是兩個整數(shù)，且b≠0.假如存在整數(shù)c使a=bc，則稱a被b整除，或b整除a，記作b|a.此時,又稱a是b倍數(shù)，b是a因子.把b不整除a記作ba.比如,6有8個因子±1,±2,±3和±6.3第3頁整除性質(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當且僅當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當且僅當amodb=04第4頁素數(shù)與合數(shù)性質(zhì)19.6假如d>1,p是素數(shù)且d|p,則d=p.性質(zhì)19.7設(shè)p是素數(shù)且p|ab,則必有p|a或者p|b.設(shè)p是素數(shù)且p|a1a2…ak,則必存在1≤i≤k,使得p|ai.注意:當d不是素數(shù)時,d|ab不一定能推出d|a或d|b.性質(zhì)19.8

a>1是合數(shù)當且僅當a=bc,其中1<b<a,1<c<a.性質(zhì)19.9合數(shù)必有素數(shù)因子.定義19.1

大于1且只能被1和本身整除正整數(shù)稱為素數(shù)或質(zhì)數(shù).大于1且不是素數(shù)正整數(shù)稱為合數(shù).比如,2,3,5,7,11是素數(shù),4,6,8,9是合數(shù).

5第5頁算術(shù)基本定理定理19.1(算術(shù)基本定理)

設(shè)a>1,則a=,其中p1,p2,…,pk是不相同素數(shù),r1,r2,…,rk是正整數(shù),而且在不計次序情況下,該表示是惟一.該表示式稱作整數(shù)a素因子分解.比如30=2×3×5,117=32×13,1024=210

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

1,其中p為素數(shù)當n是合數(shù)時,2n

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

1=(2a

1)(2a(b

1)+2a(b

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

1=3,23

1=7,25

1=31,27

1=127都是素數(shù),而211

1=2047=23×89是合數(shù).到年找到最大梅森素數(shù)是213466917

1,有4百萬位.定理19.2有沒有窮多個素數(shù).證用反證法.假設(shè)只有有窮多個素數(shù),設(shè)為p1,p2,…,pn,令m=p1p2…pn+1.顯然,pi

m,1≤i≤n.所以,要么m本身是素數(shù)，要么存在大于pn素數(shù)整除m,矛盾.8第8頁素數(shù)分布(續(xù))

(n):小于等于n素數(shù)個數(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(素數(shù)定理)9第9頁素數(shù)測試定理11.4假如a是合數(shù),則a必有小于等于真因子.證由性質(zhì)19.8,a=bc,其中1<b<a,1<c<a.顯然,b和c中必有一個小于等于.不然,bc>()2=a,矛盾.推論假如a是合數(shù),則a必有小于等于素因子.證由定理,a有小于等于真因子b.假如b是素數(shù),則結(jié)論成立.假如b是合數(shù),由性質(zhì)19.9和性質(zhì)19.5,b有素因子p<b≤.依據(jù)性質(zhì)11.2,p也是a因子,結(jié)論也成立.10第10頁例3判斷157和161是否是素數(shù).解,都小于13,小于13素數(shù)有:2,3,5,7,11.檢驗結(jié)果以下:2157,3157,5157,7157,11157結(jié)論:157是素數(shù).2161,3161,5161,7|161（161=7×23）結(jié)論：161是合數(shù).例題11第11頁

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)篩法12第12頁d是a與b公因子(條約數(shù)):d|a且d|bm是a與b公倍數(shù):a|m且b|m定義19.3設(shè)a和b是兩個不全為0整數(shù),稱a與b公因子中最大為a與b最大公因子,或最大條約數(shù),記作gcd(a,b).設(shè)a和b是兩個非零整數(shù),稱a與b最小正公倍數(shù)為a與b最小公倍數(shù),記作lcm(a,b).比如gcd(12,18)=6,lcm(12,18)=36.對任意正整數(shù)a,gcd(0,a)=a,gcd(1,a)=1,lcm(1,a)=a.19.2最大條約數(shù)與最小公倍數(shù)13第13頁定理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ì)14第14頁最大條約數(shù)與最小公倍數(shù)(續(xù))例4求150和220最大條約數(shù)和最小公倍數(shù).利用整數(shù)素因子分解,求最大條約數(shù)和最小公倍數(shù).設(shè)

其中p1,p2,…,pk是不一樣素數(shù),r1,r2,…,rk,s1,s2,…,sk是非負整數(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.15第15頁輾轉(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公因子.16第16頁輾轉(zhuǎn)相除法—歐幾里得(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,再對b和r做帶余除法b=q

r+r

,0≤r

<r.若r

=0,則gcd(a,b)=gcd(b,r)=r;不然重復(fù)上述過程,直至余數(shù)等于0為止.例5求210與715最大公因子解715=3×210+85,210=2×85+40,85=2×40+5,40=8×5.得gcd(715,210)=5.17第17頁關(guān)于最大公因子一個定理定理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.把上式改寫成ri+2=ri

qi+1ri+1,i=k

2,k

3,…,0從后向前逐一回代,就可將rk表成a和b線性組合.18第18頁例題例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.19第19頁互素定理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,則稱a和b互素.假如a1,a2,,an中任意兩個都互素,則稱它們兩兩互素.比如,8和15互素,而8和12不互素.4,9,11,35兩兩互素.20第20頁例題例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.21第21頁19.3同余定義19.3設(shè)m是正整數(shù),a和b是整數(shù).假如m|a

b,則稱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ù).22第22頁同余性質(zhì)性質(zhì)19.10同余關(guān)系是等價關(guān)系,即同余關(guān)系含有①

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

a≡c(modm).③對稱性.a≡b(modm)

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

模算術(shù)運算若a≡b(modm),c≡d(modm),則a±c≡b±d(modm),ac≡bd(modm),ak≡bk(modm),其中k是非負整數(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).23第23頁模m等價類模m等價類:在模m同余關(guān)系下等價類.[a]m,簡記作[a].Zm:Z在模m同余關(guān)系下商集在Zm上定義加法和乘法以下:

a,b,[a]+[b]=[a+b],[a]·[b]=[ab].例7寫出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]24第24頁例83455個位數(shù)是多少?解設(shè)3455個位數(shù)為x,則3455≡x(mod10).由34≡1(mod10),有3455=34113+3≡33≡7(mod10),故3455個位數(shù)是7.例9日期星期數(shù)y年m月d日星期數(shù)計算公式:其中M=(m－3)mod12+1,Y=y

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

(續(xù))比如,中華人民共和國成立日1949年10月1日,

C=19,X=49,M=8,d=1,是星期六.中國人民抗日戰(zhàn)爭勝利日1945年8月15日,

C=19,X=45,M=6,d=15,是星期三.26第26頁19.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)無解27第27頁例題例10解一次同余方程6x≡3(mod9).解gcd(6,9)=3|3,方程有解.取模9等價類代表x=

4,

3,

2,

1,0,1,2,3,4,檢驗它們是否是方程解,計算結(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.28第28頁模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),則稱b是a模m逆,記作a

1(modm)或a

1.a

1(modm)是方程ax≡1(modm)解.29第29頁例題例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逆.計算以下: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).30第30頁歐拉函數(shù)

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

1}中與n互素數(shù)個數(shù)比如

(1)=

(2)=1,

(3)=

(4)=2.當n為素數(shù)時

(n)=n

1;當n為合數(shù)時

(n)<n

1.定理19.11(歐拉定理)

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

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

31第31頁歐拉定理證實證設(shè)r1,r2,…,r

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

1}中與n互素

(n)個數(shù).因為a與n互素,對每一個1≤i≤

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

(i)≤

(n)使得ari≡r

(i)(modn).

是{1,2,…,

(n)}上映射.要證

是一個單射.a模n逆a

1存在,a

1也與n互素.

假設(shè)i≠j,

(i)=

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

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

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

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

(n)≡1(modn).32第32頁費馬(Fermat)小定理定理19.12(費馬小定理)

設(shè)p是素數(shù),a與p互素,則ap-1≡1(modp).另一個形式是,設(shè)p是素數(shù),則對任意整數(shù)a,ap≡a(modp).

費馬小定理提供了一個不用因子分解就能斷定一個數(shù)是合數(shù)新路徑.比如,29

1≡4(mod9),能夠斷定9是合數(shù).33第33頁19.6初等數(shù)論在計算機科

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

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

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

1+c)modm,n=1,2,…取un=xn/m,n=1,2,…作為U(0,1)偽隨機數(shù).35第35頁線性同余法與乘同余法線性同余法產(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,….最慣用均勻偽隨機數(shù)發(fā)生器:m=231

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

2.36第36頁密碼學(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.37第37頁加密算法線性同余加密算法

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

E(i1i2…in)=c1c2…cn,其中cj=(ij+kj)mod26,ij=0,1,…,25,j=1,2,…,n.38第38頁RSA公鑰密碼私鑰密碼:加密密鑰和解密密鑰都必須嚴格保密公鑰密碼(W.Diffie,M.Hellman,1976):加密密鑰公開,解密密鑰保密RSA公鑰密碼(R.Rivest,A.Shamir,L.Adleeman,1978)取2個大素數(shù)p和q(p≠q),記n=pq,

(n)=(p

1)(q

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

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

1(mod

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

(n)和d是保密.39第39頁解密算法正確性證實要證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.由費馬小定理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).40第40頁模冪乘運算

模冪乘運算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,則有41第41頁例題例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.計算以下: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.42第42頁例題(續(xù))設(shè)密文c=0981.d=13

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