《信息安全數(shù)學(xué)基礎(chǔ).》全套教學(xué)課件

信息安全數(shù)學(xué)基礎(chǔ)全套可編輯PPT課件數(shù)論部分?jǐn)?shù)論是研究整數(shù)性質(zhì)的一個(gè)數(shù)學(xué)分支。整數(shù)的基本元素是素?cái)?shù)，所以數(shù)論的本質(zhì)是對(duì)素?cái)?shù)性質(zhì)的研究。數(shù)論被稱(chēng)為“純而又純的數(shù)學(xué)”。高斯曾經(jīng)說(shuō)過(guò)“數(shù)學(xué)是科學(xué)的皇后，數(shù)論是數(shù)學(xué)中的皇冠”。數(shù)學(xué)家們把數(shù)論中一些懸而未決的疑難問(wèn)題，稱(chēng)為“皇冠上的明珠”。2小故事德國(guó)數(shù)學(xué)家高斯集前人大成，寫(xiě)了一本書(shū)叫做《算術(shù)探討》，1800年寄給了法國(guó)科學(xué)院，但是法國(guó)科學(xué)院拒絕了高斯的這部杰作，高斯只好在1801年自己發(fā)表了這部著作。這部書(shū)開(kāi)始了現(xiàn)代數(shù)論的新紀(jì)元。在《算術(shù)探討》中，高斯把過(guò)去研究整數(shù)性質(zhì)所用的符號(hào)標(biāo)準(zhǔn)化，把當(dāng)時(shí)的定理系統(tǒng)化并進(jìn)行了推廣，把要研究的問(wèn)題和方法進(jìn)行了分類(lèi)，還引進(jìn)了新的方法。34第1章整數(shù)的整除與唯一分解1.1帶余除法和整除1.2整數(shù)的表示1.3最大公因子與輾轉(zhuǎn)相除法1.4最小公倍數(shù)1.5整數(shù)的唯一分解1.6素?cái)?shù)有無(wú)窮多1.7麥?zhǔn)材鶖?shù)與費(fèi)馬數(shù)*1.8素?cái)?shù)的著名問(wèn)題*

5重點(diǎn)內(nèi)容概念最大公因子、互素定理整數(shù)唯一分解算法歐幾里德算法（輾轉(zhuǎn)相除法）擴(kuò)展的歐幾里德算法61.1帶余除法和整除正整數(shù)（如1,2,3,…）、負(fù)整數(shù)（如–1,–2,–3,…）與零（0）統(tǒng)稱(chēng)為整數(shù)。通常，用符號(hào)Z={0,±1,±2,±3,…}表示整數(shù)集合，零與正整數(shù)稱(chēng)為自然數(shù)。兩個(gè)整數(shù)的和、差、積仍然是整數(shù)，但兩個(gè)整數(shù)相除得到的商未必是整數(shù)。為此，我們引入整除、帶余除法概念。

7定義1.1任意兩個(gè)整數(shù)a,b，其中b≠0，如果存在一個(gè)整數(shù)q，使等式a=bq(1.1)成立，我們就說(shuō)b整除a，或a被b整除，記為b|a。此時(shí)，稱(chēng)b為a的因子，a為b的倍數(shù)。0是任何非零整數(shù)的倍數(shù)，1是任何整數(shù)的因子。

8若b|a，且b≠1,b≠a，就稱(chēng)b是a的真因子；否則，就稱(chēng)b為a的平凡因子，任何非零整數(shù)是自身的因子和倍數(shù)。式(1.1)中的整數(shù)q，常寫(xiě)成a/b或。如果不存在整數(shù)q滿(mǎn)足式(1.1)，我們就說(shuō)b不整除a，記為b

a。a=bq(1.1)9設(shè)a,b,c為整數(shù)，根據(jù)整除的定義，不難得到以下性質(zhì)：1.若c|b,b|a，則c|a；（傳遞性）2.若b|a，c≠0，則cb|ca；3.若cb|ca，則b|a；4.若b|a且a≠0，則|b|≤|a|；5.若b|a,a≠0，則；6.若c|a,c|b，則對(duì)任意整數(shù)m,n，有c|ma±nb。10一般地，有下面的余數(shù)定理。定理1.1（帶余除法）設(shè)a,b是兩個(gè)整數(shù)，其中b>0，則存在唯一的整數(shù)q和r，使得a=bq+r,0≤r<b(1.2)成立。證明

考慮b的整數(shù)倍序列…,–3b,–2b,–b,0,b,2b,3b,…，在該序列中，整數(shù)a必位于某兩個(gè)相鄰的整數(shù)之間，設(shè)該區(qū)間為[qb,(q+1)b),即存在整數(shù)q，使得qb≤a<(q+1)b成立。11令r=a–qb，則有

a=qb+r,0≤r<b。進(jìn)一步，具有上述性質(zhì)的整數(shù)q,r是唯一的。不妨假設(shè)存在另外一組整數(shù)q1,r1，滿(mǎn)足a=bq1+r1,0≤r1<b。(1.3)將式(1.3)與式(1.2)相減，得b(q–q1)=(r1–r)，所以b|q–q1|=|r1–r|。

(1.4)等式(1.4)的左邊為b的倍數(shù)，即b|q–q1|=0或b|q–q1|≥b；12

而由于0≤r,r1<b，則等式(1.4)的右邊必為0≤|r1–r|<b。因此，要使等式(1.4)成立，只有q=q1，

r1=r。□式(1.2)稱(chēng)為帶余除法，或稱(chēng)為歐幾里德除法。當(dāng)r=0時(shí)，稱(chēng)q為a除以b的完全商；當(dāng)r

≠0時(shí)，稱(chēng)q為a除以b的不完全商；通常將q通稱(chēng)為商。

r稱(chēng)為a除以b得到的余數(shù)，余數(shù)都是非負(fù)整數(shù)。a=bq+r,0≤r<b(1.2)b|q–q1|=|r1–r|

