1主要內容素數最大公約數與最小公倍數同余一次同余方程歐拉定理與費馬小定理初等數論在計算機科學技術中的幾個應用第六部分初等數論2第十九章初等數論主要內容素數最大公約數與最小公倍數同余一次同余方程歐拉定理與費馬小定理初等數論在計算機科學技術中的幾個應用319.1素數今后只考慮正整數的正因子.平凡因子

:1和自身真因子

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

若a|b且a|c,則

x,y,有a|xb+yc.性質19.2

若a|b且b|c,則a|c.性質19.3

設m≠0,則a|b當且僅當ma|mb.性質19.4

若a|b且b|a,則a=±b.性質19.5

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

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

當且僅當amodb=05素數與合數性質19.6

如果d>1,p是素數且d|p,則d=p.性質19.7

設p是素數且p|ab,則必有p|a或者p|b.

設p是素數且p|a1a2…ak,則必存在1≤i≤k,使得p|ai.

注意:當d不是素數時,d|ab不一定能推出d|a或d|b.性質19.8

a>1是合數當且僅當a=bc,其中1<b<a,1<c<a.性質19.9

合數必有素數因子.定義19.1

大于1且只能被1和自身整除的正整數稱為素數或質數.大于1且不是素數的正整數稱為合數.例如,2,3,5,7,11是素數,4,6,8,9是合數.

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

設a>1,則

a=,其中p1,p2,…,pk是不相同的素數,r1,r2,…,rk是正整數,并且在不計順序的情況下,該表示是惟一的.

該表達式稱作整數a的素因子分解.例如30=2×3×5,117=32×13,1024=210

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

10!=28×34×52×7,故10!的二進制表示中從最低位數起有8個連續的0.8素數的分布梅森數(MarinMersenne):2p

1,其中p為素數當n是合數時,2n

1一定是合數,2ab

1=(2a

1)(2a(b

1)+2a(b

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

1=3,23

1=7,25

1=31,27

1=127都是素數,而211

1=2047=23×89是合數.到2002年找到的最大梅森素數是213466917

1,有4百萬位.定理19.2

有無窮多個素數.證用反證法.假設只有有窮多個素數,設為p1,p2,…,pn,令m=p1p2…pn+1.顯然,pi

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

(n):

小于等于n的素數個數.例如

(0)=

(1)=0,

(2)=1,

(3)=

(4)=2,

(5)=3.168122995927849866457914510868686723826204211.1591.1321.1041.0851.071

(n)n/lnn

(n)n/lnn103104105106107n定理19.3(素數定理)10素數測試定理11.4

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

判斷157和161是否是素數.解,都小于13,小于13的素數有:2,3,5,7,11.檢查結果如下:2157,3157,5157,7157,11157結論:157是素數.2161,3161,5161,7|161（161=7×23）結論：161是合數.例題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的公因子(公約數):d|a且d|bm是a與b的公倍數:a|m且b|m定義19.3

設a和b是兩個不全為0的整數,稱a與b的公因子中最大的為a與b的最大公因子,或最大公約數,記作gcd(a,b).設a和b是兩個非零整數,稱a與b最小的正公倍數為a與b的最小公倍數,記作lcm(a,b).例如gcd(12,18)=6,lcm(12,18)=36.對任意的正整數a,gcd(0,a)=a,gcd(1,a)=1,lcm(1,a)=a.19.2

最大公約數與最小公倍數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),設m=qM+r,0≤r<M.由a|m,a|M,及r=m

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

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

其中p1,p2,…,pk是不同的素數,r1,r2,…,rk,s1,s2,…,sk是非負整數.則

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輾轉相除法定理19.6

設a=qb+r,其中a,b,q,r都是整數,則

gcd(a,b)=gcd(b,r).證只需證a與b和b與r有相同的公因子.設d是a與b的公因子,即d|a且d|b.注意到,r=a

qb,由性質19.1,有d|r.從而,d|b且d|r,即d也是b與r的公因子.反之一樣,設d是b與r的公因子,即d|b且d|r.注意到,a=qb+r,故有d|a.從而,d|a且d|b,即d也是a與b的公因子.17輾轉相除法—歐幾里得(Euclid)算法輾轉相除法設整數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;否則重復上述過程,直至余數等于0為止.例5

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

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

設a和b不全為0,則存在整數x和y使得

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

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的線性組合.19例題例5

(續)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

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

xa+yb=1證必要性可由定理19.7得到.充分性.設xa+yb=1,x和y是整數.又設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兩兩互素.21例題例6

設a|c,b|c,且a與b互素,則ab|c.證根據定理19.8,存在整數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

設m是正整數,a和b是整數.如果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是整數.23同余的性質性質19.10

同余關系是等價關系,即同余關系具有①

自反性.a≡a(modm)②

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

a≡c(modm).③

對稱性.a≡b(modm)

b≡a(modm).

縮寫a1≡a2≡…≡ak(modm).性質19.11

模算術運算若a≡b(modm),c≡d(modm),則

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

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

a≡b(modd).性質19.13

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

da≡db(moddm).性質19.14

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

ca≡cb(modm).24模m等價類模m等價類:在模m同余關系下的等價類.[a]m,簡記作[a].Zm:Z在模m同余關系下的商集在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]25例83455的個位數是多少?解設3455的個位數為x,則3455≡x(mod10).由34≡1(mod10),有3455=34113+3≡33≡7(mod10),故3455的個位數是7.例9

