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

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

2、, , ,() ,. abbc ac b a c bc a b a c ba b aab bbc aab cabc a 定定理理传传递递性性 若若是是 的的倍倍数数是是 的的 倍倍数数 则则是是 的的倍倍数数 也也就就是是 证证 就就是是说说存存在在两两个个整整数数使使得得 成成立立 因因此此 但但是是一一个个整整数数 故故 11 11 11 11 2,. , , ,. () , ,. a bmabm a bm a b aa m bbm abab m ababm 定定理理若若都都是是的的倍倍数数 则则也也是是的的倍倍数数 证证 是是的的倍倍数数的的意意义义就就是是存存在在两两个个整整数数 使使

3、得得 因因此此 但但是是整整数数 故故是是的的倍倍数数 12 121 122 3, , . n n nn a aam q qqnq aq a q am 定理 若都是的倍数 是任意 个整数 则 是 的倍数 ,0 , ,0.(2) . a bb qr abqrrb qr () , , 定定理理 4 4 带带余余数数除除法法 若若是是两两个个整整数数, ,其其中中 则则存存在在着着两两个个 整整数数 及及使使得得 成成立立 而而且且 及及 是是惟惟一一的的 带余数除法的内涵带余数除法的内涵 n它可以看作是整除的推广，也可以用带余除法 定理来定义整除性 n将一个未知的整数表示为小于除数的余数，将 整数

4、进行分类，从而可将无限问题转化为有限 问题 n其他应用：辗转相除法、进制间转换算法 2 最大公因数与辗转相除法最大公因数与辗转相除法 12 12 12 1212 1212 . ,(2). , , ,( ,),( ,)1, , . , n n n nn nn a aan nd da aa a aa a aaa aa a aaa aa 定定义义设设是是个个整整数数 若若整整数数 是是它它们们之之中中每每一一个个的的因因数数 那那么么就就叫叫作作 的的一一个个 整整数数的的公公因因数数中中最最大大的的一一 公公因因数数 个个叫叫作作 记记作作若若我我们们说说 若若中中每每两两个个整整数数 最最大大

