算法设计数论初步

数论初步

1/23/20241最大公约数

1/23/20242整除的根本性质定理1：①对所有a,1|a.②对所有a,a|0.③对所有a,a|a.④假设a|b且b|c,那么a|c.⑤假设a|b,那么对任意的c,有ac|bc.⑥假设ac|bc且c≠0,那么a|b.1/23/20243整除的根本性质⑦假设a|b且a|c,那么对任意的整数m,n,有a|(bm+cn).证明因为a|b且a|c,故b=aq1和c=aq2.于是,bm+cn=a(q1m+q2n),

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

a=bq+r0<r<b

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

①a和b的公约数也是b和r的公约数；证明①假设d|a且d|b,那么d|(a-bq)即d|r.这即说明:假设d是a和b的公约数,d必是b和r的公约数.②假设d|b且d|r,那么:d|(bq＋r)即d|a.这即是说假设d是b和r的公约数,d也必是a和b的公约数.1/23/20247a=bq+r③由①和②知,a和b的公约数集合等于b和r的公约数集合，故两个集合的最大整数相同,即(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最大公约数(Euclid)欧几里德算法.设: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最大公约数证明:由于:b＞r1＞r2＞…＞rn＞0,故欧几里德算法中的带余除法必在有限步内得到一个余数是零的等式,即rn+1=0.根据定理2可知：

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

.欧几里德算法也称辗转相除法.1/23/202410最大公约数在欧几里德算法中,由: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代入上式,如此继续下去,最后得到:

rn=as+bt,

s和t是整数.于是有(a,b)是a和b线性组合表示定理.(Euclid)欧几里德算法.设: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最大公约数定理3假设任给整数a>0,b>0,那么存在整数x和y,使得(a,b)=ax+by.例

①用欧几里德算法求(1997,57).②用1997和57的线性组合表示(1997,57).③求1997和57的所有公约数．1/23/202412答案①用欧几里德算法求(1997,57).②用1997和57的线性组合表示(1997,57)．③求1997和57的所有公约数．解①用下划线标识余数．1997＝57·35+257＝2·28+12＝l·2+0因此,(1997,57)=l,即1997和57是互素的.1/23/202413答案①用下划线标识余数．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是互素的,公因数只有1.1/23/202414最大公约数定理4设a1,a2,,akZ，记

A={y|y=a1x1a2x2akxk，

xiZ，ik}.如果y0是集合A中最小的正数，那么

y0=(a1,a2,,ak).即a1,,ak的最大公约数等于a1,,ak的所有整系数线性组合所形成集合A中的最小正整数.证明设d是a1,a2,,ak的一个公约数，那么dy0，所以dy0。1/23/202415A=

{y|y=a1x1

a2x2

akxk}.设y0=a1x1akxk，对任意的

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

an(xnqxn)A.如果r00，那么，因为0<r0<y0，所以r0是A中比y0还小的正数，这与y0的定义矛盾。所以r0=0，即y0y。显然aiA〔1in〕，所以y0整除每个ai〔1in〕。即y0是a1,a2,,ak的公约数。证毕。1/23/202416不定方程

1/23/202417不定方程这里介绍的不定方程，是指整系数代数方程，并且限定它的解是整数。设a1,a2,,an是非零整数，b是整数，称关于未知数x1,x2,,xn的方程

a1x1a2x2anxn=b(1)

是n元一次不定方程。假设存在整数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)。假设方程(1)有解，设为(x1,x2,,xn)。那么由dai〔1in〕及整除的性质容易知道式(2)成立。必要性得证。另一方面由定理4，存在整数y1,y2,,yn使得

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

因此，假设式(2)成立，那么

就是方程(1)的解，

充分性得证。证毕。

1/23/202419不定方程定理6设a，b，c是整数，方程

axby=c(3)

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

，tZ(4)

的形式，其中1/23/202420不定方程证明容易验证，由式(4)确定的x与y满足方程(3)。下面证明，方程(3)的解都可写成式(4)中的形式。

设(x,y)是方程(3)的解，那么由

ax0by0=axby=c

得到a(xx0)=b(yy0)，1/23/202421不定方程定理7对于任意的整数a，b，c，下面的结论成立：

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

(ⅱ)由bc，ac及(a,b)=1可以推出abc。证明(ⅰ)假设(a,b)=1，那么存在整数x与y，使得axby=1。因此acxbcy=c。(*)由上式及bac得到bc。结论(ⅰ)得证；(ⅱ)假设(a,b)=1，那么存在整数x，y使得式(*)成立。由bc与ac得到abac，abbc，再由式(*)得到abc。结论(ⅱ)得证。证毕。1/23/202422不定方程ax0

by0=ax

by=c

得到a(x

x0)=

b(y

y0)，

由此，以及

和定理7，得到x

x0，因此存在整数t，使得

证毕。1/23/202423不定方程解方程ax

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

c是否成立；(ⅱ)利用辗转相除法求出x0，y0，使得

ax0

by0=(a,b)；

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