(1.4)13為計(jì)算商q，引入下述定義。定義1.2設(shè)x為實(shí)數(shù)，小于或等于x的最大整數(shù)稱(chēng)為x的整數(shù)部分，記為[x]；x–[x]為x的小數(shù)部分。我們有[x]≤x<[x]+1。*

14整數(shù)a除以b得到的（不完全）商就是。事實(shí)上，由式(1.2)，,0≤r<b。由于，0≤<1，所以，=0。因此，q=。*

例1.1取a=17,b=5，則q==[3.4]=3,r=17–5×3=2。151.2整數(shù)的表示本節(jié)給出正整數(shù)的不同進(jìn)制表示法。對(duì)于負(fù)整數(shù)情況，可通過(guò)引入負(fù)號(hào)，類(lèi)似得到。整數(shù)通常用十進(jìn)制表示，例如，90521即為9×104+0×103+5×102+2×101+1。在計(jì)算機(jī)領(lǐng)域，整數(shù)常用二進(jìn)制、八進(jìn)制或十六進(jìn)制表示。對(duì)于任意整數(shù)n和大于1的整數(shù)a，n可以寫(xiě)成a進(jìn)制形式：n=rkak

+rk-1ak-1

+…+r1a+r0

，(1.5)其中ri∈Z,0≤ri

<a,i=0,1,…,k，式(1.5)稱(chēng)為n的a進(jìn)制表示。16n的a進(jìn)制表示可用帶余除法求得。n除以a，設(shè)商為q0，余數(shù)為r0，即n=q0a+r0,0≤r0<a，q0除以a，得到q0=q1a+r1,0≤r1<a，q1除以a，得到q1=q2a+r2,0≤r2<a，...以此類(lèi)推，得到qi=qi+1a+ri+1,0≤ri+1<a,i=0,1,2,...。由于a>1，所以整數(shù)序列n>q0>q1>q2>...≥0為嚴(yán)格遞減序列，則一定存在某個(gè)qt，使0≤qt<a，即有

qt=0×a+rt+1,0≤rt+1<a。17則有n=q0a+r0=(q1a+r1)a+r0=q1a2+r1a+r0……=qt-1at+rt-1at-1+...+r1a+r0=(qta+rt)at+rt-1at-1+...+r1a+r0=rt+1at+1+

rtat+rt-1at-1+...+r1a+r0。當(dāng)a=2時(shí)，上述方法可得到任意正整數(shù)的二進(jìn)制表示。

18例1.2將60801表示成二進(jìn)制形式。解

60801=30400×2+1(r0=1)30400=15200×2+0(r1=0)15200=7600×2+0(r2=0)7600=3800×2+0(r3=0)3800=1900×2+0(r4=0)1900=950×2+0(r5=0)950=475×2+0(r6=0)475=237×2+1(r7=1)237=118×2+1(r8=1)

19118=59×2+0(r9=0)59=29×2+1(r10=1)29=14×2+1(r11=1)14=7×2+0(r12=0)7=3×2+1(r13=1)3=1×2+1(r14=1)1=0×2+1(rt+1)(r15=1)因此，60801=(1110110110000001)2=215+214+213+211+210+28+27+1。20在十六進(jìn)制表示中，用0,1,2,…,9,A,B,C,D,E,F分別表示0,1,2,…,9,10,11,12,13,14,15這16個(gè)數(shù)。也可以反復(fù)使用帶余除法求得整數(shù)的十六進(jìn)制表示。21例1.3將60801表示成十六進(jìn)制形式。解

60801=3800×16+1(r0=1)3800=237×16+8(r1=8)237=14×16+13(r2=13)14=0×16+14(r3=14)因此，60801=(E,D,8,1)16=14×163+13×162+8×161+1實(shí)際上，二進(jìn)制與十六進(jìn)制有簡(jiǎn)單的對(duì)應(yīng)關(guān)系，例如60801=(1110110110000001)2=[(1110)2,(1101)2,(1000)2,(0001)2]16=(E,D,8,1)16。22表1.1列出了十進(jìn)制、十六進(jìn)制與二進(jìn)制三者之間的換算關(guān)系。

23根據(jù)換算表1.1，二進(jìn)制數(shù)與十六（八）進(jìn)制數(shù)可以直接相互轉(zhuǎn)化。例1.490521的二進(jìn)制表示為90521=(10110000110011001)2。則，十六（八）進(jìn)制表示是90521=[(1)2,(0110)2,(0001)2,(1001)2,(1001)2]16=(1,6,1,9,9)16。（=[(10)2,(110)2,(000)2,(110)2,(011)2,(001)2]16=(2,6,0,6,3,1)8。）24實(shí)際上，將整數(shù)的二進(jìn)制轉(zhuǎn)化為十六進(jìn)制，只要將二進(jìn)制數(shù)從最右端（低位）每隔4位分一段（最左端可以不足四位），然后每段相應(yīng)地轉(zhuǎn)化為十六進(jìn)制數(shù)即可。反之，將整數(shù)表示的十六進(jìn)制轉(zhuǎn)化為二進(jìn)制，只要將十六進(jìn)制數(shù)的每一位（起始位置左端、右端皆可）相應(yīng)地轉(zhuǎn)化為4位二進(jìn)制數(shù)即可。如a=(A3B2C1)16=(101000111011001011000001)2。*

251.3最大公因子與輾轉(zhuǎn)相除法本節(jié)利用定理1.1，討論整數(shù)的最大公因子的求法及其性質(zhì)。定義1.3設(shè)a,b為兩個(gè)非零整數(shù)，d為正整數(shù)，若d|a,d|b，則d稱(chēng)為a和b的公因子。a和b的公因子中最大的一個(gè)稱(chēng)為a和b的最大公因子，記為(a,b)或gcd(a,b)。若最大公因子(a,b)=1，就稱(chēng)a與b互素。因?yàn)?可以被任何整數(shù)整除，所以任一正整數(shù)a與0的最大公因子就是它自身a。定義(0,0)=0。26關(guān)于最大公因子，我們有以下定理。定理1.2設(shè)a,b,c是任意三個(gè)不為零的整數(shù)，且a=bq+c，其中q為整數(shù)，(1.6)則(a,b)=(b,c)。證明

