初等数论 第一章 整数的可除性

《初等数论 第一章 整数的可除性》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章整数的可除性第一章整数的可除性§1整除整数集对于加、减、乘三种运算都是封闭的，但是对于除法运算不封闭。为此，我们引进整除的概念。定义1设a,b∈Z，b≠0，如果存在q∈Z，使得等式a=bq成立，那么称b整除a或a被b整除，记作：b

2、a，此时称b为a的因数（约数），a为b的倍数。如果不存在满足等式a=bq的整数q，那么称b不能整除a或a不被b整除，记作ba。定理1设a,b,c∈Z，b≠0，c≠0，则（1）如果c

3、b，b

4、a，那么c

5、a；（2）如果b

6、a，那么bc

7、ac；反之亦真；（3）如果c

8、a，c

9、b，那么，对

10、于任意m,n∈Z，有c

11、(ma+nb)；（4）如果b

12、a，a≠0，那么

13、b

14、≤

15、a

16、；（5）如果b

17、a，a

18、b，那么

19、b

20、=

21、a

22、。证明可选证。定理2（带余除法）设a,b∈Z，b≠0，则存在q,r∈Z，使得a=bq+r，0≤r<

23、b

24、，并且q及r是唯一的。证明当b

25、a时，取q=a/b，r=0即可。当b!

26、a时，考虑集合E={a-bk

27、k∈Z}，易知E中有正整数，因此E中有最小正整数，设为r=a-bk>0，下证：r<

28、b

29、。因为b!

30、a，所以r≠

31、b

32、，若r>

33、b

34、，则r’=r-

35、b

36、>0，又r’∈E，故与r的最小性矛

37、盾，从而存在q,r∈Z，使得a=bq+r，0≤r<

38、b

39、。唯一性。设另有q’,r’∈Z，使得a=bq’+r’，0≤r’<

40、b

41、，则b(q-q’)=r’-r，于是-13-第一章整数的可除性b

42、(r’-r)，但由于0≤

43、r’-r

44、<

45、b

46、，故r’-r=0，即r=r’，从而q=q’。定义2等式a=bq+r，0≤r<

47、b

48、中的整数q称为a被b除所得的（不完全）商，整数r称为a被b除所得的余数。注r=0的情形即为a被b整除。例1设b=15，则当a=255时，a=17b+0，故q=17，r=0；当a=417时，a=27b+12，

49、故q=27，r=12；当a=-81时，a=-6b+9，故q=-6，r=9。例2整数被2除的余数有两种可能：0和1，一个整数被2整除称为偶数，否则称为奇数，分别记作2k和2k+1，k∈Z。类似地，任一整数可表示为3k，3k+1，3k+2三种形式之一。例3设a=2t-1，若a

50、2n，则a

51、n。例4设a,b∈Z，a≠0，b≠0，有x,y∈Z，使ax+by=1，证明：若a

52、n，b

53、n，则ab

54、n。-13-第一章整数的可除性§2最大公因数与最小公倍数定义1设a1,a2,…,an是n(n≥2)个整数，若整数d满足d

55、ai，i=1

56、,2,…,n，则称d为a1,a2,…,an的一个公因数；整数a1,a2,…,an的公因数中最大的一个称为最大公因数，记作：(a1,a2,…,an)；若(a1,a2,…,an)=1，则称a1,a2,…,an互质（互素）；若a1,a2,…,an中每两个整数互质，则称a1,a2,…,an两两互质。注1任意整数a1,a2,…,an必有公因数（如±1）。注2若a1,a2,…,an不全为0，则它们的公因数只有有限多个，从而它们的最大公因数必然存在而且唯一。（§1定理1之(4)）注3最大公因数一定是正整数。注4(a1,a2,…,a

57、n)=1相当于a1,a2,…,an的公因数只有±1。注5两两互质必互质，反之未然。定理1若a1,a2,…,an是任意n个不全为零的整数，则(1)a1,a2,…,an与

58、a1

59、,

60、a2

61、,…,

62、an

63、的公因数相同；(2)(a1,a2,…,an)=(

64、a1

65、,

66、a2

67、,…,

68、an

69、)。定理2若b是任一正整数，则(1)0与b的公因数就是b的因数，反之亦然；(2)(0,b)=b。推论若b是任一非零整数，则(0,b)=

70、b

71、。定理3设a,b,c是任意三个不全为零的整数，且a=bq+c，其中q∈Z，则a,b与(b,c)有相同的公

72、因数，从而(a,b)=(b,c)。定理4设a1,a2,…,an是不全为零的整数，则a1,a2,…,an的整线性组合的集合S={a1x1+a2x2+…+anxn

73、xi∈Z，i=1,2,…,n}恰由(a1,a2,…,an)的所有倍数组成。-13-第一章整数的可除性证明因为S中有正整数，所以S中有最小正整数，设为D=a1x1’+a2x2’+…+anxn’，则对于任意的a1x1+a2x2+…+anxn∈S，有a1x1+a2x2+…+anxn=(a1x1’+a2x2’+…+anxn’)q+r，其中0≤r

74、+…+anxn’，于是r=a1(x1-x1’q)+a2(x2-x2’q)+…+an(xn-xn’q)∈S，若r>0，则与D是最小正整数矛盾，故r=0，即S中任一整数都是D的倍数。反之，D的倍数也属于S，故S=DZ={Da

75、a∈Z}。设d=(a1,a2,…,an)，下证：D=d。由于D∈S，又d

76、ai，i=1,2,…,n，故d

77、D，即d≤D；另一