辗转相除法与裴蜀定理

1、二、辗转相除法与裴蜀定理4、辗转相除法与裴蜀定理定义对于整数a,b,若ab,则称a是b的约数；而b是a的倍数.定义对于不全为零的整数a/i121",n),若aai对i1,21|,n都成立，则称a是a1，a2,|4的公约定义对于非零整数al1,2j“，n),若aiaxi12“|,n都成立，则称a是agj”小的公倍数.定义整数ai(i1,2,|“，n)的公约数中，最大的一个，称为整数a/i1,2,|",n)的最大公约数，记作(a1,a2,|an).整数a/i1,2,W，n)的公倍数中，最小的一个，称为整数ai(i1,2,|“，n)的最小公倍数，记作4e2,"同.定义若

2、(a,b)=1,则称a,b互质或互素.显然有下列性质：性质1(a,b)=(b,a)=(a,-b)=(-a,-b);性质2ab=(a,b)a,b,特别地当a>0,b>0时，ab=(a,b)a,b.卜面我们介绍辗转相除法与裴蜀定理定理若a=qb+r,则(a,b)=(b,r).注：本定理也可写成：(a,b)=(abq,b),就是说，在计算(a,b)时，可用b的任意整数倍数bq去减a.下面我们介绍辗转相除法，对于给定的整数a,b(b>0),我们反复运用带余除法就有：a=q1b+b1,0b1<b,如b10,则我们继续b=q2b1+b2,0b2<b1,如b20,则我们继续b1

3、=q3b2+b3,0b3<b2,如b30,则我们继续我们知道，由于小于b的自然数是有限的，因此上述过程不可能无穷下去，在有限步之后，应有余数等于零，设在第n+1步余数为零，于是bn2=qn1bn1+bn,0bn<bn1bn1=qnbn+0上述过程称为辗转相除法，显然(a,b)=(b,b1)=(b1,b2)=(b2,b3)=(bn1,bn)=bn.由于(a,b)=(a,-b),从上述过程可以看到，辗转相除法是求两个整数最大公约数的一个很好的方法。将上述前n个式子联立方程组，消去b1,b2,，bn1,则可得到：ua+vb=bn,其中u,v都是只与q1,q2,qn1有关的整数.设(a,b

4、)=d,则ua+vb=d.于是我们有以下定理：定理若ab0,设(a,b)=d,则存在整数u,v,使得ua+vb=d.注定理中的u,v不唯一.裴蜀定理(a,b)=1的充要条件是存在整数u,v使得ua+vb=1.并且若ab>0,则可以选择u>0,v<0或u<0,而v>0.证明：必要性显然，下面证明充分性.对于整数a,b,存在整数u,v使得ua+vb=1,我们设(a,b)=d,则da,db,于是d1,又d1,所以d=1,即(a,b)=1.若ab>0,则a,b同号，所以要使ua+vb=1成立，u,v必须异号，所以u>0,v<0或u<0,而v>

5、0.综上所述，裴蜀定理成立.5.最大公约数与最小公倍数的性质性质1若(a,b)=1,且abc,则ac;性质2若(a,b)=1,则(a,bc)=(a,c);性质3若(劭bj)=1,i1,2,|m,j1,2,“|n,则9色|国,131b2bn)1性质4若(a,b)=1,且n,m是非负整数，则(an,bm)=1;性质5若ma,mb,则m(a,b);性质6设正整数a,b的质因数分解式如下a=p11P22Pkk,b=p11P22Pkk,其中sk pk ki、i(i=1,2,，k)都是非负整数，记ti=min(i,i),si=max(i,i),i=1,2,k,则有(a,b)=p11p2t2p/k;a,b=

6、pis1p2s2性质7(ma,mb)=|m|(a,b);ma,mb=|m|a,b。p, p|a1,p a性质8(_,_b_)1(a,b)(a,b)性质9若p为素数，则(p,a)6、最小非负余数性质1两个4k+3形式的数的乘积一定是4k+1形式的数;性质2 个平方数被4除, 性质3 个平方数被8除, 性质4 一个平方数被3除, 性质5 个平方数被9除,所得的最小非负余数只可能是 所得的最小非负余数只可能是 所得的最小非负余数只可能是 所得的最小非负余数只可能是0, 1；0, 4;0, 1；0, 1, 8；从上述性质我们容易知道：对任意整数222x, y,有 x y 4k 3; x2 一一一一y8