因?yàn)?a,b)|a,(a,b)|b，所以(a,b)|c，即(a,b)是b與c的公因子，根據(jù)定義1.3，(a,b)≤(b,c)。同理，(b,c)≤(a,b)。所以，(a,b)=(b,c)?！?7接下來(lái)討論最大公因子的求法，即歐幾里德算法（輾轉(zhuǎn)相除法），并借此給出最大公因子的若干性質(zhì)。設(shè)a,b為兩個(gè)正整數(shù)（a≥b），要計(jì)算(a,b)，循環(huán)使用帶余除法（定理1.1），有下列等式：a=q0b+r0,0≤r0<b，b=q1r0+r1,0≤r1<r0，r0=q2r1+r2,0≤r2<r1，...(1.7)rn-3=qn-1rn-2+rn-1,0≤rn-1<rn-2，rn-2=qnrn-1+rn,0≤rn<rn-1，rn-1=qn+1rn+rn+1,rn+1=0。事實(shí)上，因?yàn)檎麛?shù)序列b>r0>r1>r2>...≥0，嚴(yán)格遞減，故必存在某個(gè)n使得rn+1=0。28由定理1.2，rn=(0,rn)=(rn,rn-1)=(rn-1,rn-2)=...=(r1,r0)=(r0,b)=(b,a)。

因此，我們有以下定理。29定理1.3任意正整數(shù)a,b，循環(huán)使用帶余除法，最大公因子(a,b)就是式(1.7)中最后一個(gè)不為0的余數(shù)，即(a,b)=rn。算法1.1用歐幾里德算法求gcd(a,b)。輸入：兩個(gè)正整數(shù)a,b(a≥b)。輸出：gcd(a,b)。(1)求q,r使得a=qb+r,0≤r<b;(2)若r=0，則g←b,輸出g;否則，轉(zhuǎn)(3);(3)a←b,b←r,轉(zhuǎn)(1)。30例1.5求gcd(156,79)。解156=1×79+7779=1×77+277=38×2+12=2×1+0故，gcd(156,79)=1。31定理1.4

若整數(shù)a>b>0，則用歐幾里德算法求gcd(a,b)需要不多于

次除法運(yùn)算。32擴(kuò)展的歐幾里德算法：由算式(1.7)，rn=rn-2–qnrn-1

=rn-2–qn(rn-3–qn-1rn-2)=rn-2(1+qnqn-1)–qnrn-3=…=sa+tb其中s,t為整數(shù)。33于是有定理1.5（最大公因子表示定理）

任意正整數(shù)a,b，存在整數(shù)s,t，使得(a,b)=sa+tb。推論1.1若d是a和b的公因子，則d|(a,b)。34例1.6用輾轉(zhuǎn)相除法求(801,521)及整數(shù)s,t，使得(801,521)=801s+521t。解801=1×521+280(q0=1,r0=280)521=1×280+241(q1=1,r1=241)280=1×241+39(q2=1,r2=39)241=6×39+7(q3=6,r3=7)39=5×7+4(q4=5,r4=4)7=1×4+3(q5=1,r5=3)4=1×3+1(q6=1,r6=1)3=3×1+0根據(jù)定理1.3，最后一個(gè)不為0的余數(shù)是1，所以(801,521)=r6=1。35進(jìn)一步，280=801–1×521，241=521–1×280=521–(801–1×521)=2×521–801，39=280–1×241=(801–1×521)–(2×521–801)=2×801–3×521，7=241–6×39=(2×521–801)–6×(2×801–3×521)=20×521–13×801，4=39–5×7=(2×801–3×521)–5×(20×521–13×801)=67×801–103×521，3=7–1×4=(20×521–13×801)–(67×801–103×521)=123×521–80×801，1=4–1×3=(67×801–103×521)–(123×521–80×801)=147×801–226×521，即(801,521)=147×801+(–226)×521=1。36定理1.6若a|bc,(a,b)=1，則a|c。證明

若c=0，結(jié)論顯然成立。若c≠0，由于(a,b)=1，由定理1.5，存在兩個(gè)整數(shù)s,t，使sa+tb=1，故sac+tbc=c。由于a|bc，所以a|c?！?7例1.7

若3|n,5|n，則15|n。證由3|n，則存在整數(shù)n1，使得n=3n1。又由5|n，即5|3n1。因?yàn)?5,3)=1，根據(jù)定理1.6，5|n1。于是，存在整數(shù)n2，使得n1=5n2。即，n=3·5n2。故，15|n。38關(guān)于多個(gè)整數(shù)的最大公因子，有如下定義。定義1.4*

設(shè)a1,a2,….,an是n個(gè)整數(shù)，d為正整數(shù)，若(1)d|ai,i=1,2,…,n；(2)對(duì)任意正整數(shù)c，若c|ai,i=1,2,…,n，則c|d。則滿(mǎn)足條件(1)的d稱(chēng)為a1,a2,….,an的公因子；滿(mǎn)足條件(1)和(2)的d稱(chēng)為a1,a2,….,an的最大公因子，記為d=(a1,a2,….,an)。當(dāng)n=2時(shí)，由定理1.5與推論1.1，定義1.4與定義1.3等價(jià)。*

39下面的定理說(shuō)明，計(jì)算n個(gè)整數(shù)的最大公因子可以轉(zhuǎn)化為計(jì)算一系列的兩個(gè)整數(shù)的最大公因子。定理1.7*

設(shè)a1,a2,….,an是n個(gè)整數(shù)，令(a1,a2)=d2,(d2,a3)=d3,(d3,a4)=d4,…,(dn-2,an-1)=dn-1,(dn-1,an)=dn，(1.8)則(a1,a2,a3,...,an)=dn，且存在整數(shù)s1,s2,…,sn，使

s1a1+s2a2+…+snan=(a1,a2,a3,...,an)。*

40證明

由式(1.8)，di|di-1,i=n,n–1,…,3，且dn|an,dn-1|an-1,…,d3|a3,d2|a2,d2|a1。所以，dn|an,dn|an-1,…,dn|a2,dn|a1，即dn是整數(shù)a1,a2,a3,...,an的公因子。*

