算法设计-数论初步.pptVIP

1.7 对偶与范式 数论初步 最大公约数 整除的基本性质 定理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. 整除的基本性质 ⑦若 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. 例 证明：若 3|n且7|n,则21|n. 证明 因为3|n, 所以n=3m, 因此7|3m. 再由 7|7m得7|(7m-2*3m)=m. 所以, 21|n. 最大公约数 定理2 设a和b都是正整数, 且ab,  a=bq+r 0rb其中q和r都是正整数. 则: ①a和b的任一公约数也是b和r的公约数； ②b和r的任一公约数也是a和b的公约数； ③(a,b)=(b,r); ④若(a,b)=d, 则 (a|d, b|d)=1. a=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的公约数. a=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). 最大公约数 (Euclid)欧几里德算法. 设: a≥b＞0, 且: a=bq1+r1, 0＜rl＜b b=r1q2+r2, 0＜r2＜r1 r1=r2q3+r3, 0＜r3＜r2 ……. rn-2=rn-1qn+rn, 0＜rn＜rn-1 rn-1=rnqn+1+0 则(a,b)=rn. 最大公约数 证明: 由于: b＞r1＞r2＞…＞rn＞0, 故欧几里德算法中的带余除法必在有限步内得到一个余数是零的等式, 即rn+1=0. 根据定理2可知：(a,b)=(b,r1)=…=(rn-1,rn)=(rn,0)=rn . 欧几里德算法也称辗转相除法. 最大公约数 在欧几里德算法中, 由: 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线性组合表示定理. 最大公约数 定理 3 若任给整数 a0, b0, 则存在整数x和 y, 使得(a,b)= ax+by. 例 ①用欧几里德算法求(1997,57). ②用1997和57的线性组合表示(1997,57). ③求1997和57的所有公约数． 答案 ①用欧几里德算法求(1997,57). ②用1997和57的线性组合表示(1997,57)． ③求1997和57的所有公约数． 解 ①用下划线标识余数． 1997＝57·35 + 2 57＝2·28 + 1 2＝l·2 + 0 因此, (1997,57)=l, 即1997和57是互素的. 答案 ①用下划线标识余数． 1997＝57·35 + 2 57＝2·28 + 1 2＝l·2 + 0 ② 1=57-2·28 =57-(1997-57·35)·28 =-28·1997+(1+35·28)·57 =-2