輾轉(zhuǎn)相除法與裴蜀定理

1、二、輾轉(zhuǎn)相除法與裴蜀定理4、輾轉(zhuǎn)相除法與裴蜀定理定義對于整數(shù)a,b,若ab,則稱a是b的約數(shù)；而b是a的倍數(shù).定義對于不全為零的整數(shù)a/i121",n),若aai對i1,21|,n都成立，則稱a是a1，a2,|4的公約定義對于非零整數(shù)al1,2j“，n),若aiaxi12“|,n都成立，則稱a是agj”小的公倍數(shù).定義整數(shù)ai(i1,2,|“，n)的公約數(shù)中，最大的一個，稱為整數(shù)a/i1,2,|",n)的最大公約數(shù)，記作(a1,a2,|an).整數(shù)a/i1,2,W，n)的公倍數(shù)中，最小的一個，稱為整數(shù)ai(i1,2,|“，n)的最小公倍數(shù)，記作4e2,"同.定義若

2、(a,b)=1,則稱a,b互質(zhì)或互素.顯然有下列性質(zhì)：性質(zhì)1(a,b)=(b,a)=(a,-b)=(-a,-b);性質(zhì)2ab=(a,b)a,b,特別地當a>0,b>0時，ab=(a,b)a,b.卜面我們介紹輾轉(zhuǎn)相除法與裴蜀定理定理若a=qb+r,則(a,b)=(b,r).注：本定理也可寫成：(a,b)=(abq,b),就是說，在計算(a,b)時，可用b的任意整數(shù)倍數(shù)bq去減a.下面我們介紹輾轉(zhuǎn)相除法，對于給定的整數(shù)a,b(b>0),我們反復(fù)運用帶余除法就有：a=q1b+b1,0b1<b,如b10,則我們繼續(xù)b=q2b1+b2,0b2<b1,如b20,則我們繼續(xù)b1

3、=q3b2+b3,0b3<b2,如b30,則我們繼續(xù)我們知道，由于小于b的自然數(shù)是有限的，因此上述過程不可能無窮下去，在有限步之后，應(yīng)有余數(shù)等于零，設(shè)在第n+1步余數(shù)為零，于是bn2=qn1bn1+bn,0bn<bn1bn1=qnbn+0上述過程稱為輾轉(zhuǎn)相除法，顯然(a,b)=(b,b1)=(b1,b2)=(b2,b3)=(bn1,bn)=bn.由于(a,b)=(a,-b),從上述過程可以看到，輾轉(zhuǎn)相除法是求兩個整數(shù)最大公約數(shù)的一個很好的方法。將上述前n個式子聯(lián)立方程組，消去b1,b2,，bn1,則可得到：ua+vb=bn,其中u,v都是只與q1,q2,qn1有關(guān)的整數(shù).設(shè)(a,b

4、)=d,則ua+vb=d.于是我們有以下定理：定理若ab0,設(shè)(a,b)=d,則存在整數(shù)u,v,使得ua+vb=d.注定理中的u,v不唯一.裴蜀定理(a,b)=1的充要條件是存在整數(shù)u,v使得ua+vb=1.并且若ab>0,則可以選擇u>0,v<0或u<0,而v>0.證明：必要性顯然，下面證明充分性.對于整數(shù)a,b,存在整數(shù)u,v使得ua+vb=1,我們設(shè)(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.最大公約數(shù)與最小公倍數(shù)的性質(zhì)性質(zhì)1若(a,b)=1,且abc,則ac;性質(zhì)2若(a,b)=1,則(a,bc)=(a,c);性質(zhì)3若(劭bj)=1,i1,2,|m,j1,2,“|n,則9色|國,131b2bn)1性質(zhì)4若(a,b)=1,且n,m是非負整數(shù)，則(an,bm)=1;性質(zhì)5若ma,mb,則m(a,b);性質(zhì)6設(shè)正整數(shù)a,b的質(zhì)因數(shù)分解式如下a=p11P22Pkk,b=p11P22Pkk,其中sk pk ki、i(i=1,2,，k)都是非負整數(shù)，記ti=min(i,i),si=max(i,i),i=1,2,k,則有(a,b)=p11p2t2p/k;a,b=