5、公公 互互质质， 因因数数 互互质质或或 我我们们就就说说它它 互互素素 两两们们 两两互互质质 12 12 1212 , ,)1, ,) 21 n n nn a aa a aa a aaa aa n 显然,若整数,两两互质,则 (反过来却不一定成立, 且若,不全为零,则( 是存在的. 例1: 2和互素; 例2: 6,10,-15是互素的,但它们任意 两个数不互素,因为(6,10)=2,(10,15)=5, (-15,6 )=3. 12 1212 1212 , , ,)(,) n nn nn a aan a aaaaa a aaaaa 定理1 若,是任意个不全为零的 整数,则 (i) 与的公因

6、数相同； (ii) ( 12 1212 12 1212 ,. ,1,2, ,1,2, , , ,. , n ii n nn nn da aa d a ind a ind aaaaa aa aa a aaaaa 证 设是,的任一公因数由定义 因而故是 ,的一个公 因数,同法可证, 的任一公因数都是的一个公因数 故与,有相同的公因数,即 (i)获证.由(i)立得(ii). (0 (0, ). , ) (0, ) . bb bb bb bb bbb b b bb bb bb 证 显然0与 的公因数是 的因数.由于任何非零整数 都是0的因数,故的因数也就是0，的公因数,于是(i) 获证.其次,我们立刻

7、知道 的最大公因数是;而0，的 最大公因数是的最大公 定理2 若 是任一正整数,则(i) 0与的公因数就是 的因数,反之, 的因数也是0与 的 因数,故 推论2.1 若 是任一非零整数,则 公因数. (ii) b . ,. 1 3,() , 3, ,0, , ,( , )( , ). da a b c abqcqa bb bd a d b dcaq c b b ab c d b c 定理设是任意三个不全为 的整数 且其中是非零整 证 设是的任一公因数 由定义 由定理是的因数,因而是 的一个公因数. 于是定理的前一部分获证 数,则与有 相 . 第二部分显 同的公因数 因而 然随之成立. 111

8、12221 -2-1-1 -1-1+1+1 , ,0 , ,0 , (1) ,00,0,则则继继续续对对(2 -1, 2 -1)(2 -1, 2 -1)作作同同样样的的讨讨论论, ,由由辗辗转转 相相除除法法知知，结结论论成成立立. . 显显见见, 2, 2用用任任一一大大于于1 1的的自自然然数数 代代替替, ,结结论论都都成成立立. . , , , ( ), ,1 , a b mam bma b m a ba b a b ab a ba b ii 定定理理5 5 设设是是任任意意两两个个不不全全为为零零的的整整数数 (i) (i) 若若是是任任意意一一正正整整数数，则则 若若 是是的的任任

9、一一公公因因数数，则则， 特特别别 111 12221 11 , (1),. , , ,0, ,0 4, nnn n a ba b am bma m b ma b ma b m a b m ambm qrmrmbm bmrm qr mr mrm rmr m q am bmr ma b m 证证 当当有有一一为为零零时时，定定理理显显然然成成立立，今今设设都都 不不为为零零. . 由由定定理理1, 1, 因因此此不不妨妨假假定定都都是是正正数数. . 公公式式(1)(1)里里各各式式两两边边同同 乘乘以以即即得得 由由定定理理 得得因因而而(i)(i)获获证证. . ( ) , , , ,1 ,

10、 = = aba b aba b a ba b ab a b a ba b i ii i 由由( (i i) )及及定定理理1 1, , 故故 当当时时，上上式式即即为为 12 1222331 12,. ,(2) n nnn a aan a add addad 现现在在来来研研究究两两个个以以上上整整数数的的最最大大公公因因数数. . 由由定定理理 及及 ，不不妨妨假假设设是是任任意意 个个正正整整数数 令令 111121 211 1212 12 1212 2 3 , ., , 6, , , nnnnnnnnnn n nn nnnnnnn n nn d ad ddaddd a d dd ad

11、ad ad a aada aa d a d a a aana a d ad d d dd 证证 由由(2), .(2), .但但故故 由由此此类类推推, ,最最后后得得到到即即 是是的的一一个个公公因因数数. .又又设设 是是的的任任一一 公公因因数数 则则由由推推论论4.1,4.1,同同样样由由推推论论4.14.1 由由此此类类 定定理理若若是是 个个整整数数 推推 , , 最最后后得得 则则 12 . , nn nn dddd da aa . .因因而而 故故是是的的最最大大公公因因数数. . 3 整除的进一步性质及最小公倍数整除的进一步性质及最小公倍数 111 12221 1111 11

12、 , ,0, ,0, (1) ,0, kkkkkk nnn a b abqrrb brqrrr rr qrrr rr q 设设是是任任意意两两个个正正整整数数 则则可可以以得得到到下下列列诸诸等等式式： 1 01112 0112 1, 1,1, ;(2) 1, 0,1,(3) 2, k kkk kkkk kkkk a b Q aPbr kn PPq Pq PP QQQq QQ kn 定定理理若若是是任任意意两两个个正正整整数数 则则 其其中中 2212 1221022210 2 1 22222102210 111 111 1,(2),2, 1 1,10, 1, 2, 11 kk kkkk kk

13、kkk kk raqbq q q qq PP qqq QQ Q aPbr Pq PP Qq QQ k rrqr QaP bqQ aPb 证证 当当时时显显然然成成立立当当时时 但但 故故 假假定定( (2 2) ), ,( (3 3) )对对于于不不超超过过的的正正整整数数都都成成立立 则则 1111 111 111111 . 1, ,. . kkkkkk k kkk kkkkkkkk qQQaqPPb QaP br PqPPQqQQ 故故 其其中中 由由归归纳纳法法，定定理理为为真真 1.1, ,(4) 2, ,1, (, ( ),(5) , ,. a b s tasbta b a b ca

14、 c ab cb c ab cb c a b c 推推论论若若是是任任意意两两个个不不全全为为零零的的整整数数 则则存存在在 两两个个整整数数使使得得 定定理理若若是是三三个个整整数数 且且则则 i i) ) 与与有有相相同同的的公公因因数数， i ii i 上上面面假假定定了了至至少少一一个个不不为为零零 (, 1 ,. 13, ,. , , , s t asct bab sc btb dabcd b db c b cab c b cb c ab cab cb c 证证i) i)由由题题设设及及推推论论1.11.1 存存在在任任意意两两个个整整数数满满足足 等等式式 两两边边乘乘以以 即即得