7、k 3,8k 6,8k 7 ;33xy9k3,9k4,9k5,9k6.222(2)右 2，xy,则 x y n ；-222 1,(4)若 x y n ,则 6 | xy .例1对任意整数x,y,证明：22(1) 8Ixy2;(3)若3，xy,则x2y2n2；例2设a2是给定的正整数，那么任一正整数n必可唯一表示为n局%ak1rarO其中整数k0,0ria1,i0,1,2,|“，k,rk0*我们称nrkak11ar0为n的a进制表示.例3设p是素数，证明：plCp,i1,2,|,p1。(2)对任意正整数a,p|apa(3)若(a,p)=1,则p|ap11。例4设k是正整数，证明：k.k.k(1)

8、(a,b)(a,b)；(2)设a,b是正整数，(a,b)=1,ab=ck,贝Ua=(a,c)k,b=(b,k)k.例5设p是素数，(a,b)=p,求(a2,b),(a3,b),(a2,b3)所可能取的值.例6设正整数n的质因数分解式为n=p11P22pkk,其中i(i=1,2，k)都是非负整数，求n的正约数个数(n)。例7设正整数n的正约数个数为(n),所有这样的约数的和为(n),所有这样的约数的积为(n),求证：(n)(1)(n)=n2;(2)(n)2w6；(3)(n)<'n.(n)想一想设正整数n的质因数分解式为n=p11P22pkk，其中i(i=1,2,，k)都是正整数，则

9、n的所有正因数的和为(n)如何计算.如何证明(a,b)=1,一般情况下寻找裴蜀定理中的恒等式并不容易，在实际中我们一般采用以下手法：(I)寻找恒等式ua+vb=r，设(a,b)=d,则dr,由此进一步证明d=1;(n)寻找适当的r,v,使a(r-vb),由此我们得到恒等式ua+vb=r,再采用(I)法.例8证明(n!+1,(n+1)!+1)=1;(2)(21n+4,14n+3)=1;(3)m>0,n>0,且m为奇数，则(2m1,2n1)1.例9设m,n,a都是正整数，且a2,求证：(am-1,an-1)=a(m,n)-1.注：更一般地有：设a>b,(a,b)=1,则(am-b

10、m,an-bn)=a(m,n)-b(m,n).例10已知a,b,c都是整数，a2+b20,求证直线l：ax+by=c上有整点(x,y)的充要条件是(a,b)c.定理若a,b,c都是整数，且直线l:ax+by=c上有整点(x°,y°),(a,b)=d,a=md,b=nd,则直线l上的所xx0nt有整点为0(t为任意整数).yy0mt证明：(a,b)=d,a=md,b=nd(m,n)=1.容易验证整点(x0+nt,y0-mt)满足直线l的方程，就是说这样的点都在直线l上.ax0by0c设(x1,y1)是直线l上任一整数点，则由0得到axby1ca(x1x0)+b(y1y0)=0

11、m(x1x0)=-n(y1y0)m-n(y1-y0),又(m,n)=1,m(y1-y0)可设y1-y0=-mty1=y0-mt代入m(x1x0)=-n(y1y0),得至Ux1=x0+nt这说明吉线l上所有的整点具君(x0+nt,y0-mt)的形式.综上所述，定理成立.例11设n,a都是正整数，若吗不是整数，则吗必是无理数.例12、设a,b是不全为0的整数，一切形如ax+by(x,yZ)的数中的最小正数是d,求证：d=(a,b).例13、设S=1,2,3,280,求最小的正整数n,使得S的每个有n个元素的子集都含有5个两两互质的数.1、略；2、略;3、证明：Cp占安p，i1,2，lll，p1IP

12、i.CpZ，i1,2J”，p1,i!(pi)!|P(P1)!pp又：p是素数，(p,i!(pi)!)1i1,2,",p1i!(Pi)!|(p1)!,即.(p1)!,Z,i1,2,11,p1i!(pi)!”plCp,i1,2,|,p1(2)对a用数学归纳法证明结合(1)容易证明；(3)由(2)及性质1容易证明.4、证明：(1) (ak,bk) (a,b)kkka b(a,b) , (a,b)kkn a ba b/,1, ,1,(a,b)(a,b)(a,b)(a,b)(ak,bk) (a,b)kk 1k kkk 1kkk(2) a = a(a ,b) (a , c ) (a,c) ; b

