2最大公因数辗转相除法整除性质最小公倍数

1、最大公因数与辗转相除法 整除的性质与最小公倍数 复习复习 定义定义 设设 a,b是任意两个整数，其中是任意两个整数，其中b?0 ，如果存在一个整数如果存在一个整数 q使得使得 等式等式 a?bq(1)成立，我们就说成立，我们就说 b整除整除 a或或a可被可被 b整除整除, , 记作记作ba, , 此时我们把此时我们把 b叫作叫作 a的因数的因数, , 把把 a叫作叫作b的倍数的倍数. . 如果如果(1)(1)里的整数里的整数q不存在不存在, ,我们就说我们就说b不能整除不能整除a或或a不被不被 b整除整除, , 记作记作b |a. 定理定理 1(传递性传递性 )若若a是是b的倍数的倍数 ,b是

2、是c的的倍数倍数,则则a是是c的倍数的倍数 ,也就是也就是b a,cb?c a. 证证 ba,cb就是说存在两个整数就是说存在两个整数a1,b1使得使得a?a1b,b?b1c成立成立,因此因此 a?(a1b1)c,但但a1b1是一个整数是一个整数 ,故故c a. 定理定理 2若若a,b都是都是 m的倍数的倍数 ,则则a?b也是也是 m的倍数的倍数 . 证证 a,b是是m的倍数的意义就是存在两个整数的倍数的意义就是存在两个整数a1,b1,使得使得a?a1m ,b?b1m .因此因此 a?b?(a1?b1)m ,但但a1?b1是整数是整数 ,故故 a?b是是m的倍数的倍数 . 定理 3若a1,a2

3、,q1,q2,?,an都是 m 的倍数 ,qn是任意 n个整数 ,则q1a1?q2a2?qnan是m 的倍数 . 定理定理 4 4 (带余数除法带余数除法)若若 a,b是两个整数是两个整数, ,其中其中 b0 , q及及r,使得使得a?bq?r,0?r?b.,而且而且 q及及r是惟一的是惟一的.(2)则存在着两个则存在着两个整数整数成立成立带余数除法的内涵带余数除法的内涵 ?它可以看作是整除的推广，也可以用带余除法定理来定义整除性 ?将一个未知的整数表示为小于除数的余数，将整数进行分类，从而可将无限问题转化为有限问题 ?其他应用：辗转相除法、进制间转换算法 2 最大公因数与辗转相除法最大公因数

