初等数论第一章3

1、初等数论,NumberTheory,第一章整除理论,整除性理论是初等数论的基础。本章要介绍带余数除法，辗转相除法，最大公约数，最小公倍数，算术基本定理以及它们的一些应用。,第三节最大公约数,定义1整数a1,a2,ak的公共约数称为a1,a2,ak的公约数。不全为零的整数a1,a2,ak的公约数中最大的一个叫做a1,a2,ak的最大公约数（或最大公因数），记为(a1,a2,ak)。,由于每个非零整数的约数的个数是有限的,所以最大公约数是存在的,并且是正整数.,第三节最大公约数,如果(a1,a2,ak)=1，则称a1,a2,ak是互素的（或互质的）；如果(ai,aj)=1，1i,jk，ij，则称a

2、1,a2,ak是两两互素的(或两两互质的).,显然，a1,a2,ak两两互素可以推出(a1,a2,ak)=1，反之则不然，例如(2,6,15)=1，但(2,6)=2。,第三节最大公约数,定理1下面的等式成立：()(a1,a2,ak)=(|a1|,|a2|,|ak|)；()(a,1)=1，(a,0)=|a|，(a,a)=|a|；()(a,b)=(b,a)；()若p是素数,a是整数,则(p,a)=1或pa;()若a=bqr，则(a,b)=(b,r)。,第三节最大公约数,证明()()留作习题。()由第一节定理1可知,如果da，db，则有dr=abq，反之,若db，dr，则da=bqr.因此a与b的全

3、体公约数的集合就是b与r的全体公约数的集合，这两个集合中的最大正数当然相等，即(a,b)=(b,r)。证毕。,由定理1可知,在讨论(a1,a2,an)时,不妨假设a1,a2,an是正整数,以后我们就维持这一假设.,第三节最大公约数,定理2设a1,a2,akZ，记A=y:y=x1a1+x2a2+xkak,xiZ,ik.如果y0是集合A中最小的正数,则y0=(a1,a2,ak).,证明设d是a1,a2,ak的一个公约数,则dy0,所以dy0.另一方面,由第二节例2知,y0也是a1,a2,ak的公约数.因此y0是a1,a2,ak的公约数中的最大者,即y0=(a1,a2,ak).证毕.,第三节最大公约

4、数,推论1设d是a1,a2,ak的一个公约数，则d(a1,a2,ak)。,这个推论对最大公约数的性质做了更深的刻划：最大公约数不但是公约数中的最大的，而且是所有公约数的倍数。,推论2(ma1,ma2,mak)=|m|(a1,a2,ak)。,第三节最大公约数,推论3记=(a1,a2,ak)，则,特别地,第三节最大公约数,定理3(a1,a2,ak)=1的充要条件是存在整数x1,x2,xk，使得a1x1a2x2akxk=1。(1),证明必要性由定理2得到。充分性若式(1)成立，如果(a1,a2,ak)=d1，那么由dai（1ik）推出da1x1a2x2akxk=1，这是不可能的。所以有(a1,a2,

5、ak)=1。证毕。,第三节最大公约数,定理4对于任意的整数a，b，c，下面的结论成立：()由bac及(a,b)=1可以推出bc；()由bc，ac及(a,b)=1可以推出abc。,证明()若(a,b)=1，由定理2，存在整数x与y，使得axby=1。,第三节最大公约数,因此acxbcy=c(2)由上式及bac得到bc。结论()得证；()若(a,b)=1，则存在整数x，y使得式(2)成立。由bc与ac得到abac，abbc，再由式(2)得到abc。结论()得证。证毕。,第三节最大公约数,推论1若p是素数，则下述结论成立：()pabpa或pb；()pa2pa。,证明留作习题。,第三节最大公约数,推论

6、2若(a,b)=1，则(a,bc)=(a,c)。,证明设d是a与bc的一个公约数，则da，dbc，由式（2）得到，d|c,即d是a与c的公约数。另一方面，若d是a与c的公约数，则它也是a与bc的公约数。因此，a与c的公约数的集合，就是a与bc的公约数的集合，所以(a,bc)=(a,c)。证毕。,第三节最大公约数,推论3若(a,bi)=1，1in，则(a,b1b2bn)=1。,证明留作习题。,定理5对于任意的n个整数a1,a2,an，记(a1,a2)=d2,(d2,a3)=d3,(dn2,an1)=dn1,(dn1,an)=dn，则dn=(a1,a2,an).,第三节最大公约数,证明由定理2的推

7、论，我们有dn=(dn1,an)dnan，dndn1，dn1=(dn2,an1)dn1an1，dn1dn2，dnan，dnan1，dndn2，dn2=(dn3,an2)dn2an2，dn2dn3dnan，dnan1，dnan2，dndn3，,第三节最大公约数,d2=(a1,a2)dnan，dnan1，dna2，dna1，即dn是a1,a2,an的一个公约数。,另一方面，对于a1,a2,an的任何公约数d，由定理2的推论及d2,dn的定义，依次得出da1，da2dd2，dd2，da3dd3，,第三节最大公约数,ddn1，danddn，因此dn是a1,a2,an的公约数中的最大者，即dn=(a1,

8、a2,an)。证毕。,第三节最大公约数,证明由定理1得到(21n4,14n3)=(7n1,14n3)=(7n1,1)=1。,例1证明:若n是正整数,则是既约分数.,注：一般地，若(x,y)=1，那么，对于任意的整数a，b，有(x,y)=(xay,y)=(xay,yb(xay)=(xay,(ab1)ybx)，因此，是既约分数。,第三节最大公约数,证明由于121=112，n22n12=(n1)211，所以，若112(n1)211，(3)则11(n1)2，因此，由定理4的推论1得到11n1，112(n1)2。再由式(3)得到11211，这是不可能的。所以式(3)不能成立。,例2证明：,第三节最大公约

9、数,注：这个例题的一般形式是：设p是素数，a，b是整数，则Pk(anb)kpk1c，其中c是不被p整除的任意整数，k是任意的大于1的整数。,第三节最大公约数,证明由式(4)得到9(ab)23ab3(ab)23ab3(ab)23ab(5)9(ab)2。,例3设a，b是整数，且9a2abb2，(4)则3(a,b)。,第三节最大公约数,再由式(4)得到93ab3ab。因此，由定理4的推论1，得到3a或3b。若3a，由式(5)得到3b；若3b，由(5)式也得到3a。因此，总有3a且3b。由定理2的推论推出3(a,b)。再由式(3)得到11211，这是不可能的。所以式(3)不能成立。,第三节最大公约数,证明()若a2,则2b12a1.,第三节最大公约数,()若a=b，且式(6)成立，则由式(6)得到2a1(2a1)22a122a122a3，于是b=a=1，这是不可能的，所以式(6)不成立。,第三节最大公约数,()若ab，记a=kbr，0rb，此时2kb1=(2b1)(2(k1)b2(k2)b1)=(2b1)Q,其中Q是整数。所以2a1=2kb+r1=2r(2kb11)1=2r(2b1)Q1)1=(2b1)Q(2r1),其中Q是整数。因此2b12a12b12r1，在()中已经证明这是不可能的,所以式(6)