chapter7数论1

《chapter7数论1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学（数论基础篇）DiscreteMathematics（NumberTheory）计算机科学及信息类专业基础教材内蒙古大学计算机学院:段禅伦,斯勤夫数论基础本章主要介绍整数的整除性和因数分解等内容．在本章或下一章中，如无特别说明，常以小写英文字母，或有时标以足码或肩码表示整数．当几个字母写在一起时，表示它们相乘，如:abc=a×b×c;但注意数目字写在一起不表示相乘，如168不是1×6×8而是一百六十八．当数目字和字母写在一起时，则表示该数目字和字母相乘,如168abc＝168×a×b×C.7.1因数和倍数定义7.

2、1.1设a,b为整数，a≠0.若有一整数q,使得b=aq,则称a是b的因数为是a的倍数;并称a整除b,记为a

3、b,可形式地表示为:a

4、b:=(q)(b=aq)若a不能整除b，记为ab.若b=aq,而a既非b又非1,则称a是b的真因数.7.1因数和倍数关于整除，显然有下列定理：定理7.1.2①对所有a,1

5、a.②对所有a,a

6、0.③对所有a,a

7、a.④若a

8、b且b

9、c,则a

10、c.⑤若a

11、b,则对任意的c,有ac

12、bc.⑥若ac

13、bc且c≠0,则a

14、b.7.1因数和倍数⑦若a

15、b且a

16、c,则对任意的m,n,有a

17、(bm+

18、cn).⑧若a

19、b,则b=0或

20、a

21、≤

22、b

23、,其中

24、a

25、是a的绝对值,当a≥0时

26、a

27、=a;当a＜0时

28、a

29、=-a.⑨若a

30、b,则(-a)

31、b,a

32、(-b),(-a)

33、(-b),

34、a

35、

36、

37、b

38、.证明只证明⑦,余下不难证明.⑦因为a

39、b且a

40、c,故b=aq1和c=aq2.于是,bm+cn=a(q1m+q2n),所以,a

41、(bm+cn).7.1因数和倍数定理7.1.2若a是b的真因数,则1＜

42、a

43、＜

44、b

45、.定理7.1.3若a为是整数,且

46、a

47、＜

48、b

49、,

50、b

51、

52、

53、a

54、,则a=0.证明因为

55、b

56、

57、

58、a

59、,故有整数q,使得

60、a

61、=

62、

63、b

64、q.若

65、a

66、=0,则a=0.若

67、a

68、>0,则由于0<

69、a

70、<

71、b

72、和

73、a

74、=

75、b

76、q,有q≥0.若q>0,则由q是整数而有q≥1.由

77、a

78、=

79、b

80、和q≥1有

81、a

82、>

83、b

84、,这与

85、a

86、<

87、b

88、矛盾,故q=0;若q=0和

89、a

90、=

91、b

92、q有a=0.7.1因数和倍数定理7.1.4(带余除法)若a为是二个整数,b≠0,则唯一存在二个整数q和r,使得下式成立:a=bq+r,0≤r<

93、b

94、.证明考虑两种可能：只证明①.存在一整数q,使得a=bq,故r=0,定理成立.7.2素数和合数在正整数中,1只能被它本身整除.任何大于1的整数

95、都至少能被1和它本身整除．定义7.2.1一个大于1且只能被1和它本身整除的整数,称为素数;否则,称为合数.由该定义可知，正整数集合可分三类:素数、合数和1.素数常用户或p或p1,p2…,来表示.7.2素数和合数定义7.2.2若正整数a有一因数b,而b又是素数,则称b为a的素因数．例:12=3×4,其中3是12的素因数,而4则不是.定理7.2.1若a是大于1的整数,则a的大于1的最小因数一定是素数.证明若a是素数,显然a的大于二的最小因素就是素数a;若a是合数,则除1和a外还有其它的因数，令b是这些正因数中最小者,可以证明

96、b不是合数而是素数,若其不然,b必有大于1且不等于b的因数c,于是由c

97、b和b

98、c可知c

99、a,即c是a的因数,又有1

100、整除,则a是素数.假设是合数且a＝be,其中b和c都是大于1的整数,由于a不能被大于1且小于或等于的整数整除,所以b＞,c＞,于是,可得bc＞.=a,这与bc=a矛盾.因此,若a不能被大于三且小于或等于的整数整除，则是素数．7.2素数和合数由上可知,若a是合数,则a一定有大于1且小于或等于人的因数.由定理7.2.1知,a的大于1的最小因数一定是素数,故本定理得证.素数有多少？公元前三世纪,古希腊数学家欧几里德Euclid就证明了素数有无穷多个.7.2素数和合数定理7.2.3(Euclid)素数有无穷多个.证明(反证法)假

101、设素数是有限多个,共有n个,令它们是p1,p2,…,pn,并令a=p1p2…pn+1.若a是素数,则因a≠pi;其中1

102、p1p2…pn,但pi不能整除1,故pi不能整除a,因此b≠