41假設(shè)c為a1,a2,….,an的公因子，即c|ai,i=1,2,…,n。因?yàn)閏|a1,c|a2，由推論1.1得c|d2；進(jìn)一步，由c|a3，得c|d3；…以此類(lèi)推，最后得c|dn。根據(jù)定義1.4，dn是a1,a2,….,an的最大公因子。*

42運(yùn)用定理1.5，可證明后一個(gè)結(jié)論。由于(a1,a2)=d2，存在整數(shù)t1,t2，使得t1a1+t2a2=d2；由于(d2,a3)=d3，存在整數(shù)u1,u2，使得u2d2+u3a3=d3，即u2(t1a1+t2a2)+u3a3=u2t1a1+u2t2a2+u3a3=d3；…以此類(lèi)推，存在整數(shù)s1,s2,…,sn，使s1a1+s2a2+…+snan=(a1,a2,a3,...,an)。

□*

43例1.8

計(jì)算10836,3744,7452,3834,708的最大公因子。解(1)計(jì)算(10836,3744)：10836=2×3744+33483744=1×3348+3963348=8×396+180396=2×180+36180=5×36+0由定理1.3，最后一個(gè)不為0的余數(shù)就是最大公因子，即(10836,3744)=36。*

44(2)計(jì)算(36,7452)=36。(3)(36,3834)=18。(4)(18,708)=6。所以，10836,3744,7452,3834,708的最大公因子是6。*

451.4最小公倍數(shù)定義1.5設(shè)a1,a2,…,an是n個(gè)非零整數(shù)，若m是這n個(gè)數(shù)中每一個(gè)數(shù)的倍數(shù)，即ai|m(1≤i≤n)，則m稱(chēng)為這n個(gè)數(shù)的一個(gè)公倍數(shù)。在a1,a2,…,an的所有公倍數(shù)中最小的正整數(shù)稱(chēng)為最小公倍數(shù)，記為[a1,a2,…,an]。因?yàn)槌朔e|a1||a2|…|an|就是a1,a2,…,an的一個(gè)公倍數(shù)，故最小公倍數(shù)存在。由于任何整數(shù)都不是0的倍數(shù)，故討論最小公倍數(shù)時(shí)，總假定這些整數(shù)均不為0。同最大公因子類(lèi)似，顯然有[a1,a2,…,an]=[|a1|,|a2|,…,|an|]，故只需討論正整數(shù)的最小公倍數(shù)。46定義1.5也可如下陳述：設(shè)a1,a2,…,an是n個(gè)非零整數(shù)，m為正整數(shù)，若(1)ai|m,i=1,2,…,n；(2)對(duì)任一正整數(shù)u，若ai|u,i=1,2,…,n，則m|u。則滿(mǎn)足條件(1)的m稱(chēng)為a1,a2,….,an的公倍數(shù)；滿(mǎn)足條件(1)和(2)的m稱(chēng)為a1,a2,….,an的最小公倍數(shù)，記為m=[a1,a2,….,an]。47當(dāng)n=2時(shí)，以下定理用于求兩個(gè)整數(shù)的最小公倍數(shù)。定理1.8設(shè)a,b是兩個(gè)正整數(shù)，則[a,b]=

。證明

設(shè)d=(a,b)，a=a1d,b=b1d。顯然，(a1,b1)=1。所以，=a1b1d。因?yàn)閍|a1b1d,b|a1b1d，由定義1.5，a1b1d是a和b的公倍數(shù)。48下面證明，a1b1d是a和b的最小公倍數(shù)。假設(shè)整數(shù)u滿(mǎn)足a|u,b|u。由a1d|u得，存在整數(shù)k，使得u=ka1d。

(1.9)由b1d|u，得b1d|ka1d。因此，b1|ka1。49因?yàn)?a1,b1)=1，由定理1.6，所以b1|k。令k=mb1，m為某整數(shù)。于是，u=ma1b1d。

(1.10)因此，只要整數(shù)u滿(mǎn)足a|u,b|u，就有a1b1d|u。這就證明了a1b1d是a和b的最小公倍數(shù)，即[a,b]=。

□50例1.9計(jì)算[1946,2006]。解第一步，求(1946,2006)。2006=1×1946+601946=32×60+2660=2×26+826=3×8+28=4×2+0所以，(1946,2006)=2。第二步，計(jì)算[1946,2006]==1951838。51求兩個(gè)以上正整數(shù)的最小公倍數(shù)，可以轉(zhuǎn)化為一系列求兩個(gè)正整數(shù)的最小公倍數(shù)。設(shè)a1,a2,…,an是n個(gè)正整數(shù)，令[a1,a2]=m2,[m2,a3]=m3,…,[mn-1,an]=mn，

(1.11)我們有定理1.9*

若a1,a2,…,an是n個(gè)正整數(shù)，則[a1,a2,…,an]=mn。證明

由式(1.11)，mi|mi+1,i=2,3,…,n–1，且a1|m2,a2|m2,a3|m3,…,an|mn。所以，a1|mn,a2|mn,…,an|mn，即mn是整數(shù)a1,a2,a3,...,an的公倍數(shù)。*

52假設(shè)m為a1,a2,….,an的公倍數(shù)，即ai|m,i=1,2,…,n。由式(1.11)，a1|m,a2|m，得m2|m；進(jìn)一步，由a3|m，得m3|m；…以此類(lèi)推，最終得mn|m。根據(jù)定義1.5，mn是a1,a2,….,an的最小公倍數(shù)。□定理1.8和定理1.9給出了兩個(gè)整數(shù)和多個(gè)整數(shù)的最小公倍數(shù)的求法。*

53例1.10計(jì)算200,150,360,45的最小公倍數(shù)。*

解第一步，根據(jù)定理1.8，求[200,150]：[200,150]===600。第二步，求[600,360]：[600,360]==

