《整除性辗转相除》PPT课件

《整除性辗转相除》PPT课件

ID:37460519

大小:259.50 KB

页数:32页

时间:2019-05-12

《整除性辗转相除》PPT课件_第1页
《整除性辗转相除》PPT课件_第2页
《整除性辗转相除》PPT课件_第3页
《整除性辗转相除》PPT课件_第4页
《整除性辗转相除》PPT课件_第5页
资源描述:

《《整除性辗转相除》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,b0,唯一存在一对整数q和r,使得0≤r<

4、b

5、,a=qb+r。q称为(不完全)商数,r称为a被b除的余数。证明:(1)当b>0时,存在性成立。看函数y=bx,

6、xZ。因为b>0,所以y是x的单调递增函数,且当x+∞时,y+∞;当x-∞时,y-∞,从而存在q,使得x=q时,y≤a;x=q+1时ya。即bq≤a,b(q+1)a。令r=a-bq,则r≥0且rb。于是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(b0),都有q,r,使得a=qb+r0≤r

7、b

8、…………()定理5.1.1(3)q和r的唯一性。设

9、另有一对q’和r’满足a=q’b+r’0r

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,(b0)当且仅当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、bc。证明:因为a

44、b,a

45、c,故有整数d,e使b=ad,c=ae。因之,bc=a(de)。但de为整数,所以a

46、bc。性质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,所以a0,b0。以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辗转

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。