15、得 设设 是是与与 的的任任一一公公因因数数. .由由上上式式及及 定定理理 因因而而 是是的的一一个个公公因因数数 反反之之的的任任一一公公因因数数显显然然是是的的一一个个公公因因数数 故故(i)(i)获获证证. . (ii) (ii)因因为为不不全全为为零零, ,故故是是存存在在的的, ,因因而而由由(i)(i) 即即知知存存在在, ,且且 1 1212 22 121 2 3 , . ,1, ,1,. 2.2, 1,2,. ,. . 2 njnjnj nm nm cab cb c c dc b a aa ba aa ba bj a cc abc b a aab bb a aabbb m 推

16、推论论2.1 2.1 若若则则 推推论论设设及及是是任任意意两两组组整整数数 若若前前一一组组中中任任一一整整数数与与后后一一组组中中任任一一整整数数互互质质, , 证证 由由定定理理2 2及及 2 2定定理理2,32,3 则则 与与互互质质 得得 故故, ,因因而而 证证 由由定定理理2, 2, 再再用用定定理理 ， 121 2122 3 12 , ,1. nmnm nm a aa bbba aa b bb a aa b 12 12 12 1212 ,2 , ,. 3 ,. . n n n nn a aan ndn dna aa a aa a aaaaa 定定义义 设设是是 个个整整数数.

17、. 若若 是是这这 个个数数的的 倍倍数数, ,则则 就就叫叫作作这这 个个数数的的一一个个公公倍倍数数. .又又在在的的 一一切切公公倍倍数数中中的的最最小小正正数数叫叫作作最最小小公公倍倍数数, ,记记作作 由由于于任任何何正正数数都都不不是是0 0的的倍倍数数, ,故故讨讨论论整整数数的的最最小小公公倍倍数数 时时, ,一一概概假假定定这这些些整整数数都都不不是是零零 定定理理 11 11 11 , , ,.,1, , , . , ,1 , , ma b makbk aa a bbb a b a kb a ba b a ba b ab a ba ba k a b ba b a b 证证

18、设设是是的的任任一一公公倍倍数数. .由由定定义义可可设设 定定理理4 4 设设是是任任意意两两个个正正整整数数, ,则则(i) (i) 的的所所有有 公公倍倍数数就就是是的的所所有有倍倍数数;(ii);(ii) 令令, ,由由 的的最最小小公公倍倍数数 等等于于以以它它们们的的最最大大公公因因数数除除它它们们的的乘乘积积所所得得的的商商, , 即即特特别别 上上式式即即得得 但但由由 2 2定定理理5, 5, 的的, ,若若则则 1 ,b k故故由由推推论论2.12.1 1 1 ,(6) , . , , 1, , ( ). ab makabtt a b tkbtt ab ta b a b a

19、b ta b a b 因因此此 其其中中 满满足足等等式式反反过过来来, ,当当 为为任任一一整整数数时时， 为为的的一一个个公公倍倍数数，故故(6)(6)可可以以表表示示的的一一切切 公公倍倍数数. .令令即即得得到到最最小小的的正正数数，故故 即即 ii ii 获获证证又又由由(6),(i)(6),(i)亦亦获获证证. . 12 1222331 ,. ,(7) n nnn a aan a amm ammam 现现在在来来研研究究两两个个以以上上整整数数的的最最小小公公倍倍数数. . 设设是是任任意意 个个正正整整数数 令令 11 121 2 1212 1223 2 3 ,2,3,1,2,3, , , ,4(., 4(. ,2, . . iiii nnn n n n n nn m mina ma m in ma aama aa a m a mm ma m m a aan na aa m m mm mmm 证证 由由(7), (7), 且且 故故是是的的一一个个公公倍倍数数. .反反之之, ,设设 是是的的 任任一一个个公公倍倍数数, ,则则故故由由定定理理i), i), 又又 同同样样由由定定理理i), i), 依依此此类类推推, ,最最后后得得到到因因 定定理理5 5 若若是是个个整整数数, ,则则 此此, , 故故 1