信息安全數學基礎任課教師：李發根E-mail:fagenli@上課時間：周一1,2節（8:30分開始）(雙周)，周三5,6節(2:30分開始)學時：48教材：許春香，周俊輝,信息安全數學基礎,電子科技大學出版，2008成績構成：平時20%+期中10%+期末閉卷考試70%第一章整除與同余第一章整除與同余主要內容整除的基本概念（掌握）素數（掌握）同余的概念（掌握）1.1整除定義1：設a，b是任意兩個整數，其中b0，如果存在一個整數q，使a=qb，則我們稱b整除a，或a被b整除，記為ba，此時稱b是a的因子，a是b的倍數．例1：a=10,b=2則有210；若a=10,b=100有10100例2：設a是整數，a

0,則a0．即0是任意整數的倍數注：定義1并沒有指明整數a,b是否可以是負數！所以，a,b可以是負數！例2’：設a是整數，則(-)1a．即(-)1是任意整數的因子整除的基本性質：如果ba且ab，則b=a或b=a．如果ab且bc，則ac．如果ca且cb，則cua+vb，其中u，v是整數．整除的基本性質（證明）：證明：（1）由ba，根據整除定義我們可以得出：存在整數q1使a=q1b

，同理；由ab，則存在整數q2使b=q2a．于是a=q1b=q2q1a．所以q2q1=1，由于q1，q2是整數，則q2=q1=1，或q2=q1=1．故b=a或b=a．命題得證。性質1：如果ba且ab，則b=a或b=a．整除的基本性質（證明）：證明：（2）因為ab，則存在整數q1，使b=q1a①又因為bc，則存在整數q2，使c=q2b②于是將①式帶入②式有：c=q2b=q1q2a=qa，其中q=q1q2．故ac．性質2：如果ab且bc，則ac整除的基本性質（證明）：證明：（3）因為ca，則存在整數q1，使a=q1c①兩邊同乘以整數u，有ua=p1c(其中p1=uq1)②同理cb，有vb=p2c(其中p2=vq2)③②+③

得出：pc=ua+vb其中p=p1+p2=uq1+vq2

，故cua+vb．性質3：如果ca且cb，則cua+vb，其中u，v是整數整除的基本性質（補充）：(1)ab<=>-ab<=>a-b<=>-a-b<=>ab（2）b≠0且ab=>a≤b

帶余除法當兩個整數不能整除時，我們有帶余除法：對于a，b兩個整數，其中b0，則存在唯一q，r使得：

a=bq+r，0≤

r

<|b|．r稱為a被b除得到的余數．顯然當r=0時，ba．帶余除法：例3

1）a=–37，b=5，則–37=(8)5+3，r=3．2）a=67，b=7，則67=(9)(7)+4，r=4．最大公因子（定義）定義2：1）設a，b是兩個整數，如果整數ca且cb，則c稱為a，b的公因子．2）設c0是兩個不全為零的整數a，b的公因子，如果a，b的任何公因子都整除c，則c稱為a，b的最大公因子，記為c=(a，b)．最大公因子（性質）簡單性質：(a,b)=(-a,b)=(a,-b)=(-a,-b)(0,a)=|a|(1,a)=1最大公因子（求解）方法1：因子分解例4：a=60=2×2×3×5，b=36=2×2×3×3觀察得：c=（a，b）=2×2×3=12方法2（一般方法）：歐幾里德除法也稱為輾轉相除法。最大公因子（求解）歐幾里德除法（輾轉相除法）：已知a，b，使r0=a，r1=b，r0=q1r1+r2，0≤r2＜r1;r1=q2r2+r3，0≤r3＜r2;…rn-2=qn-1rn-1+rn，0≤rn＜rn-1;rn-1=qnrnrn=（a，b）此方法擴展可用于求元素的逆元最大公因子（求解）例5：(3824，1837)=？