13、 = b(b , a) (b ,c ) (b,c)5、解：(a, b) = p 可设 a pa，b pb 且上)1,则222(a2, b)=(pa1,pb1) p(pa1,b1) p(p,b) p或 p(a3,b)= (p3a13,pb1) p(p2a；,b1)p(p2,b1)p或 p2或 p3,2,3、/ _2_2 _3_3_2,_2 _3、_2Z_ 2 一、2- 3(a2, b3)= (p a，p b1 )p (a1，pb)p (a1，p)p 或 p6、解：显然n的正约数x的质因数分解式应为x = p1 1 p2 2 pk k ,其中0 ii.i=1,2,k,由于i有1+ i种取法，故由乘

14、法原理知道n的正约数个数(n) = (1+ 1)(1+ 2)-(1+ k)7、证明：(1)设集合M=d d是n的正因数,显然若d M,则： M.对于每一个d M ,建立映射f: d n ,显然映射f是从M到M的一一映射.于是(n)= d2(n) = d = (d ) = n = nd M d M d d M d d M(n)(n)(n) = n 2(2)设 Mi = d d M,且 d Jn , M 2 = d d M,且 d 品建立映射g： d n, d Mi,则显然映射g是从集合Mi到M2的一一映射.所以是(n) =card(M) = card(M M2) cardMi+ cardM2 =

15、 2 cardM 12 , n .card(M 1)=card(M 2),于(3)由平均值不等式定理有:d(n) dn(n)(n)(n) d (n) (n) n ,d M(n!+1),而(n!, n!+1)=18、证明：(1)设(n!+1,(n+1)!+1)=d.(n!+1)(n+1)-(n+1)!+1)=n，dndn!,又d1. d1d=1,即(n!+1,(n+1)!+1)=1.(2)(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,1)=1设(2m1,2n1)d,则2m1pd,2n1qd2mn(pd1)nk1d1,2mn(qd1)mk2d1k1d1k2d1(k2k1)d2d

16、|2d1或2,但2m1,2n1都是奇数，d1,即(2m1,2n1)19、证明：设(am-1,an-1)=d,(m,n)=x,则又可设m=px,n=qx,(p,q)=1. (ax-1)(ax)p-1,(axT)(ax)q-1,即(a(m,n)-1)(am-1)且(a(m,n)-1)(an-1)(a(m,n)-1)d.(1)另一方面，由于p>0,q>0且(p,q)=1,所以存在正整数u,v使up-vq=1um-vn=x又(am-1)(aum-1),d(am-1) .d(aum-1),同理可证d(avn-1), d(aum-1)-(avn-1),即davn(aumvn1)davn(ax-

17、1)-1d(an-1),且(an-1,an)=1,/.(d,an)=1(d,avn)=1d(ax-1),即d(a(m,n)-1)(2)由(1)(2)两个方面可得出d=a(m,n)-1即(am-1,an-1)=a(m,n)-1成立.10、证明：必要性显然，下面证明充分性.设(a,b)=d,于是存在整数u,v使得ua+vb=d由(a,b)c,可设c=kda(ku)+b(kv)=c所以直线l上有整点(ku,kv),充分性成立.综上所述直线l:ax+by=c上有整点(x,y)的充要条件是(a,b)cii、证明：设n/a是非整数的有理数，则n/ac,bi,(b,c)1bnc于是ab|c,因(b,c)1,

18、所以(b,c)1,但b1,所以bn才cn矛盾b112、证明：记d=axo+byo,d(a,b)设ax+by=dq+r,0rd1,则ra(xqx0)b(yqy0)axby也是形如ax+by(x,yZ)的数，由0rd1及d是形如ax+by(x,yZ)的数中的最小正数知道r=0,即ax+by=dq所以d整除一切形如ax+by(x,yZ)的数，取x=1,y=0,得d|a,取x=0,y=1得d|b,所以d是a,b的公约数，故dd,又d|a,d|b,故d|ax0by0,即d|d,从而dddd13、解：考虑如下四个集合：Ak=S中可被k整除的自然数,k=2,3,5,7.令A=A2A3A5Ai.由容斥原理不难算出集合A中共有216个元素，另一方面从A中任取5个数必有两个数在同一个Ak中，从而它们不互质，故n217.下面考虑n=217能否满足要求.考虑如下六个集合；B1=1和S中所有的质数,B2=1319,