4、与辗转相除法 定义定义 设设 a1,a2,的一个的一个公因数公因数. 整数整数 a1,a2,a1,a2,an的公因数中最大的一的公因数中最大的一 个叫作个叫作最大最大,an),若若(a1,a2,an)?1, 我们说我们说,an中每两个整数中每两个整数互质，互质，公公因数因数,记作记作(a1,a2,an是是 n(n?2) 个整数个整数.若整数若整数d,an是它们之中每一个的因数是它们之中每一个的因数 ,那么那么d就叫作就叫作a1,a2,an互质或互质或互素互素,若若a1,a2,我们就说它我们就说它们们两两两互质两互质. 显然,若整数 a1,a2,(a1,a2,an两两互质,则,an)?1, 反过

5、来却不一定成立,an不全为零,则(a1,a2,an)且若 a1,a2,是存在的. 例1: 2和2 n?1 互素; 例2: 6,10,-15是互素的,但它们任意两个数不互素,因为(6,10)=2,(10,15)=5,(-15,6)=3. 定理1 若 a1,a2,整数,则 (i) a1,a2, (ii) (a1,a2,an是任意 n个不全为零的,an与a1,a2,an的公因数相同；,an),an)?(a1,a2, 证 设 d是 a1,a2,d ai,i?1,2,a1,a2,an的任一公因数.由定义,n,故 d是,n,因而d ai,i?1,2,an的一个公因数,同法可证, a1,a2,an的一个公因

6、数.,an的任一公因数都是a1,a2,故a1,a2,an与a1,a2,an有相同的公因数,即(i)获证.由(i)立得(ii). 定理2 若b是任一正整数,则(i) 0与b的公因数就是b的因数,反之,b的因数也是0与b的公因数. (ii) (0 ,b)?b. 证 显然0与b的公因数是b的因数.由于任何非零整数都是0的因数,故 b的因数也就是0， b的公因数,于是(i)获证.其次,我们立刻知道 b的最大公因数是 b;而0， b的最大公因数是 b的最大公因数,故 (0, b)?b. 推论2.1 若b是任一非零整数,则 (0, b)?b. 定理 3设a,b,c是任意三个不全为 0的整数 ,且a?bq?

7、c,其中 q是非零整 数,则a,b与b,c有相同的公因数 ,因而 (a,b)?(b,c). 证 设d是a,b的任一公因数 ,由定义 d a,db.由1定理 3,d是c?a?(?q)b的因数 ,因而 d是b,c的一个公因数 . 于是定理的前一部分获证.第二部分显 然随之成立 . 设a,b是任意两个正整数,由带余数除法 ,我们有下面的系 列等式： a?bq1?r1,0?r1b, b?r1q2?r2,0?r2r1, rn-2?rn-1qn?rn,0?rn0,0,则继续对则继续对(2 (2 -1, 2-1, 2 -1)-1)作同样的讨论作同样的讨论, ,由辗转由辗转nr1相除法知，结论成立相除法知，结

8、论成立 . . 显见显见, 2, 2用任一大于用任一大于1 1的自然数的自然数a代替代替, ,结论都成立结论都成立. . 定理定理5 5 设设a,b是任意两个不全为零的整数是任意两个不全为零的整数 (i) (i) 若若m是任意一正整数，则是任意一正整数，则?am ,bm?a,b?m?a b?a,b?(ii)若若?是是a,b的任一公因数，则的任一公因数，则?,?，? ?ab? 特别特别?,?1a,ba,b? ? 证证 当当a,b有一为零时，定理显然成立，今设有一为零时，定理显然成立，今设 a,b都都 不为零不为零. .(1) 由定理由定理1, 1,?am ,bm?a m ,b m?,?a,b?m

9、?a ,b?m .因此不妨假定因此不妨假定 a,b都是正数都是正数. . 公式公式(1)(1)里各式两边同里各式两边同乘以乘以m ,即得即得am?bm?q1?r1m ,0?r1m?bm ,bm?r1m?q2?r2m ,0?r2m?r1mrn?1m?rnm?qn?1由定理由定理4 得得?am ,bm?rnm?a,b?m ,因而因而(i)(i)获证获证. .(ii ii)由由(i)(i)及定理及定理 1, 1,? a?b?a b?,?,?a , b?a,b ,? ?a b?a,b?故故?,? ?ab?当当?= =?a,b?时，上式即为时，上式即为?,?1?a,b? ?a,b?现在来研究两个以上整数

10、的最大公因数现在来研究两个以上整数的最大公因数 . .由定理由定理1 及及2 ，不妨假设，不妨假设a1,a2,令令?a1,a2?d2,?d2,a3?d3,an是任意是任意n 个正整数个正整数.,?dn?1,an?dn(2)定理定理6若若a1,a2,an是是n 个整数个整数, ,则则?a1,a2,an?dn证证 由由(2), (2), dnan,dndn?1. .但但dn?1an?1,dn?1dn?2,故故dnan?1,dndn?2.由此类推由此类推, ,最后得到最后得到dnan,dnan?1,是是a1,a2,an的一个公因数的一个公因数. .又设又设d是是a1,a2,dna1,即即dn,an的

11、任一的任一公因数公因数,则则d a1,d a2,由推论由推论4.1,4.1,d d2,同样由推论同样由推论4.14.1d d3,由此类由此类推推,最后得最后得d dn. .因而因而d?d?dn.故故dn是是a1,a2,an的最大公因数的最大公因数. .3 整除的进一步性质及最小公倍数整除的进一步性质及最小公倍数 设设a,b是任意两个正整数是任意两个正整数 ,则可以得到下列诸等式：则可以得到下列诸等式：a?bq1?r1,0?r1?b,b?r1q2?r2,0?r2?r1,(1)rk?1?rkqk?1?rk?1,0?rk?1?rk,rn?1?rnqn?1定理定理1若若a,b是任意两个正整数是任意两个

12、正整数 ,则则Qk?1ka?Pkb?1?rk,k?1, ,n;其中其中P0?1, P1?q1,Pk?qkPk?1?Pk?2,Q0?0, Q1?1, Qk?qkQk?1?Qk?2,k?2, ,n(2)(3)证证 当当k?1 时时,(2) 显然成立显然成立,当当k?2 时时, 故故r2? ?aq2?b?1?q1q2?Q2a?P2b?1?kk2?1但但1?q1q2?q2P1?P0,q2?q2?1?0?q2Q1?Q0,r2,P2?q2P1?P0,Q2?q2Q1?Q0假定假定(2),(3)(2),(3) 对于不超过对于不超过 k?2的正整数都成立的正整数都成立 ,则则 ?1?rk?1?1? ?rk?1?

13、qk?1rk? ?Qk?1a?Pk?1b?qk?1?Qka?Pkb? ?qk?1Qk?Qk?1?a?qk?1Pk?Pk?1?b.故故 Qk?1a?Pk?1b?1?rk?1,其中其中 Pk?1?qk?1Pk?Pk?1,Qk?1?qk?1Qk?Qk?1.由归纳法，定理为真由归纳法，定理为真 .k推论推论1.1若若a,b是任意两个不全为零的整数是任意两个不全为零的整数 ,则存在则存在两个整数两个整数 s,t使得使得as?bt?a,b?(4)定理定理2 若若a,b,c是三个整数是三个整数,且且?a,c?1, 则则(i) i) ab,c与与b,c有相同的公因数，有相同的公因数，(ii ii)?ab,c?