(3824，1837)=(3824，1837)．3824=21837+1501837=12150+37150=437+237=182+12=21

得(3824，1837)=1，故(3824，1837)=1．最大公因子定理定理1

設a，b是兩個不全為零的整數，則存在兩個整數u，v，使d=ua+vb．（其中d=(a，b)）證明1已知a，b，使r0=a，r1=b，r0=q1r1+r2，0≤r2＜r1;r1=q2r2+r3，0≤r3＜r2;…rn-3=qn-2rn-2+rn-1rn-2=qn-1rn-1+rn，0≤rn＜rn-1;

rn-1=qnrnrn=（a，b）rn=(*1)(r0-q1r1)

+(*2)

r1

=(*1)r0

+(*2-q1)

r1;rn=(*1)r2+

(*2)

r1;…rn=rn-2-qn-1(rn-3-qn-2rn-2)

=(1-qn-2qn-1)

rn-2-qn-1rn-3rn=rn-2-qn-1rn-1rn=（a，b）最大公因子定理證明證明設Z是全體整數集合．做一個如下集合：S={xa+ybx，yZ}．S中的元素顯然大于等于0．設d是S中的最小正整數，則d可表示為a，b的組合，設d=ua+vb．現在我們證明da且db．做帶余除法：a=qd+r，0

r

d．于是r=a–qd=a–q(ua+vb)=(1–qu)a–qvb．這說明r也可表示為a，b的組合，則rS．由于d是S中的最小正整數，所以只有r=0．故da．同理db．設c是a，b的任意公因子，由ca和cb得cd=ua+vb．故d是a，b的最大公因子，證畢．a,b最大公因子1、是a,b的公因子2、是最大的，即a,b的任意公因子都是最大公因子的因子最大公因子定理例6：將a=888，b=312的最大公因子表示為(a，b)=ua+vb

解利用歐幾里得除法求最大公因子的過程可以解出．888=2312+264312=1264+48264=548+24我們有：264=888231248=312264=312(8882312)=–888+331224=264548=(8882312)5(–888+3312)=688817312故(888，312)=24=688817312．最大公因子（推廣的定義）定義2：1）設a1，…,an是n個整數，如果整數cai，則c稱為a1，…,an的公因子．2）設c0是n個不全為零的整數a1，…,an的公因子，如果a1，…,an的任何公因子都整除c，則c稱為a，b的最大公因子，記為c=(a1，…,an)．互素定義3：a，b是兩個整數，如果(a，b)=1，則稱a，b互素．推論：a，b互素的充分必要條件是：存在u，v，使ua+vb=1．證明必要條件是定理1的特例，只需證充分條件．如果存在u，v，使ua+vb=1．則由(a，b)(ua+vb)，得(a，b)1，所以(a，b)=1．整除性質3互素（性質）互素有如下性質：1）如果cab且(c，a)=1，則cb．2）如果ac，bc，且(a，b)=1，則abc．3）如果(a，c)=1，(b，c)=1，則(ab，c)=1．互素性質證明證明1）因為(c，a)=1，存在u，v屬于Z，使ua+vc=1，兩端乘b得uab+vbc=b．由cab，cbc，得cuab，cvbc，故cb．性質1：如果cab且(c，a)=1，則cb．互素性質證明證明2）因為(a，b)=1，存在u，v，使ua+vb=1，兩端乘c得uac+vbc=c．由于ac，bc,故abvbc,abuac,所以abc．性質2：如果ac，bc，且(a，b)=1，則abc．互素性質證明證明3）因為(a，c)=1，存在u，v，使ua+vc=1，因為(b，c)=1，存在r，s，使rb+sc=1，于是(ua+vc)(rb+sc)=(ur)ab+(usa+vrb+vsc)c=1．故(ab，c)=1．

