第一章-整除與同余

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

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

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

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

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

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

a=bq+r，0≤

r

<|b|．r稱為a被b除得到的余數(shù)．顯然當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）設(shè)a，b是兩個整數(shù)，如果整數(shù)ca且cb，則c稱為a，b的公因子．2）設(shè)c0是兩個不全為零的整數(shù)a，b的公因子，如果a，b的任何公因子都整除c，則c稱為a，b的最大公因子，記為c=(a，b)．最大公因子（性質(zhì)）簡單性質(zhì)：(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（一般方法）：歐幾里德除法也稱為輾轉(zhuǎn)相除法。最大公因子（求解）歐幾里德除法（輾轉(zhuǎn)相除法）：已知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

設(shè)a，b是兩個不全為零的整數(shù)，則存在兩個整數(shù)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）最大公因子定理證明證明設(shè)Z是全體整數(shù)集合．做一個如下集合：S={xa+ybx，yZ}．S中的元素顯然大于等于0．設(shè)d是S中的最小正整數(shù)，則d可表示為a，b的組合，設(shè)d=ua+vb．現(xiàn)在我們證明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中的最小正整數(shù)，所以只有r=0．故da．同理db．設(shè)c是a，b的任意公因子，由ca和cb得cd=ua+vb．故d是a，b的最大公因子，證畢．a(chǎn),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）設(shè)a1，…,an是n個整數(shù)，如果整數(shù)cai，則c稱為a1，…,an的公因子．2）設(shè)c0是n個不全為零的整數(shù)a1，…,an的公因子，如果a1，…,an的任何公因子都整除c，則c稱為a，b的最大公因子，記為c=(a1，…,an)．互素定義3：a，b是兩個整數(shù)，如果(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．整除性質(zhì)3互素（性質(zhì)）互素有如下性質(zhì)：1）如果cab且(c，a)=1，則cb．2）如果ac，bc，且(a，b)=1，則abc．3）如果(a，c)=1，(b，c)=1，則(ab，c)=1．互素性質(zhì)證明證明1）因為(c，a)=1，存在u，v屬于Z，使ua+vc=1，兩端乘b得uab+vbc=b．由cab，cbc，得cuab，cvbc，故cb．性質(zhì)1：如果cab且(c，a)=1，則cb．互素性質(zhì)證明證明2）因為(a，b)=1，存在u，v，使ua+vb=1，兩端乘c得uac+vbc=c．由于ac，bc,故abvbc,abuac,所以abc．性質(zhì)2：如果ac，bc，且(a，b)=1，則abc．互素性質(zhì)證明證明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．

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

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

最小公倍數(shù)與最大公約數(shù)關(guān)系定理2

1）設(shè)d是a，b的任意公倍數(shù)，則[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的倍數(shù)，同理r也是b的倍數(shù)，即r也是a,b的公倍數(shù)。因為[a，b]是a，b的最小公倍數(shù)（最小的，且正），所以r=0，故[a，b]d．

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

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

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

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

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

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

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

a=p1

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

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

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

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

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

71．試分解n=32954765761773295963Eratosthenes篩法

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

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

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100Eratosthenes篩法Eratosthenes篩法得到剩下的數(shù)：

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

123579111315171921232527293133353739414345474951535557596163656769717375777981838587899193959799Eratosthenes篩法得到剩下的數(shù)：

12357111317192325293135374143474953555961656771737779838589Eratosthenes篩法

同理可以將因子5，7的倍數(shù)劃去：（3）劃去5的全部倍數(shù)：（4）劃去7的全部倍數(shù)：最終經(jīng)過上述步驟后剩下的數(shù)除1外就是不超過100的全部素數(shù)：（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步找出的全部素數(shù)：p1，p2，…，pm．第2步在1~N中分別劃去p1，p2，…，pm全部倍數(shù)．第2步完成后剩下的數(shù)除1外就是不超過N的全部素數(shù)．篩法原理如下：對于一個數(shù)aN，如果p1，p2，…，pm都不整除a，則a是素數(shù)．這是因為如果a是合數(shù)，則由定理3，它必有一素因子在p1，p2，…，pm中．素數(shù)無窮個素數(shù)總共有多少個呢？古希臘的數(shù)學家回答了這個問題．定理1.2.4素數(shù)有無窮多個．證明用反證法．假設(shè)素數(shù)是有限個，設(shè)它們?yōu)椋簆1，p2，…，pk．令M=p1p2…pk+1，且設(shè)M為合數(shù)（？）．設(shè)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

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

r

m，則稱a和b關(guān)于模m同余，記為a

b(modm)．

例1.3.1

251(mod8)，16

5(mod7)．1.3同余定理1.3.1整數(shù)a，b對模m同余的充分必要條件是：m(ab)，即a=b+mt，t是整數(shù)．1.3同余證明設(shè)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．證畢。

同余性質(zhì)及推論同余具有下列性質(zhì)：如果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是正整數(shù)，則a

b(modd)．

同余性質(zhì)及推論由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)．證畢．

同余性質(zhì)及推論推論如果a1

b1(modm)，a2

b2(modm)，則1）a1x+a2y

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

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

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