14、b,c?上面假定了上面假定了a,b,c至少一个不为零至少一个不为零 .(5)证证 (i) i)由题设及推论由题设及推论1.11.1,存在任意两个整数存在任意两个整数 s,t满足满足等式等式as?ct?1两边乘以两边乘以b,即得即得 ?ab?s?c?bt?b. 设设d是是ab与与c的任一公因数的任一公因数. .由上式及由上式及1 定理定理3, d b,因而因而d是是b,c的一个公因数的一个公因数. 反之反之b,c的任一公因数显然是的任一公因数显然是 ab,c的一个公因数的一个公因数,故故(i)(i)获证获证. . (ii) (ii)因为因为b,c不全为零不全为零, ,故故?b,c?是存在的是存在

15、的, ,因而由因而由(i)(i)即知即知?ab,c?存在存在, ,且且?ab,c?b,c? 推论推论2.1 2.1 若若?a,c?1, c ab,则则c b. 证证 由定理由定理2 2及及2 2定理定理2,32,3得得 c?ab,c?b,c?,故故 c d, ,因而因而c b. 推论推论2.2设设a1,a2,a1a2an与与b1b2,an及及b1,b2,bm互质互质.an,bj?an,bj?1,j?1, 2,an,b2b3bm?a1a2an,bm?1.,m .,bm是任意两组整数是任意两组整数 . 若前一组中任一整数与后一组中任一整数互质若前一组中任一整数与后一组中任一整数互质 , ,则则 证

16、证 由定理由定理2, 2,?aa1 2an,bj?a2a3再用定理再用定理2 ，?a1a2an,b1b2bm?a1a2 ? 定义定义 设设a1,a2,an是是 n?n?2?个整数个整数. . 若若d是这是这n个数的个数的,an的的倍数倍数, ,则则d就叫作这就叫作这n个数的一个公倍数个数的一个公倍数. .又在又在a1,a2,一切公倍数中的最小正数叫作最小公倍数一切公倍数中的最小正数叫作最小公倍数 , ,记作记作 a1,a2,an. 由于任何正数都不是由于任何正数都不是0 0的倍数的倍数, ,故讨论整数的最小公倍数故讨论整数的最小公倍数时时, ,一概假定这些整数都不是零一概假定这些整数都不是零.

17、 定理定理3a1,a2,an?a1,a2,an. 定理定理4 4 设设a,b是任意两个正整数是任意两个正整数, ,则则(i) (i) a,b的所有的所有公倍数就是公倍数就是?a,b?的所有倍数的所有倍数;(ii);(ii)a,b的最小公倍数的最小公倍数等于以它们的最大公因数除它们的乘积所得的商等于以它们的最大公因数除它们的乘积所得的商 , ,ab即即?a,b?.特别特别的的, ,若若?a,b?1, 则则?a,b?a?b.?a,b? 证证 设设m是是a,b的任一公倍数的任一公倍数. .由定义可设由定义可设 m?ak?bk令令a?a1?a,b?,b?b1?a,b?, ,由由上式即得上式即得a1k?

18、b1k但由但由2 2定理定理5, 5, ?a1,b1?1 ,故由推论故由推论2.12.1,b1kab 因此因此 m?ak?ab1t?t,(6)?a,b?其中其中t满足等式满足等式k?b1t.反过来反过来, ,当当t为任一整数时，为任一整数时，abt 为的一个公倍数，故为的一个公倍数，故 (6)(6)可以表示可以表示a,b的一切的一切?a,b?ab公倍数公倍数. .令令t?1 即得到最小的正数，故即得到最小的正数，故?a,b?a,b?即即(ii ii)获证又由获证又由.(6),(i)(6),(i)亦获证亦获证. .现在来研究两个以上整数的最小公倍数现在来研究两个以上整数的最小公倍数 . .设设a

19、1,a2,an是任意是任意n 个正整数个正整数.令令?a1,a2?m2,?m2,a3?m3,?mn?1,an?mn(7)定理定理5 5 若若a1,a2,an是是n?n?2?个整数个整数, ,则则?a1,a2,an?mn,n,证证 由由(7), (7), mimi?1,i?2,3,故故mn是是a1,a2,n?1, 且且a1m2,aimi,i?2,3,an的一个公倍数的一个公倍数. .反之反之, ,设设m 是是a1,a2,an的的任一个公倍数任一个公倍数, ,则则a1m,a2m,故由定理故由定理4( i), i), m2m .又又a3m,同样由定理同样由定理4( i), i), m3m .依此类推依此类推, ,最后得到最后得到mnm . 因因此此, ,mn?m.故故mn?a1,a2