性質3：如果(a，c)=1，(b，c)=1，則(ab，c)=1互素（推廣的定義）定義3：a1，…,an是n個整數，如果(a1，…,an)=1，則稱a1，…,an互素．公倍數，最小公倍數定義4設a，b是兩個不等于零的整數．如果ad，bd，則稱d是a和b的公倍數．a和b的正公倍數中最小的稱為a和b的最小公倍數，記為[a，b]．顯然，[a，b]=[–a，b]=[a，–b]=[–a，–b]．例8

a=2，b=3．它們的公倍數集合為{0，6，12，18，…}．而[2，3]=6．公倍數，最小公倍數

最小公倍數與最大公約數關系定理2

1）設d是a，b的任意公倍數，則[a，b]d．2），特別地，如果(a，b)=1，[a，b]=|ab|．定理2證明證明1）做帶余除法：d=q[a，b]+r，0r[a，b]，由于ad，以及a[a，b]，則ar，

r也是a的倍數，同理r也是b的倍數，即r也是a,b的公倍數。因為[a，b]是a，b的最小公倍數（最小的，且正），所以r=0，故[a，b]d．

定理2證明2）不失一般性，假設a，b均是正整數．我們現在證明是a，b的公倍數而且對于a，b的任意公倍數d都有設a=ka(a，b)，b=kb(a，b)，其中(ka，kb)=1．則

=kab=kba，所以是a，b的公倍數．設a，b的任意公倍數d=qaa=qbb，于是定理2證明d=qaka(a，b)=qbkb(a，b)，qaka=qbkb．因為(ka，kb)=1，則kaqb，kabqbb=d，這表明是公倍數中最小的，定理得證．最小公倍數與最大公約數關系例9

a=888，b=312，求[a，b]．解

(888，312)=24，則[888，312]==11544．a,b最小公倍數1、是a,b的公倍數2、是最小的，即a,b的任意公倍數都是最小公倍數的倍數求最小公倍數先求最大公因子再求最小公倍數1.2素數定義1如果一個大于1的整數p除1和p外無其他因子，則p稱為一個素數，否則稱為合數．定理1設p是一個素數，則1）對任意整數a，如果p不整除a，則(p，a)=1．2）如果pab，則pa，或pb．1.2素數證明

1）因為(p，a)p，由素數的定義，(p，a)=1，或者(p，a)=p．因為p不整除a，所以(p，a)p．故(p，a)=1．

2）如果pa，則成立．否則(p，a)=1，則由互素的性質，有pb．算術基本定理定理2

（算術基本定理）每個大于1的整數a都可以分解為有限個素數的乘積：

a=p1

p2…pr．該分解除素數因子的排列外是唯一的．證明:分解是顯然的，我們只需證明分解除素數因子的排列外是唯一的．假設a有兩個分解：

a=p1p2…pr=q1q2…qs．由于p1q1q2…qs，則p1整除q1，q2，…，qs之一，不失一般性，假設p1q1，由p1，q1都是素數得p1=q1．在等式兩邊消去p1，q1，得p2…pr=q2…qs．重復上述過程可得p1p2…pr和q1q2…qs除排列外是相同的，證畢．標準因子分解式

由于p1，p2，…，pr中可能存在重復，所以a的分解式可表示為有限個素數的冪的乘積：

a=p1k1p2k2…pmkm．這稱為a的標準因子分解式．例

2100的標準因子分解式：2100=223557=223152

71．試分解n=32954765761773295963Eratosthenes篩法

定理3設a是任意大于1的整數，則a的除1外最小正因子q是素數，并且當a是合數時，證明由算術基本定理，該定理的前一點是顯然的．當a是一合數時，可設a=a1q，其中a1q，則a=a1q

q2，定理證畢．求不超過100的全部素數．第1步找出的全部素數：2，3，5，7．第2步在1～100中分別劃去第1步找出的每個素數的全部倍數：分別劃去2的全部倍數、3的全部倍數、5的全部倍數和7的全部倍數．（1）劃去2的全部倍數：

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100Eratosthenes篩法Eratosthenes篩法得到剩下的數：

