(3)_第一章_質(zhì)數(shù)、算術(shù)基本定理;函數(shù)[x],{x}

1、質(zhì)數(shù).算數(shù)基本定理函數(shù)x,x及其應(yīng)用 2015.03.25復(fù)習(xí)復(fù)習(xí) 最大公因數(shù)與輾轉(zhuǎn)相除法最大公因數(shù)與輾轉(zhuǎn)相除法12121212121212.,(2).,( ,),( ,)1,.,nnnnnnna aan ndda aaa aaa aaa aaa aaa aa 定定義義設(shè)設(shè)是是個個整整數(shù)數(shù) 若若整整數(shù)數(shù)是是它它們們之之中中每每一一個個的的因因數(shù)數(shù) 那那么么就就叫叫作作的的一一個個整整數(shù)數(shù)的的公公因因數(shù)數(shù)中中最最大大的的一一公公因因數(shù)數(shù)個個叫叫作作記記作作若若我我們們說說若若中中每每兩兩個個整整數(shù)數(shù)最最大大公公互互質(zhì)質(zhì)，因因數(shù)數(shù)互互質(zhì)質(zhì)或或我我們們就就說說它它 互互素素兩兩們們 兩兩互互質(zhì)質(zhì) 2

2、1212121212,)(,)nnnnna aana aaaaaa aaaaa 定理1 若,是任意個不全為零的整數(shù),則 (i) 與的公因數(shù)相同； (ii) (3(0, ).bbbbbbb 定理2 若 是任一正整數(shù),則(i) 0與的公因數(shù)就是的因數(shù),反之, 的因數(shù)也是0與 的公因數(shù). (ii) 3, ,0,( , )( , ).a b cabqcqa bb ca bb c 定理設(shè)是任意三個不全為 的整數(shù)且其中是非零整數(shù),則與有相同的公因數(shù) 因而411112221-2-1-1-1-1+1+1, ,0 , ,0 , (1) ,00,=1, ,(3). (3)0,=1, .1260=2=klkiijl

3、iaappikppijaaappil 推推論論3.1 3.1 任任一一大大于于 的的整整數(shù)數(shù)能能夠夠惟惟一一地地寫寫成成 ., ., 其其中中（）叫叫做做的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)分分解解式式. .在在應(yīng)應(yīng)用用中中, ,為為方方便便計計，有有時時我我們們插插進(jìn)進(jìn)若若干干質(zhì)質(zhì)數(shù)數(shù)的的零零次次冪冪而而把把表表成成下下面面的的形形式式., ., 例例 2579 2 2579 2 5 79 251111.1 0,=1, ,0,=1,3.1,.,kkkikijiaad aappidqkaddppikaddap推推論論32 32 設(shè)設(shè) 是是一一個個大大于于 的的整整數(shù)數(shù)，且且 ., ., 則則 的的正正因因數(shù)數(shù)可可以以