日期的星期數

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

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

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

C=19,X=49,M=8,d=1,是星期六.中國人民抗日戰爭勝利日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).

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

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

4,

3,

2,

1,0,1,2,3,4,檢查它們是否是方程的解,計算結果如下: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),方程的最小正整數解是2.29模m逆定理19.10(1)a的模m逆存在的充要條件是a與m互素.(2)設a與m互素,則在模m下a的模m逆是惟一的.證(1)這是定理19.9的直接推論.(2)設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)的解.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.做輾轉相除法,求得整數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).31歐拉函數

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

1}中與n互素的數的個數例如

(1)=

(2)=1,

(3)=

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

(n)=n

1;當n為合數時

(n)<n

1.定理19.11(歐拉定理)

設a與n互素,則

a

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

32歐拉定理的證明證設r1,r2,…,r

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

1}中與n互素的

(n)個數.由于a與n互素,對每一個1≤i≤

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

(i)≤

(n)使得ari≡r

(i)(modn).

是{1,2,…,

(n)}上的映射.要證

是一個單射.a的模n逆a

1存在,a

1也與n互素.

假設i≠j,

(i)=

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

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

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

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

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

設p是素數,a與p互素,則

ap-1≡1(modp).另一種形式是,設p是素數,則對任意的整數a,ap≡a(modp).

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

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

學技術中的幾個應用主要內容產生均勻偽隨機數的方法密碼學35產生均勻偽隨機數的方法隨機數:隨機變量的觀察值偽隨機數(0,1)上的均勻分布U(0,1):

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

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

1+c)modm,n=1,2,…取un=xn/m,n=1,2,…作為U(0,1)偽隨機數.36線性同余法與乘同余法線性同余法產生的序列的質量取決于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,….最常用的均勻偽隨機數發生器:m=231

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

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

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

D(i)=(i

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

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

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

(W.Diffie,M.Hellman,1976):加密密鑰公開,解密密鑰保密RSA公鑰密碼(R.Rivest,A.Shamir,L.Adleeman,1978)取2個大素數p和q(p≠q),記n=pq,

(n)=(p

1)(q

1).選擇正整數w,w與

(n)互素,設d=w

1(mod

(n)).將明文數字化,分成若干段,每一個明文段m<n.加密算法c=E(m)=mwmodn,解密算法D(c)=cdmodn,其中加密密鑰w和n是公開的,而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不互素.不妨設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).41模冪乘運算

模冪乘運算ab(modn)設b=b0+b1×2+…+br

1×2r

1,其中bi=0或1,于是令A0=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位.設明文段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.43例題(續)設密文c=0981.d=13

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