资源描述:
《《整除性辗转相除》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第五章数论基础第五章数论基础§5.1整除性辗转相除§5.2互质质因数分解§5.3合同一次同余式§5.4秦九韶定理Euler函数§5.5一元高次同余式二次剩余§5.1.1整除及其性质定义5.1.1设a和b是任意整数,若存在整数c,使得a=bc,则说a是b的倍数,b是a的因数。或者说a被b整除,而b整除a。记为b
2、a。显然,任意数整除0,特别0
3、0;1(-1)整除任意整数。定理5.1.1对任意整数a和b,b0,唯一存在一对整数q和r,使得0≤r<
4、b
5、,a=qb+r。q称为(不完全)商数,r称为a被b除的余数。证明:(1)当b>0时,存在性成立。看函数y=bx,
6、xZ。因为b>0,所以y是x的单调递增函数,且当x+∞时,y+∞;当x-∞时,y-∞,从而存在q,使得x=q时,y≤a;x=q+1时ya。即bq≤a,b(q+1)a。令r=a-bq,则r≥0且rb。于是a=qb+r,0≤r<b。定理5.1.1(2)当b=-b’0时,存在性成立。由(1)知,存在q’,r’,使得a=q’b’+r’,0≤r’b’。取q=-q’,r=r’,则得a=-qb’+r=qb+r,0≤r-b。综合(1),(2)对任意b(b0),都有q,r,使得a=qb+r0≤r
7、b
8、…………()定理5.1.1(3)q和r的唯一性。设
9、另有一对q’和r’满足a=q’b+r’0r
10、b
11、…………()则()-()得r’-r=(q-q’)b,从而有
12、r’-r
13、=
14、q-q’
15、
16、b
17、。注意到
18、r’-r
19、
20、b
21、,而
22、q-q’
23、0为整数,所以必有
24、q-q’
25、=0,从而
26、r’-r
27、=0。即q=q’,r=r’。所以,唯一性成立。由整除的定义,易得如下推论:b
28、a,(b0)当且仅当a被b除的余数为0。整除的基本性质性质1若a
29、b,b
30、c,则a
31、c证明:因为a
32、b,b
33、c,故有整数d,e使b=ad,c=be,因之,c=a(de)。但de是整数,所以a
34、c。性质2若a
35、b,则a
36、bc证明:由定义知
37、,b
38、bc。今a
39、b,故由性质1,a
40、bc整除的基本性质性质3若a
41、b,a
42、c,则a
43、bc。证明:因为a
44、b,a
45、c,故有整数d,e使b=ad,c=ae。因之,bc=a(de)。但de为整数,所以a
46、bc。性质4若a整除b1,…,bn,则a
47、λ1b1+…+λnbn,其中λi为任意整数。证明:因为a
48、bi,故由性质2,a
49、ibi。因为a
50、1b1,a
51、2b2,故由性质3,a
52、1b1+2b2。由此及a
53、3b3,又有a
54、1b1+2b2+3b3。如此类推归纳证明了a
55、1b1+…+nbn。整除的基本性质性质5若在一等式中,除某项外,其余各项
56、都是a的倍数,则此项也是a的倍数。证明:这是性质4的直接推论。例如,在等式b-c=-d+e+f中,设b,c,d,f都是a的倍数,求证e也是a的倍数。解出e得e=b-c+d-f。由性质4,此式右边是a的倍数,故e是a的倍数。整除的基本性质性质6若a
57、b,b
58、a,则b=a。证明:由条件知,或者a=b=0,或者a,b都不为0。若a=b=0,则b=a自然是对的。若a,b都不是0。因为a
59、b,b
60、a,故有整数d,e使b=ad,a=be,从而a=ade。消去a得1=de。今d,e是整数而相乘得1,故此二数必然都是1,因而b=a。整除的基本性质定义5.1.2若d是a
61、的因数也是b的因数,则称d为a,b的公因数。若d是a,b的公因数,而a,b的任意公因数整除d,则称d为a,b的最高公因数。a,b的最高公因数通常记为d=(a,b)。整除的基本性质性质7设a=qb+c,则a,b的公因数与b,c的公因数是完全相同的。证明:若d是b,c的公因数,则由上式及性质5,d也是a的因数,因而是a,b的公因数。反之,若d是a,b的公因数,则由上式及性质5,d也是c的因数,因而是b,c的公因数。最高公因数的定义只是说,如果有那样的d,则d叫做a,b的最高公因数。对于任意的a,b是否有那样的d呢?现在还不知道,等下面再研究。不过,有一点是容易说明
62、的:如果a,b有最高公因数,则最高公因数除符号外唯一确定。事实上,若d和d'都是a,b的最高公因数,则d
63、d',d'
64、d,因而由性质6知,d'=±d。现在我们来看,是否任意a,b有最高公因数?若b
65、a,则由定义易见,b就是a,b的最高公因数。同样,若a
66、b,a就是a,b的最高公因数。5.1.2辗转相除今设a
67、b,b
68、a。因为任意数整除0,所以a0,b0。以b除a得商q1余数r1,以r1除b得商q2余数r2,以r2除r1得商q3余数r3。如此类推有下列各式:a=q1b+r1b=q2r1+r2………rk-2=qkrk-1+rk………rn-2=qnrn-1+rn
69、rn-1=qn+1rn。5.1.2辗转