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

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

2、1212121212,)(,)nnnnna aana aaaaaa aaaaa 定理1 若,是任意個不全為零的整數,則 (i) 與的公因數相同； (ii) (3(0, ).bbbbbbb 定理2 若 是任一正整數,則(i) 0與的公因數就是的因數,反之, 的因數也是0與 的公因數. (ii) 3, ,0,( , )( , ).a b cabqcqa bb ca bb c 定理設是任意三個不全為 的整數且其中是非零整數,則與有相同的公因數 因而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 任任一一大大于于 的的整整數數能能夠夠惟惟一一地地寫寫成成 ., ., 其其中中（）叫叫做做的的標標準準分分解解式式. .在在應應用用中中, ,為為方方便便計計，有有時時我我們們插插進進若若干干質質數數的的零零次次冪冪而而把把表表成成下下面面的的形形式式., ., 例例 2579 2 2579 2 5 79 251111.1 0,=1, ,0,=1,3.1,.,kkkikijiaad aappidqkaddppikaddap推推論論32 32 設設 是是一一個個大大于于 的的整整數數，且且 ., ., 則則 的的正正因因數數可可以以

4、表表成成 ., ., 的的形形式式 而而且且當當可可以以表表成成上上證證 若若則則由由推推論論知知的的標標準準分分解解式式是是惟惟一一的的 故故的的標標準準述述形形式式時時是是的的正正因因數數 分分解解式式中中出出現現的的質質數數 都都在在 (1,2, ),.jjjjjjjjkpdda中中出出現現, ,且且在在的的標標準準分分解解式式中中出出現現的的指指數數亦亦即即反反過過來來當當時時，顯顯然然整整除除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設設是是任任意意兩兩個個正正整整數數，且且 則則其其中中表表示示中中較較小小的的數數，),iii 表表示示中中較較大大的的數數. .271/21/21/2111100()100100(10(),()ssNapNNpNppNpp解解 不不超超過過或或任任給給的的正正整整數數的的正正合合數數 必必有有一一個個不不可可約約數數或或因因而而, ,只只要要先先求求出出不不超超過過1010 或或的的全全部部不不可可約約數數2,3,5,7(2,3,5,7(或或,),),然然后后依依次次把把不不超超過過100(100(

6、或或的的正正整整數數中中的的除除了了2,3,5,7(2,3,5,7(或或,),)以以外外的的2 2的的倍倍數數、3 3 的的 例例 求求出出不不超超過過或或任任給給的的正正整整數數的的所所有有不不可可約約數數. . 倍倍數數、5 5的的倍倍數數、7 7的的倍倍數數( (或或 的的倍倍數數, , , ,)100()spNN的的倍倍數數), ),全全部部刪刪除除, ,就就刪刪去去了了不不超超過過100(100(或或的的全全部部合合數數, ,剩剩下下的的正正好好是是不不超超過過或或任任給給的的正正整整數數的的所所有有不不可可約約數數.(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 證證用用反反證證法法. .假假設設只只有有有有限限個個質質數數 設設為為,.,.,.,.令令則則由由定定理理 ，有有一一質質因因數數這這里里否否則則, ,因因此此而而與與是是 定定理理質質數數矛矛盾盾故故是是上上面面?zhèn)€個質質數數以以外外質質數數的的個個數數是是無無窮窮的的. . 的的質質數數 定定理理獲獲證證 30 5 5 函數函數x,xx,x及其應用及其應用1 , ; . xxxxxxxxxxx 定定義義 函函數數 與與 是是對對于于一一切切實實數數都都有有定定義義的的函函數

9、數 函函數數 的的值值等等于于不不大大于于的的最最大大整整數數 函函數數 的的值值是是我我們們把把 稱稱為為 的的整整數數部部分分,稱稱為為 的的小小數數部部分分. . 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 性性質質(i) (i) 證證 及及當當時時, , 知知 當當121 ,=0,+.rrrs

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

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

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

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