最大公因数和最小公倍数

《最大公因数和最小公倍数》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§2.3最大公因数与最小公倍数公因数最大公因数定义1若d

2、ai,i=1,2,…n,n≥2,则称d为a1,a2,…,an的公因数。由于任何非零整数的因数只有有限个，所有有限个不全为0的整数的一切公因数构成有限集，其中必有最大数。定义2不全为零的整数a1,a2,…,an的公因数中的最大数叫做这n个整数的最大公因数，记作(a1,a2,…,an)。显而易见，(a1,a2,…,an)是不小于1的整数。互素定义3如果(a1,a2,…,an)=1，则称a1,a2,…,an互素。如果a1,a2,…,an中每两个数都互素，就说它们两两互素。例1已知费尔马(Fermat)

3、数Fn=22^n+1(整数n≥0)，求证(Fi,Fj)=1，这里i,j都是非负整数，且i≠j。公式[提示]：要熟知下面的公式(其中n为正偶数)（其中n为正奇数）(其中n是自然数)例题1证明例1已知费尔马(Fermat)数Fn=22^n+1(整数n≥0)，求证(Fi,Fj)=1，这里i,j都是非负整数，且i≠j。证明：不妨设j=i+k(k为自然数),由于Fj-2=Fi+k-2=(22^i)2^k-1,从而Fi

4、Fj-2。设(Fi,Fj)=d，由d

5、Fi知d

6、Fj-2,又d

7、Fj,于是d

8、2，但Fn是奇数，所以d=1。例1表明每两个费尔马数都互素，进而可知

9、(F0,F1,…,Fn)=1。定理定理1(a1,a2,…,an)=(

10、a1

11、,

12、a2

13、,…,

14、an

15、)。定理1表明，涉及到最大公因数问题，只要对非负整数进行讨论就行了。定理2若整数a,b,c不全为零，且a=bq+c，则(a,b)=(b,c)。定理2证明定理2若整数a,b,c不全为零，且a=bq+c，则(a,b)=(b,c)。证明：设(a,b)=d1,(b,c)=d2,因为d1

16、a,d1

17、b,所以d1

18、a-bq,即d1

19、c,又d1

20、b，因此d1≤（b,c）,即d1≤d2；同理可证，d2

21、b,d2

22、c,所以d2

23、bq+c,即d2

24、a,又d2

25、b，因此d2≤

26、（a,b）,即d2≤d1.因为d1≤d2,d2≤d1,所以d1=d2。定理2的应用定理2给出了求最大公因数的方法，对a,b∈N，反复作带余除法，有a=bq1+r1,0

27、)=(b,r1)(b,r1)=(r1,r2)(r1,r2)=(r2,r3)……(rn-1,rn)=(rn,rn+1)(rn,rn+1)=rn可知：(a,b)=rn定理3若a,b∈N，对a,b作辗转相除，则(a,b)为最后一个不为零的余数。定理4a=bq1+r1,0

28、b不全为零，则存在x,y∈Z,使得ax+by=(a,b)。相关定理和推论推论(a,b)=1的充要条件是有x,y∈Z,使得ax+by=1定理5若d

29、a,d

30、b,则d

31、(a,b)。定理6若m∈N，则(ma,mb)=m(a,b)。定理7若(a,c)=1，b∈Z,b、c中至少有一个不为零，则(ab,c)=(b,c)。推论1若(a,c)=1,(b,c)=1，则(ab,c)=1。推论2若(a,b)=1,a

32、bc,则a

33、c。推论3若(a,b)=1，a

34、c,b

35、c,则ab

36、c。谢谢定理8设(a1,a2)=d2,(d2,a3)=d3,…,(dn-1,an)=dn,则(a

37、1,a2,…,an)=dn。证明：由条件知d2

38、a1,dk

39、ak(k=2,3,…,n),di

40、di-1(i=3,4,…,n)，于是dn是a1,a2,…,an的公因数。设d是a1,a2,…,an的任一个公因数，由d

41、a1,d

42、a2知d

43、d2。再由d

44、a3知d

45、d3，依次类推，最后得d

46、dn，于是d≤

47、d

48、≤dn。所以dn是a1,a2,…,an的最大公约数。定理9若整数a1,a2,…,an（n≥2）不全为零，则存在xi∈Z,i=1,2,…,n,使得a1x1+a2x2+…+anxn=(a1,a2,…,an)。例题例2设(a,b)=1,求证(ab,a+b)=1

49、。证：设（a,a+b）=d,由d

50、a,d

51、a+b知d

52、b,又由于(a,b)=1，于是d=1；同