算法設(shè)計數(shù)論初步

數(shù)論初步

1/23/20241最大公約數(shù)

1/23/20242整除的根本性質(zhì)定理1：①對所有a,1|a.②對所有a,a|0.③對所有a,a|a.④假設(shè)a|b且b|c,那么a|c.⑤假設(shè)a|b,那么對任意的c,有ac|bc.⑥假設(shè)ac|bc且c≠0,那么a|b.1/23/20243整除的根本性質(zhì)⑦假設(shè)a|b且a|c,那么對任意的整數(shù)m,n,有a|(bm+cn).證明因為a|b且a|c,故b=aq1和c=aq2.于是,bm+cn=a(q1m+q2n),

所以,a|(bm+cn).⑧假設(shè)c≠0且a|b,那么ac|bc.1/23/20244例證明：假設(shè)3|n且7|n,那么21|n.證明因為3|n,所以n=3m,因此7|3m.再由7|7m得7|(7m-2*3m)=m.所以,21|n.1/23/20245最大公約數(shù)定理2設(shè)a和b都是正整數(shù),且a>b,

a=bq+r0<r<b

其中q和r都是正整數(shù).那么:①a和b的任一公約數(shù)也是b和r的公約數(shù)；②b和r的任一公約數(shù)也是a和b的公約數(shù)；③(a,b)=(b,r);④假設(shè)(a,b)=d,那么(a|d,b|d)=1.1/23/20246a=bq+r

①a和b的公約數(shù)也是b和r的公約數(shù)；證明①假設(shè)d|a且d|b,那么d|(a-bq)即d|r.這即說明:假設(shè)d是a和b的公約數(shù),d必是b和r的公約數(shù).②假設(shè)d|b且d|r,那么:d|(bq＋r)即d|a.這即是說假設(shè)d是b和r的公約數(shù),d也必是a和b的公約數(shù).1/23/20247a=bq+r③由①和②知,a和b的公約數(shù)集合等于b和r的公約數(shù)集合，故兩個集合的最大整數(shù)相同,即(a,b)=(b,r).(a,b)=(b,r)的證明也可不基于①和②,另有證法.因為(a,b)|a,(a,b)|b,故(a,b)|(a-bq)即(a,b)|r.因此(a,b)≤(b,r).同理可證

(b,r)≤(a,b).于是得到(a,b)=(b,r).1/23/20248最大公約數(shù)(Euclid)歐幾里德算法.設(shè):a≥b＞0,且:a=bq1+r1,0＜rl＜bb=r1q2+r2,0＜r2＜r1r1=r2q3+r3,0＜r3＜r2…….rn-2=rn-1qn+rn,0＜rn＜rn-1rn-1=rnqn+1+0那么(a,b)=rn.1/23/20249最大公約數(shù)證明:由于:b＞r1＞r2＞…＞rn＞0,故歐幾里德算法中的帶余除法必在有限步內(nèi)得到一個余數(shù)是零的等式,即rn+1=0.根據(jù)定理2可知：

(a,b)=(b,r1)=…=(rn-1,rn)=(rn,0)=rn

.歐幾里德算法也稱輾轉(zhuǎn)相除法.1/23/202410最大公約數(shù)在歐幾里德算法中,由:rn=rn-2-rn-1qn,和

rn-1=rn-3-rn-2qn-1,得rn=rn-2(1+qnqn-1)-rn-3qn,再將rn-2=rn-4-rn-3qn-2代入上式,如此繼續(xù)下去,最后得到:

rn=as+bt,

s和t是整數(shù).于是有(a,b)是a和b線性組合表示定理.(Euclid)歐幾里德算法.設(shè):a≥b＞0,且:a=bq1+r1,b=r1q2+r2,r1=r2q3+r3,

…….rn-2=rn-1qn+rn,

rn-1=rnqn+1+0那么(a,b)=rn.1/23/202411最大公約數(shù)定理3假設(shè)任給整數(shù)a>0,b>0,那么存在整數(shù)x和y,使得(a,b)=ax+by.例

①用歐幾里德算法求(1997,57).②用1997和57的線性組合表示(1997,57).③求1997和57的所有公約數(shù)．1/23/202412答案①用歐幾里德算法求(1997,57).②用1997和57的線性組合表示(1997,57)．③求1997和57的所有公約數(shù)．解①用下劃線標(biāo)識余數(shù)．1997＝57·35+257＝2·28+12＝l·2+0因此,(1997,57)=l,即1997和57是互素的.1/23/202413答案①用下劃線標(biāo)識余數(shù)．1997＝57·35+257＝2·28+12＝l·2+0②1=57-2·28=57-(1997-57·35)·28=-28·1997+(1+35·28)·57=-28·1997+981·57③由于1997和57是互素的,公因數(shù)只有1.1/23/202414最大公約數(shù)定理4設(shè)a1,a2,,akZ，記