6、pis1p2s2性質(zhì)7(ma,mb)=|m|(a,b);ma,mb=|m|a,b。p, p|a1,p a性質(zhì)8(_,_b_)1(a,b)(a,b)性質(zhì)9若p為素數(shù)，則(p,a)6、最小非負余數(shù)性質(zhì)1兩個4k+3形式的數(shù)的乘積一定是4k+1形式的數(shù);性質(zhì)2 個平方數(shù)被4除, 性質(zhì)3 個平方數(shù)被8除, 性質(zhì)4 一個平方數(shù)被3除, 性質(zhì)5 個平方數(shù)被9除,所得的最小非負余數(shù)只可能是 所得的最小非負余數(shù)只可能是 所得的最小非負余數(shù)只可能是 所得的最小非負余數(shù)只可能是0, 1；0, 4;0, 1；0, 1, 8；從上述性質(zhì)我們?nèi)菀字溃簩θ我庹麛?shù)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對任意整數(shù)x,y,證明：22(1) 8Ixy2;(3)若3，xy,則x2y2n2；例2設(shè)a2是給定的正整數(shù)，那么任一正整數(shù)n必可唯一表示為n局%ak1rarO其中整數(shù)k0,0ria1,i0,1,2,|“，k,rk0*我們稱nrkak11ar0為n的a進制表示.例3設(shè)p是素數(shù)，證明：plCp,i1,2,|,p1。(2)對任意正整數(shù)a,p|apa(3)若(a,p)=1,則p|ap11。例4設(shè)k是正整數(shù)，證明：k.k.k(1)

8、(a,b)(a,b)；(2)設(shè)a,b是正整數(shù)，(a,b)=1,ab=ck,貝Ua=(a,c)k,b=(b,k)k.例5設(shè)p是素數(shù)，(a,b)=p,求(a2,b),(a3,b),(a2,b3)所可能取的值.例6設(shè)正整數(shù)n的質(zhì)因數(shù)分解式為n=p11P22pkk,其中i(i=1,2，k)都是非負整數(shù)，求n的正約數(shù)個數(shù)(n)。例7設(shè)正整數(shù)n的正約數(shù)個數(shù)為(n),所有這樣的約數(shù)的和為(n),所有這樣的約數(shù)的積為(n),求證：(n)(1)(n)=n2;(2)(n)2w6；(3)(n)<'n.(n)想一想設(shè)正整數(shù)n的質(zhì)因數(shù)分解式為n=p11P22pkk，其中i(i=1,2,，k)都是正整數(shù)，則

9、n的所有正因數(shù)的和為(n)如何計算.如何證明(a,b)=1,一般情況下尋找裴蜀定理中的恒等式并不容易，在實際中我們一般采用以下手法：(I)尋找恒等式ua+vb=r，設(shè)(a,b)=d,則dr,由此進一步證明d=1;(n)尋找適當?shù)膔,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為奇數(shù)，則(2m1,2n1)1.例9設(shè)m,n,a都是正整數(shù)，且a2,求證：(am-1,an-1)=a(m,n)-1.注：更一般地有：設(shè)a>b,(a,b)=1,則(am-b

10、m,an-bn)=a(m,n)-b(m,n).例10已知a,b,c都是整數(shù)，a2+b20,求證直線l：ax+by=c上有整點(x,y)的充要條件是(a,b)c.定理若a,b,c都是整數(shù)，且直線l:ax+by=c上有整點(x°,y°),(a,b)=d,a=md,b=nd,則直線l上的所xx0nt有整點為0(t為任意整數(shù)).yy0mt證明：(a,b)=d,a=md,b=nd(m,n)=1.容易驗證整點(x0+nt,y0-mt)滿足直線l的方程，就是說這樣的點都在直線l上.ax0by0c設(shè)(x1,y1)是直線l上任一整數(shù)點，則由0得到axby1ca(x1x0)+b(y1y0)=0

