整除性辗转相除ou

《整除性辗转相除ou》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章数论基础本章为数论的一部分。数论是数学中最古老的分支之一。公元前三世纪，古希腊数学家欧几里得所著《几何原本》中证明了质数的个数无穷多，并给出了求两个正整数公因数的算法（辗转相除法）。公元前50年，在我国第一部数学名著《九章算术》的第一章中就开始讨论整数，介绍了辗转相除法，与欧几里得的辗转相除法是各自独立总结出来的。四世纪时，在我国的《孙子算经》中对整数做了研究，给出了解一次同余式的算法，其中之一“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问至少物几何？”。把孙子所有算法推广开即闻名于世的孙子定理（秦九韶定理），国外称作中

2、国剩余定理----初等数论中一个重要的定理。数论主要用算术方法（加减乘除）研究整数性质。任意两个整数相加、相减、相乘的结果仍是整数。但两个整数不一定能在整数的范围内相除，这是整数系统的特点，研究整数就针对这一特点加以分析，研究整数的性质基本上就是要研究整除性和因数分解等问题以及其它一些有关的问题。数论特点：原理讲起来容易，应用起来很难，灵活性强。真正学好数论，不但需要数论的知识，还要有灵活、聪明的头脑，光死板学是学不好的。数论包含内容很多，本章介绍其中最基本的知识，即，整数的一些最基本的性质。为下面三章作准备，因为抽象代数里一些较抽象的内容很

3、多都可以在数论中找到根源和实例。第五章数论基础§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

4、a。Note:1、任意整数整除0，特别0

5、0；但0不能整除任意整数。2、1（-1）整除任意整数。定理5.1.1(带余除法定理)对任意整数a和b，b0，唯一存在一对整数q和r，使得a=qb+r，0≤r＜

6、b

7、。（q称为

8、商数，r称为a被b除的余数。）证明:(一）存在性(1)若b>0,a≥0，则算术中学过长除法，有q和r，使得a=qb+r，0≤r＜b。(2)若b>0,a≤0，则取a’=-a，于是a’≥0。由(1)知，对a’,b，有q’,r’，使得a’=q’b+r’，0≤r’＜b。于是a=-a’=(-q’)b+(-r’)①若r’=0，则取q=-q’，有a=qb②若r’≠0，取r=b-r’，则0

9、b

10、=b。定理5.1.1（3）若b0，而a任意，则取b’=

11、-b，于是b’>0，由(1)(2)知，存在q’，r’，使得a=q’b’+r’，0≤r’b’=

12、b

13、。即a=q’(-b)+r’=(-q’)b+r’，0≤r’

14、b

15、故取q=-q’，r=r’，则得a=qb+r，0≤r

16、b

17、。综合(1)-(3)对任意b(b0)，都有q，r，使得a=qb+r0≤r

18、b

19、…………()定理5.1.1（二）q和r的唯一性。设另有一对q’和r’满足a=q’b+r’0r’

20、b

21、…………()则()-()得r’-r=(q-q’)b，从而有

22、r’-r

23、=

24、q-q’

25、

26、b

27、。注意到

28、r’-r

29、

30、b

31、，而

32、q-

33、q’

34、0为整数，所以必有

35、q-q’

36、=0，从而

37、r’-r

38、=0。即q=q’，r=r’。所以，唯一性成立。由整除的定义，易得如下推论：b

39、a，(b0)当且仅当a被b除（或者a除以b,或者b除a）的余数为0。推论整除的基本性质性质1若a

40、b，b

41、c，则a

42、c证明：因为a

43、b，b

44、c，故有整数d，e使b=ad，c=be，因之，c=a(de)。而de是整数，所以a

45、c。性质2若a

46、b，则a

47、bc证明：由定义知，b

48、bc。今a

49、b，故由性质1，a

50、bc整除的基本性质性质3若a

51、b，a

52、c，则a

53、bc。证明：因为a

54、b，a

55、c，故有整数d，e使b=

56、ad，c=ae。因之，bc=a(de)。而de为整数，所以a

57、bc。性质4若a整除b1,…,bn,则a

58、1b1+…+nbn，其中i为任意整数。证明：因为a

59、bi，故由性质2，a

60、ibi。因为a

61、1b1，a

62、2b2，故由性质3，a

63、1b1+2b2。由此及a

64、3b3，又有a

65、1b1+2b2+3b3。如此类推归纳证明了a

66、1b1+…+nbn。（也可用数学归纳法）整除的基本性质性质5若在一等式中，除某项外，其余各项都是a的倍数，则此项也是a的倍数。证明：这是性质4的直接推论。例.在等式b-c=-d+e+f中，设b，

67、c，d，f都是a的倍数，求证e也是a的倍数。解出e得e=b-c+d-f。由性质4，此式右边是a的倍数，故e是a的倍数。例5.1.1若5

68、(a+b)，则25

69、(a5+