第一章-整除与同余

信息安全数学基础任课教师：李发根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(