11、m(x1x0)=-n(y1y0)m-n(y1-y0),又(m,n)=1,m(y1-y0)可設(shè)y1-y0=-mty1=y0-mt代入m(x1x0)=-n(y1y0),得至Ux1=x0+nt這說明吉線l上所有的整點具君(x0+nt,y0-mt)的形式.綜上所述，定理成立.例11設(shè)n,a都是正整數(shù)，若嗎不是整數(shù)，則嗎必是無理數(shù).例12、設(shè)a,b是不全為0的整數(shù)，一切形如ax+by(x,yZ)的數(shù)中的最小正數(shù)是d,求證：d=(a,b).例13、設(shè)S=1,2,3,280,求最小的正整數(shù)n,使得S的每個有n個元素的子集都含有5個兩兩互質(zhì)的數(shù).1、略；2、略;3、證明：Cp占安p，i1,2，lll，p1IP

12、i.CpZ，i1,2J”，p1,i!(pi)!|P(P1)!pp又：p是素數(shù)，(p,i!(pi)!)1i1,2,",p1i!(Pi)!|(p1)!,即.(p1)!,Z,i1,2,11,p1i!(pi)!”plCp,i1,2,|,p1(2)對a用數(shù)學(xué)歸納法證明結(jié)合(1)容易證明；(3)由(2)及性質(zhì)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 可設(shè) 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的正約數(shù)x的質(zhì)因數(shù)分解式應(yīng)為x = p1 1 p2 2 pk k ,其中0 ii.i=1,2,k,由于i有1+ i種取法，故由乘

14、法原理知道n的正約數(shù)個數(shù)(n) = (1+ 1)(1+ 2)-(1+ k)7、證明：(1)設(shè)集合M=d d是n的正因數(shù),顯然若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)設(shè) 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)設(shè)(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設(shè)(2m1,2n1)d,則2m1pd,2n1qd2mn(pd1)nk1d1,2mn(qd1)mk2d1k1d1k2d1(k2k1)d2d

16、|2d1或2,但2m1,2n1都是奇數(shù)，d1,即(2m1,2n1)19、證明：設(shè)(am-1,an-1)=d,(m,n)=x,則又可設(shè)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,所以存在正整數(shù)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、證明：必要性顯然，下面證明充分性.設(shè)(a,b)=d,于是存在整數(shù)u,v使得ua+vb=d由(a,b)c,可設(shè)c=kda(ku)+b(kv)=c所以直線l上有整點(ku,kv),充分性成立.綜上所述直線l:ax+by=c上有整點(x,y)的充要條件是(a,b)cii、證明：設(shè)n/a是非整數(shù)的有理數(shù)，則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)設(shè)ax+by=dq+r,0rd1,則ra(xqx0)b(yqy0)axby也是形如ax+by(x,yZ)的數(shù)，由0rd1及d是形如ax+by(x,yZ)的數(shù)中的最小正數(shù)知道r=0,即ax+by=dq所以d整除一切形如ax+by(x,yZ)的數(shù)，取x=1,y=0,得d|a,取x=0,y=1得d|b,所以d是a,b的公約數(shù)，故dd,又d|a,d|b,故d|ax0by0,即d|d,從而dddd13、解：考慮如下四個集合：Ak=S中可被k整除的自然數(shù),k=2,3,5,7.令A(yù)=A2A3A5Ai.由容斥原理不難算出集合A中共有216個元素，另一方面從A中任取5個數(shù)必有兩個數(shù)在同一個Ak中，從而它們不互質(zhì)，故n217.下面考慮n=217能否滿足要求.考慮如下六個集合；B1=1和S中所有的質(zhì)數(shù),B2=1319,