=1800。第三步，求[1800,45]：[1800,45]===1800。1800即為200,150,360,45的最小公倍數(shù)。541.5整數(shù)的唯一分解一個(gè)大于1的整數(shù)p是素?cái)?shù)，當(dāng)且僅當(dāng)它的因子只有兩個(gè)，即1和它本身；若還包括除1和它本身以外的因子，則稱(chēng)該整數(shù)為合數(shù)。1和0既非素?cái)?shù)也非合數(shù)。素?cái)?shù)與合數(shù)是相對(duì)立的兩個(gè)概念，二者是數(shù)論中最基礎(chǔ)的定義。本節(jié)的主要內(nèi)容是證明一個(gè)大于1的整數(shù)，若不考慮素?cái)?shù)的次序，能唯一地分解成素?cái)?shù)（素?cái)?shù)冪）的乘積。55定理1.10若p為素?cái)?shù)，a是任一整數(shù)，則p|a或(p,a)=1。證明

因?yàn)?p,a)|p，根據(jù)素?cái)?shù)定義，(p,a)=1或(p,a)=p，后者即p|a。

□56定理1.11設(shè)p為素?cái)?shù)，a,b為整數(shù)，若p|ab,則p|a或p|b。證明

由定理1.10，若p|a，得證。若p

a，則(p,a)=1。由定理1.5，存在整數(shù)s,t，使得sp+ta=1，所以，spb+tab=b。由于p|ab，因此p|b。

□57定理1.12（整數(shù)唯一分解定理）任意大于1的整數(shù)可以分解為素?cái)?shù)冪形式的乘積：，(1.12)這里p1<p2<…<pk為素?cái)?shù)，α1,α2,…,αk為正整數(shù)。若不考慮素?cái)?shù)的次序，這種分解是唯一的。式(1.12)稱(chēng)為a的標(biāo)準(zhǔn)分解式。58證明

首先證明標(biāo)準(zhǔn)分解式的存在性。若a是素?cái)?shù)，定理顯然成立。若a是合數(shù)，設(shè)q1是a的最小真因子，則q1一定是素?cái)?shù)（若q1不是素?cái)?shù)，則存在a的更小的真因子）。設(shè)a=q1a1,1<a1<a。同理，若a1是素?cái)?shù)，則分解完畢。59若a1是合數(shù)，則a1存在最小的素因子q2。設(shè)a=q1q2a2,1≤a2<a1。如此進(jìn)行下去，可得分解形式如下a=q1q2q3..qt。將相同的素?cái)?shù)乘積寫(xiě)成冪形式，即得,p1<p2<...<pk,αi≥1,i=1,2,…,k。(1.13)下面證明標(biāo)準(zhǔn)分解式的唯一性。假設(shè)存在a的另一組素?cái)?shù)分解

,q1<q2<...<qt,βi≥1,i=1,2,…,t。(1.14)60由定理1.11，任一pi必整除某一qj，反之，qj必整除pi，所以pi=qj，且k=t。于是，p1=q1,…,pk=qk。由式(1.13)與式(1.14)得。

(1.15)等式(1.15)左邊是素?cái)?shù)q1的倍數(shù)，而等式右邊不是q1的倍數(shù)，因此，只有α1=β1。同理可證αi=βi,i=1,2,…,k?！?1例1.11寫(xiě)出21,28,49,100的標(biāo)準(zhǔn)分解式。解

根據(jù)定理1.12，有21=3·7,28=22·7,49=72,100=22·52。唯一分解定理的直接應(yīng)用是可以求最大公因子與最小公倍數(shù)。62對(duì)于式(1.12)，如果正整數(shù)d滿(mǎn)足d|a，則d的標(biāo)準(zhǔn)分解式為,0≤γi≤αi,i=1,2,…,k。(1.16)反之，寫(xiě)成式(1.16)中形式的d，必有d|a。(1.12)63定理1.13設(shè)整數(shù)a>0,b>0，且,αi

≥0,i=1,2,…,k。,

βi≥0,i=1,2,…,k。則(a,b)=,di=min(αi,βi),i=1,2,…,k。(1.17)[a,b]=,mi=max(αi,βi),i=1,2,…,k。(1.18)其中符號(hào)min(α,β)表示α,β中較小的數(shù)，符號(hào)max(α,β)表示α,β中較大的數(shù)。64例1.12計(jì)算a=24×32×53×76×112,b=34×52×73×11×132的最大公因子與最小公倍數(shù)。解

根據(jù)定理1.13，有(a,b)=32×52×73×11，[a,b]=24×34×53×76×112×132。65例1.13

計(jì)算整數(shù)70,150,210,840的最大公因子和最小公倍數(shù)。解根據(jù)定理1.12，我們有70=2·5·7,150=2·3·52,210=2·3·5·7,840=23·3·5·7。定理1.13可推廣到多個(gè)整數(shù)的情況：(70,150,210,840)=2·5=10，[70,150,210,840]=23·3·52·7=4200。66若整數(shù)a,b比較大，通常難以分解，用標(biāo)準(zhǔn)分解式方法求兩個(gè)數(shù)的最大公因子或最小公倍數(shù)時(shí)，計(jì)算量太大。用輾轉(zhuǎn)相除法求最大公因子的優(yōu)點(diǎn)是，不必考慮整數(shù)的分解。671.6素?cái)?shù)有無(wú)窮多根據(jù)1.5節(jié)的素?cái)?shù)定義，2,3,5,7,11,13,…都是素?cái)?shù)。10以?xún)?nèi)的素?cái)?shù)有4個(gè)，100內(nèi)的素?cái)?shù)共有25個(gè)，1000以?xún)?nèi)的素?cái)?shù)有168個(gè)，…。關(guān)于素?cái)?shù)的個(gè)數(shù)，有以下定理。定理1.14素?cái)?shù)有無(wú)窮多個(gè)。證明

反證法。假設(shè)素?cái)?shù)是有限的，設(shè)p1=2,p2=3,…,pk是全體素?cái)?shù)。68令整數(shù)P=p1p2…pk+1，因?yàn)閜i

