第二次课-- 整除与同余

《第二次课-- 整除与同余》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章整除与同余第一章整除与同余主要内容整除的基本概念（掌握）素数（掌握）同余的概念（掌握）1.1整除定义1：设a，b是任意两个整数，其中b0，如果存在一个整数q，使a=qb，则我们称b整除a，或a被b整除，记为ba，此时称b是a的因子，a是b的倍数．例1：a=10,b=2则有210；若a=100,b=10有10100例2：设a是整数，a0,则a0．即0是任意整数的倍数整除的基本性质：如果ba且ab，则b=a或b=a．如果ab且bc，则ac．如果ca且cb，则cua+vb，其中

2、u，v是整数．整除的基本性质（证明）：证明：（1）由ba，根据整除定义我们可以得出：存在整数q1使a=q1b，同理；由ab，则存在整数q2使b=q2a．于是a=q1b=q2q1a．所以q2q1=1，由于q1，q2是整数，则q2=q1=1，或q2=q1=1．故b=a或b=a．命题得证。性质1：如果ba且ab，则b=a或b=a．整除的基本性质（证明）：证明：（2）因为ab，则存在整数q1，使b=q1a①又因为bc，则存在整数q2，使c=q2b②于是将①式带入②式有：c=q2b=q1q2a=qa

3、，其中q=q1q2．故ac．性质2：如果ab且bc，则ac整除的基本性质（证明）：证明：（3）因为ca，则存在整数q1，使a=q1c①两边同乘以整数u，有ua=p1c(其中p1=uq1)②同理cb，有vb=p2c(其中p2=vq2)③②+③得出：pc=ua+vb其中p=p1+p2=uq1+vq2，故cua+vb．性质3：如果ca且cb，则cua+vb，其中u，v是整数整除的基本性质（补充）：(1)ab<=>-ab<=>a-b<=>-a-b<=>abb≠0且ab=>a

4、≤b带余除法：当两个整数不能整除时，我们有带余除法：对于a，b两个整数，其中b0，则存在唯一q，r使得：a=bq+r，0≤r<

5、b

6、．r称为a被b除得到的余数．显然当r=0时，ba．证明带余除法：例31）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是两个整数，如果整数ca且cb，则c称为a，b的公因子．2）设c0是两个不全为零的整数a，b的公因子，如果a，b的任何公因子都整除c，则c称

7、为a，b的最大公因子，记为c=(a，b)．最大公因子（性质）简单性质：(a,b)=(-a,b)=(a,-b)=(-a,-b)(0,a)=a最大公因子（求解）方法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=b;r1=q2r2+r3，0≤r3＜r2;…rn-2=qn-1rn-1+

8、rn，0≤rn＜rn-1;rn-1=qnrnrn=(a，b)此方法扩展可用于求元素的逆元欧几里德算法原理（1）rn可以整除rn-1,rn-2，…..,r2,r1,r0,所以rn是a,b的公因子。(2)若d整除r0,r1,则d整除r2，r3，…..,rn-2,rn-1,rn。故，rn是（a,b）的最大公因子。最大公因子（求解）例5：(3824，1837)=？(3824，1837)=(3824，1837)．3824=21837+1501837=12150+37150=437+237=182+12=2

9、1得(3824，1837)=1，故(3824，1837)=1．最大公因子定理定理1设a，b是两个不全为零的整数，则存在两个整数u，v，使(a，b)=ua+vb．证明设Z是全体整数集合，构造如下一个集合：S={xa+ybx，yZ}．S中的元素显然大于等于0．设d是S中的最小正整数，设d=ua+vb．现在我们证明da且db．做带余除法：a=qd+r，0rd．于是r=a–qd=a–q(ua+vb)=(1–qu)a–qvb．这说明r也可表示为a，b的组合，则rS．由于d是S中的最小者，所以r=

10、0．故da．同理db．设c是a，b的任意公因子，由ca和cb得cua+vb．故d是a，b的最大公因子，证毕．最大公因子定理例6：将a=888，b=312的最大公因子表示为(a，b)=ua+vb解利用欧几里得除法求最大公因子的过程可以解出．888=2312+264312=1264+48264=548+2448=224我们有：264=888231248=312264=312(888231