123579111315171921232527293133353739414345474951535557596163656769717375777981838587899193959799Eratosthenes篩法（2）劃去3的全部倍數：

123579111315171921232527293133353739414345474951535557596163656769717375777981838587899193959799Eratosthenes篩法得到剩下的數：

12357111317192325293135374143474953555961656771737779838589Eratosthenes篩法

同理可以將因子5，7的倍數劃去：（3）劃去5的全部倍數：（4）劃去7的全部倍數：最終經過上述步驟后剩下的數除1外就是不超過100的全部素數：（25個）

2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97Eratosthenes篩法對于一般N，Eratosthenes篩法可表述如下：第1步找出的全部素數：p1，p2，…，pm．第2步在1~N中分別劃去p1，p2，…，pm全部倍數．第2步完成后剩下的數除1外就是不超過N的全部素數．篩法原理如下：對于一個數aN，如果p1，p2，…，pm都不整除a，則a是素數．這是因為如果a是合數，則由定理3，它必有一素因子在p1，p2，…，pm中．素數無窮個素數總共有多少個呢？古希臘的數學家回答了這個問題．定理1.2.4素數有無窮多個．證明用反證法．假設素數是有限個，設它們為：p1，p2，…，pk．令M=p1p2…pk+1，且設M為合數（？）．設p是M的一個素因子，則pM，而p在p1，p2，…，pk中，則pp1p2…pk，于是p

(M

p1p2…pk)，而M

p1p2…pk=1，因為p1，這顯然是不可能的，所以p不在p1，p2，…，pk中．定理得證．1.3同余定義1

給定一個稱為模的正整數m．如果m除整數a，b得相同的余數，即a=q1m+r，b=q2m+r，0

r

m，則稱a和b關于模m同余，記為a

b(modm)．

例1.3.1

251(mod8)，16

5(mod7)．1.3同余定理1.3.1整數a，b對模m同余的充分必要條件是：m(ab)，即a=b+mt，t是整數．1.3同余證明設a=q1m+r1，0

r1m，b=q2m+r2，0

r2m．（必要性）如果a

b(modm)，則r1=r2因此ab=m(q1q2)，m(ab)．（充分性）如果m(ab)，則mm(q1q2)+(r1r2)，于是m(r1r2)．由于|r1r2|m，故(r1r2)=0，r1=r2．證畢。

同余性質及推論同余具有下列性質：如果a1

b1(modm)，a2

b2(modm)，則1）a1+a2

b1+b2(modm)，2）a1a2

b1b2(modm)，3）a1a2

b1b2(modm)，4）如果ac

bc(modm)，且(c，m)=1，則a

b(modm)，5）如果a

b(modm)，且dm，d是正整數，則a

b(modd)．

同余性質及推論由a1

b1(modm)，a2

b2(modm)，得m(a1b1)，m(a2b2)，則1）m(a1b1)+(a2b2)=(a1+a2)(b1+b2)，故a1+a2

b1+b2(modm)．2）m(a1b1)(a2b2)=(a1a2)(b1b2)，故a1a2

b1b2(modm)．3）ma2(a1b1)+b1(a2b2)=a1a2

b1b2，故a1a2

b1b2(modm)．4）由ac

bc(modm)，得macbc=c(ab)，因為(c，m)=1，則m(ab)，a

b(modm)．5）由a

b(modm)，得m(ab)，而dm，則dm(ab)，a

b(modd)．證畢．

同余性質及推論推論如果a1

b1(modm)，a2

b2(modm)，則1）a1x+a2y

b1x+b2y(modm)，其中x，y是任意整數．2）a1n=b1n(modm)，其中n是正整數．3）f(a1)

f(b1)(modm)，其中f(x)是任一給定的整系數多項式：f(x)=c0+c1x+…+ckxk．推論的證明留做習題．同余應用例1.3.2

求264(mod641)解28=256，216=65536154(