4、表表成成 ., ., 的的形形式式 而而且且當(dāng)當(dāng)可可以以表表成成上上證證 若若則則由由推推論論知知的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)分分解解式式是是惟惟一一的的 故故的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)述述形形式式時時是是的的正正因因數(shù)數(shù) 分分解解式式中中出出現(xiàn)現(xiàn)的的質(zhì)質(zhì)數(shù)數(shù) 都都在在 (1,2, ),.jjjjjjjjkpdda中中出出現(xiàn)現(xiàn), ,且且在在的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)分分解解式式中中出出現(xiàn)現(xiàn)的的指指數(shù)數(shù)亦亦即即反反過過來來當(dāng)當(dāng)時時，顯顯然然整整除除261212121212121212,0,1,2, ,0,1,2, , ( , ), , ,min(,),max(,),1,2, ,min(,),max(,kkkkkikikkiiiiiiiii

5、iia bap ppikbp ppika bp ppa bp ppik 推推論論3.33.3設(shè)設(shè)是是任任意意兩兩個個正正整整數(shù)數(shù)，且且 則則其其中中表表示示中中較較小小的的數(shù)數(shù)，),iii 表表示示中中較較大大的的數(shù)數(shù). .271/21/21/2111100()100100(10(),()ssNapNNpNppNpp解解 不不超超過過或或任任給給的的正正整整數(shù)數(shù)的的正正合合數(shù)數(shù) 必必有有一一個個不不可可約約數(shù)數(shù)或或因因而而, ,只只要要先先求求出出不不超超過過1010 或或的的全全部部不不可可約約數(shù)數(shù)2,3,5,7(2,3,5,7(或或,),),然然后后依依次次把把不不超超過過100(100(

6、或或的的正正整整數(shù)數(shù)中中的的除除了了2,3,5,7(2,3,5,7(或或,),)以以外外的的2 2的的倍倍數(shù)數(shù)、3 3 的的 例例 求求出出不不超超過過或或任任給給的的正正整整數(shù)數(shù)的的所所有有不不可可約約數(shù)數(shù). . 倍倍數(shù)數(shù)、5 5的的倍倍數(shù)數(shù)、7 7的的倍倍數(shù)數(shù)( (或或 的的倍倍數(shù)數(shù), , , ,)100()spNN的的倍倍數(shù)數(shù)), ),全全部部刪刪除除, ,就就刪刪去去了了不不超超過過100(100(或或的的全全部部合合數(shù)數(shù), ,剩剩下下的的正正好好是是不不超超過過或或任任給給的的正正整整數(shù)數(shù)的的所所有有不不可可約約數(shù)數(shù).(Eratosthenes.(Eratosthenes篩篩法法、埃

7、埃拉拉托托塞塞尼尼) )281 2 3 4 5 6 7 8 9 10 11 1213 14 15 16 17 18 19 20 21 22 23 2425 26 27 28 29 30 31 32 33 34 35 3637 38 39 40 41 42 43 44 45 46 47 4849 50 51 52 53 54 55 56 57 58 59 6061 62 63 64 65 66 67 68 69 70 71 7273 74 75 76 77 78 79 80 81 82 83 8485 86 87 88 89 90 91 92 93 94 95 9697 98 99 100291

8、1212,.1, 1.1.,1,2, ,1,.4,.kkikppp ppNNNppp ikp p ppp Npppk 證證用用反反證證法法. .假假設(shè)設(shè)只只有有有有限限個個質(zhì)質(zhì)數(shù)數(shù) 設(shè)設(shè)為為,.,.,.,.令令則則由由定定理理 ，有有一一質(zhì)質(zhì)因因數(shù)數(shù)這這里里否否則則, ,因因此此而而與與是是 定定理理質(zhì)質(zhì)數(shù)數(shù)矛矛盾盾故故是是上上面面?zhèn)€個質(zhì)質(zhì)數(shù)數(shù)以以外外質(zhì)質(zhì)數(shù)數(shù)的的個個數(shù)數(shù)是是無無窮窮的的. . 的的質(zhì)質(zhì)數(shù)數(shù) 定定理理獲獲證證 30 5 5 函數(shù)函數(shù)x,xx,x及其應(yīng)用及其應(yīng)用1 , ; . xxxxxxxxxxx 定定義義 函函數(shù)數(shù) 與與 是是對對于于一一切切實(shí)實(shí)數(shù)數(shù)都都有有定定義義的的函函數(shù)

9、數(shù) 函函數(shù)數(shù) 的的值值等等于于不不大大于于的的最最大大整整數(shù)數(shù) 函函數(shù)數(shù) 的的值值是是我我們們把把 稱稱為為 的的整整數(shù)數(shù)部部分分,稱稱為為 的的小小數(shù)數(shù)部部分分. . 31 23 =3,e=2,- =-4,=0,- =-1;3532 -=,=0.14159,2 =0.414,55-=1-0.14159=0.85840.例例 32 ,0 2.0 .(ii) 1, -1 ,0 1.(iii) ,. (iv 1) ,+; .xxxxxxxxxxnxxn nxyxyxyxxyxyxyxyxyxyxyxyxxyy 性性質(zhì)質(zhì)(i) (i) 證證 及及當(dāng)當(dāng)時時, , 知知 當(dāng)當(dāng)121 ,=0,+.rrrs

10、snp pnnnnhpppnnhnpprnrh nnnnnpnp 定定理理 求求的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)素素因因數(shù)數(shù)分分解解式式中中質(zhì)質(zhì)因因數(shù)數(shù)的的指指數(shù)數(shù)注注意意 若若則則故故上上式式只只有有有有限限項項不不為為證證 設(shè)設(shè)想想把把都都分分解解成成標(biāo)標(biāo)準(zhǔn)準(zhǔn)分分解解式式 則則由由算算術(shù)術(shù)基基本本定定理理，就就是是這這個個分分解解式式中中 的的指指數(shù)數(shù)之之和和 設(shè)設(shè)其其中中 的的指指數(shù)數(shù)是是 的的有有個個則則零零 因因而而有有意意義義 2323312312=1+=2,-1(vii),=+=.rrrrrrrrnnnnNNNNnnnnpnnnnNhpppp 其其中中恰恰好好是是這這個個數(shù)數(shù)中中能能被被除除盡盡的的

11、個個數(shù)數(shù)但但由由故故3611-+=1=1=1-(iv)( - ),+,-1!,.!20 .!( - )!+.rrrrrrrn kkprnprrrrp nnrpnn kknn knpnkpppnn kkppnk nkpn kp 推推論論 其其中中表表示示展展布布在在不不超超過過 的的一一切切質(zhì)質(zhì)數(shù)數(shù)上上的的積積式式 推推論論 賈賈憲憲數(shù)數(shù)是是整整數(shù)數(shù)（） 由由故故 證證 及及=11.1!()! !,.rrrrnppp np npknkn由由推推論論 即即得得故故推推論論證證得得37( )( )-1-110( )+()( )( )( )-!( )+,( )!()(-1)(1)()!=.!)(),-

12、.!2knnnnkiikikkkikifxn kkf xa xaxa x afxxkkikf xnfxfxkiikiknn kkbaakkfb 推推論論3 3 若若是是一一 次次整整系系數(shù)數(shù)多多項項式式，是是它它的的階階導(dǎo)導(dǎo)數(shù)數(shù)證證 顯顯然然是是次次整整系系數(shù)數(shù)多多項項式式，設(shè)設(shè)則則中中的的系系數(shù)數(shù)由由推推論論 及及假假則則是是一一次次整整系系設(shè)設(shè)知知 為為整整數(shù)數(shù)，即即數(shù)數(shù)多多項項式式 ( ).!xk是是整整系系數(shù)數(shù)38235711132020202010521 18248162020628;392020204;2;1;571120hhhhhh 解解 不不超超過過2020的的素素數(shù)數(shù)有有2,

13、3,5,7,11,13,17,19.2,3,5,7,11,13,17,19. 例例1 1 求求2020 ! !的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)素素因因數(shù)數(shù)分分解解式式 + + + + 17191884220201;1;1;1317192035711 13 17 19hh所所以以 ！=2 =2 395120!,10 80!,58080801 9.23555kkjjkkh解解 這這就就是是要要求求求求正正整整數(shù)數(shù) , ,使使1010由由上上例例知知k=4,k=4,即即是是5 5的的方方次次數(shù)數(shù). .所所以以結(jié)結(jié)尾尾有有四四個個零零. .解解 這這就就是是要要求求整整數(shù)數(shù) 使使, ,記記號號因因?yàn)闉?0!80!的的素素分分解解中中, , 素素數(shù)數(shù)越越小小, ,則則指指數(shù)數(shù)越越大大, , 故故即即求求8080 例例2 2 求求20!20!的的十十進(jìn)進(jìn)位位表表示示中中有有多多少少個個零零 例例求求80!80!的的十十進(jìn)進(jìn)制制表表示示中中零零的的個個數(shù)數(shù)! !中中 的的冪冪次次. . 所所以以8080 ! !的的十十進(jìn)進(jìn)位位表表示示中中有有1919個個零零. . 40 第一章整除理論知識要點(diǎn)第一章整除理論知識要點(diǎn) 定義：整除、素數(shù)、最大公約數(shù)、最小公倍數(shù)、定義：整除、素數(shù)、最大公約數(shù)、最小公倍數(shù)、 x x、xx 性質(zhì)：整除、最大公約數(shù)、性質(zhì)：整除、