P,i=1,2,…,k，所以，P的任一素因子q不等于pi,i=1,2,…,k。于是，存在p1,p2,…,pk以外的素?cái)?shù)，假設(shè)錯(cuò)誤。故，素?cái)?shù)有無(wú)窮多個(gè)。

□69定理1.16（素?cái)?shù)定理）設(shè)π(x)表示不大于x的所有素?cái)?shù)個(gè)數(shù)，則有。(1.19)根據(jù)定理1.16，從不大于x的自然數(shù)中隨機(jī)選一個(gè)，它是素?cái)?shù)的概率大約是1/lnx。因，所以x越大，素?cái)?shù)分布越稀疏。70素?cái)?shù)的個(gè)數(shù)無(wú)窮多，但它的分布并不規(guī)則，尋找素?cái)?shù)是一個(gè)比較難的問(wèn)題。下面討論埃拉托斯特尼（Eratosthenes）篩法，適于尋找給定界限內(nèi)的素?cái)?shù)序列。71Eratosthenes篩法利用了這樣一條定理：定理1.17（素?cái)?shù)判斷定理）

如果n不能被不大于的任何素?cái)?shù)整除，則n是一個(gè)素?cái)?shù)。因此，要判斷n是否為素?cái)?shù)，只需判斷n能否被不大于的素?cái)?shù)整除即可。72例1.14求1~100以?xún)?nèi)的所有素?cái)?shù)。分析：只需刪除1和1~100內(nèi)的所有合數(shù)。根據(jù)定理1.17，1~100內(nèi)的所有合數(shù)必存在不超過(guò)=10的素因子。首先，找出10以?xún)?nèi)的所有素?cái)?shù)2,3,5,7。然后，保留2,3,5,7，刪除1以及2,3,5,7的所有其它倍數(shù)。剩下的數(shù)就是1~100以?xún)?nèi)的所有素?cái)?shù)，如下所示73故100內(nèi)的素?cái)?shù)共有25個(gè)，它們是2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97。74在密碼算法中往往使用大素?cái)?shù)，例如二進(jìn)制表示的五百位、甚至一千位以上的素?cái)?shù)。需要使用一些有效的素性檢測(cè)算法，來(lái)判斷一個(gè)隨機(jī)整數(shù)是否為素?cái)?shù)。實(shí)際中，判斷一個(gè)大整數(shù)是否為素?cái)?shù)要比分解一個(gè)大整數(shù)容易得多。

751.7麥?zhǔn)材鶖?shù)與費(fèi)馬數(shù)*

定義1.6設(shè)p是一個(gè)素?cái)?shù)，形如2p–1的數(shù)稱(chēng)為麥?zhǔn)材∕ersenne）數(shù)，記為Mp=2p–1。如果Mp是素?cái)?shù)，就稱(chēng)它為麥?zhǔn)材財(cái)?shù)。麥?zhǔn)材鶖?shù)不一定都是素?cái)?shù)，例如：M2=22?1=3、M3=23?1=7是素?cái)?shù)。M11=211?1=2047=23×89不是素?cái)?shù)。*

76定理1.18

若2n–1為素?cái)?shù)，則n必為素?cái)?shù)。證明

反證法。假設(shè)n=kl不是素?cái)?shù),k>1,l>1。于是，2n–1=2kl–1=(2k–1)(2k(l-1)+...+2+1)，而1<2k–1<2n–1，與題設(shè)矛盾，故n必為素?cái)?shù)?！跤啥ɡ?.18，形如2n–1的素?cái)?shù)，必為麥?zhǔn)材財(cái)?shù)。*

77十七世紀(jì)，法國(guó)數(shù)學(xué)家麥?zhǔn)材∕arinMersenne）證明了p=2,3,4,7,17,19,31時(shí)，Mp是素?cái)?shù)。目前，已知的麥?zhǔn)材財(cái)?shù)有48個(gè)，他們是p=2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213,19937,21701,23209,44497,86243,110503,132049,216091,756839,859433,1257787,1398269,2976221,3021377,6972593,13466917,20996011,24036583,25964951,30402457,32582657(#44),37156667,42643801,43112609,57885161(#48)?，F(xiàn)在還不知道在第44個(gè)麥?zhǔn)材財(cái)?shù)（M25,964,951）和第48個(gè)（M57,885,161）之間是否還存在未知的麥?zhǔn)材財(cái)?shù)。麥?zhǔn)材財(cái)?shù)在代數(shù)編碼等應(yīng)用學(xué)科中得到了應(yīng)用*

78定義1.7

設(shè)n是自然數(shù)，形如的數(shù)，稱(chēng)為費(fèi)馬（Fermat）數(shù)，記為。如果Fn是素?cái)?shù)，就稱(chēng)它為費(fèi)馬素?cái)?shù)。最小的五個(gè)費(fèi)馬數(shù)F0=3,F1=5,F2=17,F3=257,F4=65537，它們都是素?cái)?shù)。據(jù)此，1640年，法國(guó)數(shù)學(xué)家費(fèi)馬（Pierrede

Fermat）猜想Fn

(n=0,1,2,…)均為素?cái)?shù)。但在1732年，歐拉（LeonhardEuler）證明了F5=641×6700417是合數(shù)。*

79故費(fèi)馬猜想不正確，不能作為求素?cái)?shù)公式。之后，人們又陸續(xù)找到了不少反例，如F6=274177×67280421310721不是素?cái)?shù)。至今，這樣的反例共找到了243個(gè)，卻還沒(méi)有找到第6個(gè)正面的例子。也就是說(shuō)，目前只知道n=0,1,2,3,4這5個(gè)情況下，F(xiàn)n才是素?cái)?shù)。于是，有人推測(cè)，僅存在有限個(gè)費(fèi)馬素?cái)?shù)。甚至有人猜想：n>4時(shí)，費(fèi)馬數(shù)全是合數(shù)。*

80實(shí)際上幾千年來(lái)，數(shù)學(xué)家們一直在尋找這樣一個(gè)公式，能給出所有素?cái)?shù)；但直到現(xiàn)在，誰(shuí)也未能找到這樣的公式，而且也未能找到證據(jù)，說(shuō)這樣的公式一定不存在；這樣的公式是否存在，成了一個(gè)著名的數(shù)學(xué)難題。*

