(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 证证用用反反证证法法. .假假设设只只有有有有限限个个质质数数 设设为为,.,.,.,.令令则则由由定定理理 ，有有一一质质因因数数这这里里否否则则, ,因因此此而而与与是是 定定理理质质数数矛矛盾盾故故是是上上面面个个质质数数以以外外质质数数的的个个数数是是无无穷穷的的. . 的的质质数数 定定理理获获证证 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 性质：整除、最大公约数、性质：整除、