A={y|y=a1x1a2x2akxk，

xiZ，ik}.如果y0是集合A中最小的正數(shù)，那么

y0=(a1,a2,,ak).即a1,,ak的最大公約數(shù)等于a1,,ak的所有整系數(shù)線性組合所形成集合A中的最小正整數(shù).證明設(shè)d是a1,a2,,ak的一個公約數(shù)，那么dy0，所以dy0。1/23/202415A=

{y|y=a1x1

a2x2

akxk}.設(shè)y0=a1x1akxk，對任意的

y=a1x1akxkA，由帶余除法，存在q,r0Z，使得y=qy0r0，0r0<y0.因此r0=yqy0=a1(x1qx1)

an(xnqxn)A.如果r00，那么，因為0<r0<y0，所以r0是A中比y0還小的正數(shù)，這與y0的定義矛盾。所以r0=0，即y0y。顯然aiA〔1in〕，所以y0整除每個ai〔1in〕。即y0是a1,a2,,ak的公約數(shù)。證畢。1/23/202416不定方程

1/23/202417不定方程這里介紹的不定方程，是指整系數(shù)代數(shù)方程，并且限定它的解是整數(shù)。設(shè)a1,a2,,an是非零整數(shù)，b是整數(shù)，稱關(guān)于未知數(shù)x1,x2,,xn的方程

a1x1a2x2anxn=b(1)

是n元一次不定方程。假設(shè)存在整數(shù)x10,x20,,xn0滿足方程(1)，那么稱(x10,x20,,xn0)是方程(1)的解，或說x1=x10，x2=x20，，xn=xn0是方程(1)的解。1/23/202418a1x1

a2x2

anxn=b(1)

定理5方程(1)有解的充要條件是

(a1,a2,,an)b。(2)證明記d=(a1,a2,,an)。假設(shè)方程(1)有解，設(shè)為(x1,x2,,xn)。那么由dai〔1in〕及整除的性質(zhì)容易知道式(2)成立。必要性得證。另一方面由定理4，存在整數(shù)y1,y2,,yn使得

a1y1a2y2anyn=(a1,a2,,an)=d。

因此，假設(shè)式(2)成立，那么

就是方程(1)的解，

充分性得證。證畢。

1/23/202419不定方程定理6設(shè)a，b，c是整數(shù)，方程

axby=c(3)

假設(shè)有解(x0,y0)，那么它的一切解具有

，tZ(4)

的形式，其中1/23/202420不定方程證明容易驗證，由式(4)確定的x與y滿足方程(3)。下面證明，方程(3)的解都可寫成式(4)中的形式。

設(shè)(x,y)是方程(3)的解，那么由

ax0by0=axby=c

得到a(xx0)=b(yy0)，1/23/202421不定方程定理7對于任意的整數(shù)a，b，c，下面的結(jié)論成立：

(ⅰ)由bac及(a,b)=1可以推出bc；

(ⅱ)由bc，ac及(a,b)=1可以推出abc。證明(ⅰ)假設(shè)(a,b)=1，那么存在整數(shù)x與y，使得axby=1。因此acxbcy=c。(*)由上式及bac得到bc。結(jié)論(ⅰ)得證；(ⅱ)假設(shè)(a,b)=1，那么存在整數(shù)x，y使得式(*)成立。由bc與ac得到abac，abbc，再由式(*)得到abc。結(jié)論(ⅱ)得證。證畢。1/23/202422不定方程ax0

by0=ax

by=c

得到a(x

x0)=

b(y

y0)，

由此，以及

和定理7，得到x

x0，因此存在整數(shù)t，使得

證畢。1/23/202423不定方程解方程ax

by=c的步驟：(ⅰ)判斷方程是否有解，即(a,b)

c是否成立；(ⅱ)利用輾轉(zhuǎn)相除法求出x0，y0，使得

ax0

by0=(a,b)；

(ⅲ)寫出方程的解1/23/202424例例1：求不定方程18x24y=9的解。例2：求不定方程3x6y=15的解。解(3,6)=315，所以方程有解。由輾轉(zhuǎn)相除法〔或直接觀察〕，可知x=1，y=1是3x6y=