81在二進(jìn)制的計(jì)算機(jī)運(yùn)算中，麥?zhǔn)材鶖?shù)和費(fèi)馬數(shù)可用來(lái)提高某些運(yùn)算的效率。例如，計(jì)算整數(shù)c除以麥?zhǔn)材鶖?shù)Mp的余數(shù)，二進(jìn)制表示的c容易寫(xiě)成

c=c0+2pc1+22pc2+...+2kpck,0≤ci<2p,i=1,2,…,k。因而，

c=(2kp–1)ck+(2kp-1–1)ck-1+...+(2p–1)c1+ck+ck-1+…+c1+c0。c除以Mp的余數(shù)與ck+ck-1+…+c1+c0除以Mp的余數(shù)相同，將除法運(yùn)算轉(zhuǎn)化成加法運(yùn)算。若ck+ck-1+…+c1+c0>Mp，重復(fù)使用上述方法，即得c除以Mp的余數(shù)。關(guān)于費(fèi)馬數(shù)，可使用類(lèi)似方法實(shí)現(xiàn)快速除法運(yùn)算。*

821.8素?cái)?shù)的著名問(wèn)題*關(guān)于素?cái)?shù)有很多世界級(jí)難題，例如孿生素?cái)?shù)、哥德巴赫猜想等。孿生素?cái)?shù)是指一對(duì)素?cái)?shù)，兩素?cái)?shù)之差是2。例如3和5，5和7，11和13，17和19，…，101和103，…，10016957和10016959等等都是孿生素?cái)?shù)。*

83即使是大素?cái)?shù)，也有可能是孿生素?cái)?shù)。通過(guò)窮舉計(jì)算發(fā)現(xiàn)：在小于1015的29,844,570,422,669個(gè)素?cái)?shù)中，有1,177,209,242,304對(duì)孿生素?cái)?shù)，占了3.94%。孿生素?cái)?shù)猜想：存在無(wú)窮多個(gè)素?cái)?shù)p，使得p+2也是素?cái)?shù)。84孿生素?cái)?shù)猜想是數(shù)論中著名的未解決問(wèn)題。這個(gè)猜想由希爾伯特在1900年巴黎國(guó)際數(shù)學(xué)家大會(huì)的報(bào)告上第8個(gè)問(wèn)題中提出，可以描述為“存在無(wú)窮多對(duì)孿生素?cái)?shù)”。該問(wèn)題尚未解決。至2011年底，發(fā)現(xiàn)的最大的孿生素?cái)?shù)是：（3756801695685·2666669–1,3756801695685·2666669+1）,這對(duì)素?cái)?shù)中的每個(gè)都長(zhǎng)達(dá)200700位。*

85孿生素?cái)?shù)方面迄今最好的結(jié)果是1966年由已故的中國(guó)數(shù)學(xué)家陳景潤(rùn)利用篩法（sievemethod）取得。陳景潤(rùn)證明了：存在無(wú)窮多個(gè)素?cái)?shù)p，使得p+2要么是素?cái)?shù)，要么是兩個(gè)素?cái)?shù)的乘積。孿生素?cái)?shù)猜想可以弱化為“能不能找到一個(gè)正數(shù)，使得有無(wú)窮多對(duì)素?cái)?shù)之差小于這個(gè)給定的正數(shù)”，在孿生素?cái)?shù)猜想中，這個(gè)正數(shù)就是2。華人數(shù)學(xué)家張益唐找到的正數(shù)是“7000萬(wàn)”。*

862013年5月14日，《自然》（Nature）雜志在線報(bào)道，美國(guó)新罕布什爾大學(xué)的華人數(shù)學(xué)家張益唐證明了“存在無(wú)窮多個(gè)之差小于7000萬(wàn)的素?cái)?shù)對(duì)”，這一研究被認(rèn)為在孿生素?cái)?shù)猜想這一數(shù)論問(wèn)題上取得了重大突破。*

87哥德巴赫猜想（也稱(chēng)為“1+1”問(wèn)題）是數(shù)論中存在最久的未解問(wèn)題之一，也是希爾伯特第8個(gè)問(wèn)題中的一個(gè)子問(wèn)題。這個(gè)猜想最早出現(xiàn)在1742年普魯士數(shù)學(xué)家哥德巴赫寫(xiě)給瑞士數(shù)學(xué)家歐拉的通信中。哥德巴赫猜想可以陳述為：“任一大于2的偶數(shù)，都可表示成兩個(gè)素?cái)?shù)之和?！崩?，4=2+2,8=3+5,10=5+5,12=5+7,14=7+7,16=3+13,18=5+13,…。*

88目前最好的結(jié)果是陳景潤(rùn)在1973年發(fā)表的陳氏定理（也稱(chēng)為“1+2”定理），即“任一充分大的偶數(shù)都可以表示成二個(gè)素?cái)?shù)的和，或是一個(gè)素?cái)?shù)與兩個(gè)素?cái)?shù)積的和?！庇猛ㄋ椎脑捳f(shuō)就是，大偶數(shù)=素?cái)?shù)+素?cái)?shù)，或大偶數(shù)=素?cái)?shù)+素?cái)?shù)*素?cái)?shù)。數(shù)學(xué)的猜想和難題，有的在提出后不久便被解決，有的尚未解決，數(shù)學(xué)家們?cè)谘芯窟@些的猜想和難題的過(guò)程中，推動(dòng)了數(shù)學(xué)的發(fā)展。*

8990作業(yè)習(xí)題12,3,8(1),11,17,21,24,25,31。919191

