互质质因数分解课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,5.2 互质 质因数分解,5.2 互质 质因数分解,1,5.2.1,整数互质,定义5.2.1,若,a，b,除1外无其它公因数，则称,a,和,b,互质,。,结论：,1,、,a,和,b,互质，必要而且只要,a,、,b,的最高公因数为,1,(,通常只考虑,+1),。,2,、,1,和,任意,整数,(,包括,0),互质。,5.2.1 整数互质 定义5.2.1 若a，b除1外,2,定理,5.2.1,a,和,b,互质，当且仅当1可表示为,a,和,b,的倍数和形式，即存在整数,s,和,t,使1=,sa+tb。,证明：,必要性,；由,a,和,b,互质知，,a,和,b,的最高公因数为1，从而根据定理,5.1.3,，存在,s，t，,使,sa+tb=1。,充分性,；只需证：若存在,s,，,t,，,使,sa+tb=1,，,则,a,和,b,的最高公因数,d=(a,b),为,1,。假设,d=(a,b),1,，,则,d|a,，,d|b,，,从而,d,整除,sa+tb=1,的左端，因此,d|1,，,矛盾。,定理5.2.1 a和b互质，当且仅当1可表示为a和b的倍数和,3,定理,5.2.2,若,a,和,b,互质，而,a,bc，,则,a,c。,证明：,因为,a，b,互质，故有,s，t,使1=,sa+tb，,从而,c=sac+tbc,(,1,),今因,a,bc,，,a|ac,，故,a,整除,(,1,),右边每一项，因而,a,c,。,定理5.2.2 若a和b互质，而abc，则ac。,4,定理,5.2.3,若,b,和,a,1,a,2,a,n,都互质，则,b,和,a,1,a,2,a,n,互质。,证明：,由题设，对,i=1,2,n，,有,s,i,，t,i,使,s,i,b+t,i,a,i,=1,把所有这,n,个式子乘起来，右边得1，左边有2,n,项，其中有一项包含,a,1,a,2,a,n,，,而其余各项都包含,b，,所以，乘起来的式子如下：,S b+T a,1,a,2,a,n,=1,由定理5.2.1得，,b,和,a,1,a,2,a,n,二者互质。,定理5.2.3 若b和a1,a2,an都互质，则b和a1,5,定理5.2.4,若,m,1,m,2,m,k,两两互质而都整除,a，,则,m,1,m,2,m,k,|a。,证明：,对,k,用数学归纳法。,当,k=1,时，结论显然。,当,k=2,时，由于,m,1,|a，,所以存在整数,q,使得,a=m,1,q,。,又,m,2,|a，,即,m,2,|m,1,q，,而(,m,1,m,2,)=1，,故,m,2,|q(,定理5.2.2)，于是存在,p，,使,q=m,2,p,。,从而,a=m,1,m,2,p,，,即,m,1,m,2,|a。,定理5.2.4若m1,m2,mk两两互质而都整除a，则m,6,定理5.2.4,假定对,i(1,ik),有,m,1,m,2,m,i,|a,(,2,),我们证明,m,1,m,2,m,i,m,i+1,|a,(,3,),由(,2,)知有,q,使,a=m,1,m,2,m,i,q,(,4,),今,m,i+1,|a,，,且由定理,5.2.3,知,m,i+1,和,m,1,m,2,m,i,互质，故由定理,5.2.2,，,m,i+1,|q,。,据此及,(4),可以得到,(3),成立。归纳证毕。,定理5.2.4假定对i(1ik)有,7,例5.2.1,试证相继三个整数之积能被6整除。,证明：,三个相继整数必有一个为偶数，且必有一个为3的倍数，即2|,n(n+1)(n+2)，3|n(n+1)(n+2)。,而(2，3)=1，故根据定理,5.2.4,有，,6|n(n+1)(n+2)。,例5.2.1试证相继三个整数之积能被6整除。,8,例5.2.2,试证相继三个整数的立方和是9的倍数。,证明：,设,n-1，n，n+1,为三个相继整数，则,(,n-1),3,+n,3,+(n+1),3,=3n,3,+3n,2,-3n,2,+6n-1+1,=3(n,3,+2n),=3(n,3,+3n-n),=3(3n+n(n,2,-1),=9n+3(n-1)n(n+1),而由上例,5.2.1,知,3|(,n-1)n(n+1),，,故,9|(,n-1),3,+n,3,+(n+1),3,),。,例5.2.2试证相继三个整数的立方和是9的倍数。,9,例5.2.3,试证2,p,-1,和2,q,-1,互质的充要条件是,p,和,q,互质。,证明：必要性：,假若,p,和,q,不互质，(,p,q)=a,1，,记,p=ap,1,，q=aq,1,，,则2,p,-1=2,ap1,-1，2,q,-1=2,aq1,-1。,有公因数2,a,-1,1，,矛盾。,充分性：,已知,(,p,q)=1,，,设,(2,p,-1,2,q,-1)=d,，,往证,d=1,。,不妨设,p,q,，,辗转相除得,p=ql,1,+r,1,，,q=r,1,l,2,+r,2,，,，,r,n-2,=r,n-1,l,n,+r,n,，,r,n-1,=r,n,l,n+1,。,由于,(,p,q)=1,，,故,r,n,=1,。,因为,2,p,-1=2,ql1+r1,-1=2,r1,(2,ql1,-1)+2,r1,-1=(2,q,-1)N+(2,r1,-1),，,所以，,(2,q,-1,2,r1,-1)=d,。,同理推得,d=(2,r1,-1,2,r2,-1)=,。,例5.2.3试证2p-1和2q-1互质的充要条件是p和q互质,10,例5.2.4,若(,a,i,b,j,)=1，1,i,n，1,j,m，,则(,a,1,a,2,a,n,b,1,b,2,b,m,)=1。,特别当(,a,b)=1,时，(,a,n,b,m,)=1，n,m,为任意正整数。,证明：,由,(,a,i,b,j,)=1,，,1,j,m,，,得,(,a,i,b,1,b,2,b,m,),=1,，,1,i,n,，,进而,(,a,1,a,2,a,n,b,1,b,2,b,m,)=1,。,取,a,i,=a,，,b,j,=b,，,则,（,a,n,b,m,）,=1,。,例5.2.4若(ai,bj)=1，1 i n，1,11,更正,P161,定理,5.2.1,中“充分性”证明的第二个,sa+td=1(“,从而,d,整除,sa+td=1,的左端”,),应该是,sa+tb=1,.,P161,定理,5.2.3,中“若,b,和,a,1,a,2,a,k,都互质”的,a,k,应该是,a,n,.,P162,例,5.2.3,倒数第二行最后,:,改为,更正P161,定理5.2.1中“充分性”证明的第二个sa+,12,例5.2.5,设,a,b,为大于1的自然数，,b,a，,且(,a,b)=1，,则,log,a,b,是无理数。,证明：反证法。若不然，假设,log,a,b=p/q,为有理数。,因,b,a,，,不妨设,p,，,q,是,正整数,，且（,p,q,）,=1,。,从而得,a,p/q,=b,，,即,a,p,=b,q,。,因为,(,a,b)=1,，,由上例,5.2.4,知,（,a,p,b,q,）,=1,，,与,a,p,=b,q,矛盾。,例5.2.5 设a,b为大于1的自然数，ba，且,13,设,f(x)=a,n,x,n,+a,n-1,x,n-1,+a,0,是整系数多项式，若10|,f(2)，10|f(5)，,则10|,f(10)。,证明：,注意到,f(10)=a,n,10,n,+a,n-1,10,n-1,+a,1,10,1,+a,0,，,所以10|,f(10),当且仅当10|,a,0,。,因为,10|,f(2),，,所以,2|,f(2),，,于是,2|,a,0,，,同样,5|,a,0,。,由（,2,，,5,）,=1和定理,5.2.4,得,10|,a,0,。,例5.2.6,设f(x)=anxn+an-1xn-1+a0是整系数多项,14,5.2.2,质数与合数算术基本定理,5.2.2 质数与合数算术基本定理,15,一个,正整数,，如果,不等于,1,而且除了自己和,1,没有其它正因数，则称其为一个,质数,(,也称为,素数,),；否则称其为,合数,。,这样，正整数分为,1,质数，合数,例如：,2,，,3,，,5,，,7,，,11,，,都是质数。,1,既不是质数也不是合数。,1,之所以要摒于质数之外，是因为它完全没有质数所具备的那些重要的数论性质。,定义,5.2.2,一个正整数，如果不等于1而且除了自己和1没有其它正因数，,16,结论：质数,p,和,a,互质，必要而且只要,p|a。,充分性。,若,p|a，,则,p,当然就不是,p,a,的公因数；,而,p,是质数，除了,p，,只有1才可能是,p,的因数，,所以只有1才可能是,p,a,的公因数，即二者互质。,结论：任意两个不同的质数互质。,证明：必要性。,反证，若,p|a，,则,p,和,a,除1外还有公因数,p，,故二者不互质，与二者互质矛盾。,结论：质数p和a互质，必要而且只要p|a。充分性。若p|a，,17,设,p,为质数,若,p,整除,a,1,a,2,a,n,，,则,p,整除,a,1,，a,2,，a,n,之一。,证明：反证。,假若,a,1,，,a,2,，,，,a,n,都不能被质数,p,整除，则,p,和它们都互质，故由定理,5.2.3,，,p,和它们的乘积互质，因而,p,将不能整除此乘积,a,1,a,2,a,n,，矛盾。,定理,5.2.5,设p为质数,定理5.2.5,18,任意,正整数,n,（,n,1,）,恰有一法,写成质数的乘积（不计因数乘积的顺序）。,证明：,先证,n,可以,写成质数的乘积。,用数学归纳法，,n=2,时,显然成立，因为,2,是质数，算是已经写成了质数的乘积。,假定,na,时,n,可以写成质数的乘积，,试证,n=a,时也可以这样写。,定理,5.2.6,(算术基本定理),任意正整数n（n1）恰有一法写成质数的乘积（不计因数乘积的,19,若,a,是质数，则,a,算是已经写成了质数的乘积。,若,a,不是质数，于是，,a,有因数,b,，,1ba,。,使,a=bc,，,1ca,。,既然,b,和,c,都,a,，,故由归纳假定，,b,和,c,都可以写成质数的乘积。又,a=bc,，,只要把这两个乘积连接起来就把,a,写成了质数的乘积。归纳法已经完成，所以任意正整数,n,（,n,1,）,可以写成质数的乘积。,若a是质数，则a算是已经写成了质数的乘积。,20,再证,n,只有一法,写成质数的乘积，,如果,n=p,1,p,h,=q,1,q,k,(,5,),而,p,1,p,h,，q,1,q,k,都是质数，往证,h=k，,而且,p,1,p,h,和,q,1,q,k,完全一样，最多次序不同。,由(,5,)，,p,1,|q,1,q,k,，,故由定理5.2.5，,p,1,应整除,q,1,q,k,之一，颠倒后者的次序，可假定,p,1,|q,1,。,今,q,1,是质数，只有,q,1,和1两个正因数，而,p,1,1，,故,p,1,必等于,q,1,。,再证n只有一法写成质数的乘积，,21,由(,5,)消去,p,1,而得,p,2,p,h,=q,2,q,k,由此同上可证,p,2,应整除,q,2,q,k,之一。如此类推，可见,p,1,p,h,和,q,1,q,k,完全一样，最多次序不一样。不可能一边已经消完而另一边还剩下质数，因为，那样则一个质数或一些质数之积等于1，这不可能。,由(5)消去p1而得,22,推论1,任意整数(,0，,1)恰好有一法写成下面的形式：,p,1,p,k,(,6,),其中,p,1,p,k,都是质数。,推论2,任意整数(,0，,1)恰好有一法写成下面的形式：,p,1,r1,p,n,r n,(,7,),其中,p,1,p,n,是不同的质数，,r,1,r,n,是正整数。,定理,5.2.6,(算术基本定理),推论1 任意整数(0，1)恰好有一法写成下面的形式：,23,Note,：,1,若,a,写成,p,1,r1,p,n,rn,的形式，则,a,有,2(r,1,+1)(r,n,+1),个因数。