謝謝！92第2章同余式同余描述兩個(gè)整數(shù)之間的一種關(guān)系，是數(shù)論中的一個(gè)基本概念，首先由高斯引入，是數(shù)論中一個(gè)內(nèi)容豐富的分支，數(shù)論中的很多問(wèn)題直接或間接地應(yīng)用了同余理論。9393第2章同余式2.1同余的定義2.2剩余類(lèi)2.3歐拉函數(shù)2.4同余方程2.5中國(guó)剩余定理2.6RSA公鑰密碼體制94重點(diǎn)內(nèi)容概念同余、剩余類(lèi)、完全剩余系定理歐拉定理、費(fèi)馬定理、中國(guó)剩余定理、算法RSA算法952.1同余的定義定義2.1給定一個(gè)正整數(shù)m，若用m分別去除兩個(gè)整數(shù)a,b所得的余數(shù)相同，則稱(chēng)a與b模m同余，記作a≡b(modm)。如果余數(shù)不同，就稱(chēng)a,b模m不同余，記作a?b(modm)。例2.1739除以7的余數(shù)是4，18除以7的余數(shù)也是4，所以，739≡18(mod7)以及739≡4(mod7)。同樣，1623≡7(mod8),1623≡15(mod8)。96定理2.1

整數(shù)a,b模m同余的充要條件是m|a–b。證明

設(shè)a=k1m+ra,b=k2m+rb,0≤ra,rb

<m,k1,k2為整數(shù)。“=>”若a,b模m同余，由定義2.1，得ra=rb。于是，a–b=(k1–k2)m，即m|a–b。97“<=”m|a–b=>m|(k1–k2)m+(ra–rb)=>m|ra–rb。因?yàn)楱Cm<ra–rb

<m，所以，只有ra=rb。故，a與b模m同余。

□推論2.1a≡b(modm)，當(dāng)且僅當(dāng)存在整數(shù)k，使得a=km+b。98例2.2因?yàn)?|739–18,所以739≡18(mod7)。因?yàn)?|162–22，所以162≡22(mod7)。731=101·7+24，根據(jù)推論2.1，731≡24(mod7)。顯然，同余是一個(gè)等價(jià)關(guān)系：(1)a≡a(modm)；（自反性）(2)若a≡b(modm)，則b≡a(modm)；（對(duì)稱(chēng)性）(3)若a≡b(modm)，b≡c(modm)，則a≡c(modm)；（傳遞性）99定理2.2設(shè)a,b,d,a1,a2,b1,b2,m為整數(shù)，則有以下性質(zhì)(1)若a1≡b1(modm),a2≡b2(modm)，則①a1+a2≡b1+b2(modm),a1–a2≡b1–b2(modm)；②a1a2≡b1b2(modm)；(2)若a≡b(modm)，n為正整數(shù)，則an≡bn(modm)；進(jìn)一步，有f(a)≡f(b)(modm)，其中f(x)為一個(gè)整系數(shù)多項(xiàng)式；100(3)設(shè)ad≡bd(modm)，若(d,m)=1，則a≡b(modm)；(4)設(shè)a≡b(modm)，若d|m，則a≡b(modd)；(5)設(shè)a≡b(modm)，若d是a,b,m的公因子，則；(6)若a≡b(modmi)，i=1,2,...,k，則a≡b(mod[m1,m2,...,mk])；(7)若a≡b(modm)，則(a,m)=(b,m)。101證明

(1)若a1≡b1(modm),a2≡b2(modm)，則存在k1,k2

∈

Z，使得a1=k1m+b1,a2=k2m+b2。于是，①a1+a2=(k1+k2)m+b1+b2。因此，a1+a2≡b1+b2(modm)。同理，a1–a2≡b1–b2(modm)。②a1a2=(k1k2m+b1k2+b2k1)m+b1b2，由推論2.1知，a1a2≡b1b2(modm)。102(2)類(lèi)似(1)中②的證明即得。(3)若ad≡bd(modm)，則m|(a–b)d。由定理1.6，因?yàn)?d,m)=1，所以m|(a–b)，即a≡b(modm)。103(4)若a≡b(modm)，則m|a–b。因?yàn)閐|m，所以d|a–b。。因此，a≡b(modd)。(5)若a≡b(modm)，則存在k∈

Z，使得a=km+b。由于d是a,b,m的公因子，于是。故，。104(6)若a≡b(modmi)，i=1,2,...,k，即mi|(a–b),i=1,2,...,k。由最小公倍數(shù)定義1.5知，[m1,m2,...,mk]|a–b，故，a≡b(mod[m1,m2,...,mk])。(7)若a≡b(modm)，則存在k

∈

Z，使得a=km+b。由定理1.2，有(a,m)=(b,m)。□105例2.3

已知3≡703(mod7),5≡75(mod7)，則3+5≡703+75(mod7)以及3×5≡703×75(mod7)。已知6≡496(mod7)，因?yàn)?2,7)=1，由定理2.2的(3)，所以3≡248(mod7)。已知6≡286(mod14)，因?yàn)?|14，所以6≡286(mod7)。

106已知6≡286(mod14)，2|6,2|286,2|14，由定理2.2的(4)，所以3≡143(mod7)。已知12≡1212(mod12),12≡1212(mod10)，因?yàn)閇12,10]=60，根據(jù)定理2.2的(6)得，12≡1212(mod60)。對(duì)任意的整數(shù)k，有2≡10k+2(mod10)，根據(jù)定理2.2的(7)得，(2,10)=(10k+2,10)。107例2.4求證：(1)8|(472131+17)；(2)8|(52n+7)；(3)127|(193000–1)。證(1)因?yàn)?7=6×8–1，472131=k×8–1（k為某整數(shù)）。于是472131+17=k×8+16。所以，8|(472131+17)。(2)52n=25n=(3×8+1)n=k×8+1（k為某整數(shù)）。所以，8|(52n+7)。(3)因?yàn)?96≡1(mod127)，所以127|(193000–1)。108例2.5證明，一個(gè)十進(jìn)制數(shù)被9除的余數(shù)，等于它的各位數(shù)之和被9除的余數(shù)。證設(shè)這個(gè)十進(jìn)制數(shù)為A=anan-1…a2a1a0，于是A(mod9)=((11…11)×9+1)an+((1…11)×9+1)an-1+…+(11×9+1)a2+(1×9+1)a1+a0(mod9)=an+an-1+…+a2+a1+