数论算法讲义 8章（数论函数）

数论算法讲义 8章（数论函数） 《数论算法》 第五章 数论函数 第 8 章 数论函数 (一) 内容 , 数论函数的某些一般理论 , 几种重要的数论函数 , 函数的狄利克雷乘积 , 积性函数 (二) 重点 , 数论函数 , 性质 , 函数的狄利克雷乘积和积性函数 8.1 数论函数 在数论中，经常出现各种数论函数，它们在数论的研究 中，起着重要作用。 【定义8.1.1】一个定义在正整数集上的实或复值函数，，fn 叫做一个数论函数或算术函数。 ,例如，,,等都是数论函数。 a,n!,nn ,,x8.2 函数、、 xx，，，，8. 2. 1 函数 x，， (一) 定义 【定义8.2.1】函数是对于一切实数都有定义的函数，x，， x其值等于不大于的最大整数。 (二) 性质 1. ; x,x,x，1，，，， 1/20 《数论算法》 第五章 数论函数 2. ; x，y,x，y，，，，，， n3.当是整数时，; n，x,n，x，，，， ,x,1，当x不是整数时，,，，4. , -x,，，,x，当x是整数时;，，, 5.若a,b是任意两个正整数，则不大于a而为b的倍数的正 a,,整数的个数是。 ,,b，， 8. 2. 2 函数 x，， (一) 定义 【定义8.2.2】函数是对于一切实数都有定义的函数，x，， 其值等于不小于x的最小整数。 (二) 性质 1. ; x,1,x,x，，，， 2. x,x,x，，，， 3. ; x，y,x，y，，，，，， n4.当是整数时，; n，x,n，x，，，， ,x，1，当x不是整数时，,，，5. , -x,，，,x，当x是整数时;，，, 6. 当x,整数时，,，当x?整数时< xxxx，，，，，，，， ,,x8. 2. 3 函数 2/20 《数论算法》 第五章 数论函数 (一) 定义 ,,x【定义8.2.3】函数是对于一切实数都有定义的函数， 其值为x四舍五入的结果，即 ,,x, x，0.5，， (二) 性质 ,,,,xx1. 当x,整数时，,,，当x?整数时??xxx，，，，，， x，， ,,,,nn，xx2.当是整数时，,n，; ,,,,-xx3. ,, 8.3 数论函数 potnp m【定义8.3.1】对于一给定的素数p，设(即p||nmm，1?n)，则记。 potn,mp|n,pp m对于有理数，定义 n m,,pot,potm,potn ,,pppn,, 对于给定的素数p，potn是一个数论函数。 p 由定义，显然有以下简单的性质: ，，potp1. ,1 p ，，potmn,potm，potn2. ppp kpotn,k,potnk,03. ，这里 pp potn4. p?n，则,0 p 3因此，有54,3，2,3，0,3，54,potpotpotpot3332 3/20 《数论算法》 第五章 数论函数 33，2,0，1,1，等等。 potpot22 本节主要求出的公式。 potn!p kk，1【定理8.3.1】设，则有 p,n,p ,,,,,,nnn (1) potn？,，，，(!)p,,,,,,2kppp，，，，，，(证)因为 pot(n!),pot1，pot2，？，potnpppp ,,,,n,,，， ,potp，potp，，potp2？ppp,,,,p，，,,和 ， pot(jp),potp，potj,1，potjpppp有 ,,,,,,nn,, (2) pot(n!),，pot!pp,,,,,,pp，，，，,, ,,,,n ,,,,pn，，,,由8.2.1节性质(5)可知,，故 2,,pp ,, ，， ,,,,,,,,,,nnn,,,,pot!,，pot! pp,,,,,,22,,,,ppp，，，，，，,,,, …… ,,,,,,,,,,,,nnnn,,,,pot!，pot!,, pp,,,,,,,,k,1kkk,,,,pppp，，，，，，，，,,,,代入(2)便得(1)。证完 4/20 《数论算法》 第五章 数论函数 ,,,n定理8.3.1的结果，也可写成,。它给pot(n!)p,,,tp，，t1,出了 ,，，n,,,tp,,，，,t1n!, p, p,n 0,r,n【定理8.3.2】设，则 n,,n!,, ,,,rr!(n,r)!,, 是一个整数。 ，，n,n,r，r(证)因为，故从函数的性质2推出 x，， ,,,,,,nnrr,， ,，,,,,,,tttppp，，，，，， ,,,,,,,,,nnrr,， ,，,,,,,,,,,tttppp，，，，，，t1t1t1,,, n,,利用上面给出的pot(n!)的公式，就证明了是整数。证,,p,,r,,完。 c,c,0【定理8.3.3】对于给定的素数p和，有 0,r,p c,,p,,pot,c,potr。 (3) pp,,r,, (证)时，(3)显然成立。设，有 r,1r,1 ccccc,,ppp,1p,2p,r,1，，,,,,,？， ,,r12r,1r,, c因为，故 0,r,p c，，potp,j,potjj,1,？,r,1，， pp 5/20 《数论算法》 第五章 数论函数 c,1rr,,pcc,,，，，， pot,potp，potp,j,potjpp,p,p,,r,1,1jj,, 。 ,c,potrp 这就证明了(3)。证完。 1hh,【定理8.3.4】， n,ap，ap，？，ap，a110hh, j,0,1,？,h,1这里，，，，0,a,p1,a,pjh h ，，，则有 An,p,a,k ,0k h,,，，n,An,pn (4) ,,pot(n!)p,,,kp,1p，，,1k (证)因为 hhkk，，，，，，， n,An,p,ap,1,ap,1,,kk ,0,1kk故 h，，n,An,p,1,2kk，， ,ap，p，？，p，1,kp,1,1k hh,1,2, a，ap，？，ap，a，ap，？，ap，？，ahhh1223h,hk，，, ap，？，ap，a，1,hkk ,1k h,,n, ,,,kp，，,1k h,,nhh，1因为，故由定理8.3.1知。 ,pot(n!)p,n,pp,,,kp,1，，k n,,,,现在，可以进一步求出pot。 p,,r,, 6/20 《数论算法》 第五章 数论函数 【定理8.3.5】设，则 0,r,n n,,Ar,p，An,r,p,An,p，，，，，，,,。 pot,p,,rp,1,, (证)因为 n,,,,， ，，pot,pot(n!),pot(r!),pot(n,r)!pppp,,r,, 由(4)，故 n,,,,n,An,pr,Ar,p，n,r,An,r,p，，，，，，,,,, pot,,p,,,,rp,1p,1,,,, ，，，，，，Ar,p，An,r,p,An,p, p,1 8.4 墨比乌斯函数 ，，,n【定义8.4.1】麦比乌斯(Mobius)函数，当n,1时，，,n lls1n,1;当时，设为n的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 分解式，，，n,p？p,1,11s 则定义为 ，，,n s,，，,1,l,,l,1时，？,1s，，,n, ,，，，有某个ljs时0,11,,.,j, n,1【定理8.4.1】如果，则有 1,,，， (1) d,,,,,n，，d|n n,1证 n,1时，(1)显然成立。现设，n的标准分解 lls1式为，则 n,p？p1s 7/20 《数论算法》 第五章 数论函数 ，，，，，，，，，，,d,,1，,p，？，,p，,pp1s12, d|n ，，，，，？，,pp，？，,p？ps,1s1s sss,,,,,,2s 1,,1,,1,,1，，，，，，,，,，,，？，,,,,,,,12s,,,,,, s，， ,1,1,0 函数在数论中经常出现。例如 ，，,n ,,,,11,,,,，，nn11 (2) ,,,,？,,,,pp1s,,,, lls1其中是n的标准分解式，利用，可将(2)，，n,p？p,n1s 改写为 n ，，，，nd,,,,dd|n n,1【定理8.4.2】设，当d遍历n的不含有多于m个素因数的因数时，则 ,0,当m为偶数时，, ,，，d (3) ,,,,0,当m为奇数时。, lls1证 设是n的标准分解式，则在m,n时，n,p？p1s 由定理8.4.1，(3)式成立。现设m 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示n的因数，，，，,n,1,dn0, d|n ，，,n的个数。即通常的n的全部因子的和。于是，设，，,n1 ,,k1是n的标准分解式，就有 n,p？p1k ,,k1，，，，，，， ,n,,p？,p1k,,, ,,,2,,jj，，,p,1，p，p，？，p而 jjjj, ,,，，，1j,,1pj,,,,0,,, p1,,j ,,，1,,,0,j, 故 ,,，1，，jk,,1pj,,,,0,,,p,1,,1jj,，，, n,,k,，，,1,,0.，,j,,,1j, 【定理8.6.3】如果，，和，，，，，，都是积性函gnhn,fn,gn数，则，，也是积性函数。 fn m,n证 如果，，不是积性函数，则存在一对正整数，fn ，，m,n,1，使得 ，，，，，，， fmn,fmfn于是我们可以选择这样一对m,n，使得mn最小。 mn,1，，，，，，，，如果，则，故。因为f1,f1f1f1,1 16/20 《数论算法》 第五章 数论函数 ，，hn，这将得出不是积性函数，，，，，，，，，h1,f1g1,f1,1 与所设矛盾。 如果mn,1，则对所有正整数对 ，，a,b,a,b,1,ab,mn，有。于是有 ，，，，，，fab,fafb mn,, ，，，，hmnfabg,,,,,ab,,an||mb mn,, ，，，，，，,fabg，fmng1,,,ab,,ambn|,|ab,mn mn,,,,，，，， ，，,fafbgg，fmn,,,,,ab,,,,a|m,b|nab,mn mn,,,,，，，，，，，，，，,fag,fbg,fmfn，fmn,,,,,,ab,,,,a|mb|n 。 ，，，，，，，，，，,hmhn,fmfn，fmn ，，，，，，hmn,hmhn因为，故，此与，，，，，，fmn,fmfn ，，hn是积性函数矛盾。 【定理8.6.4】如是一个积性函数，则的狄利克，，，，gngn雷逆函数也是一个积性函数。 ,1，，，，，，证 因为和都是积性函数，故由，，gn,gn,Ingn ,1，，定理8.6.3得知，也是积性函数。 gn 定理8.6.2和定理8.6.4指出全体积性函数组成阿贝尔群D的一个子群。 完全积性函数的狄利克雷逆函数是容易决定的。 ，，，，【定理8.6.5】设是一个积性函数，则是一个完fnfn 17/20 《数论算法》 第五章 数论函数 全积性函数的充分必要条件是 ,1。 ，，，，，，fn,,nfn 证 设，如果是一个完全积性函数，，，，，，，，，gn,,nfnfn 则有 n,, ，，，，，，，，，，，，gn,fn,,dfdf,fn,d,,,,d,,d|nd|n ， ，，，，，，,fnIn,In ,1故。 ，，，，fn,gn ,1反之，假设，为了证明是完全积性，，，，，，，，fn,,nfnfn ,,,，，，，函数，只需证明对于素数的方幂，有。对fp,fpp n,1于，有 n,,1, ，，，，，，，，，，Infnfndfdf0,,,,,,,,d,,|dn ,,,0因此，取，，我们有 n,p ,,,1，，，，，，，，，，，， ,1f1fp，,pfpfp,0即 ,,,1，，，，，，。 fp,fpfp ,,，，，，由此可推出，故是完全积性函数。 ，，fp,fpfn 8.7 Euler函数 18/20 《数论算法》 第五章 数论函数 (一) 定义 (二) 性质 8.8 素数个数函数 第1章已经讲过。 (一) 定义 【定义8.8.1】记1,n的所有素数的个数为(n)，称为素,数个数函数。 例如:(2)=1，(3)=(4)=2，(5)=(6)=3，,,,,,(7)=(8)= =(9)=(10)=4，(11)=(12)=5。 ,,,,,,(二) 性质 【性质8.8.1】当m?n时，有(m)?(n)。且 ,, (n)?? , 【性质8.8.2】设n?2，则有 1nn?(x)?12 , 8log nlog n【性质8.8.3】(契比雪夫不等式) 设x?2，则有。 ln2xx，，,x,6ln2, 3lnxlnx 18nlnn,p,nlnn和 ，n?2 n6ln2ln2 其中是第n个素数。 pn 19/20 《数论算法》 第五章 数论函数 ，，,x【性质8.8.4】(素数定理) lim,1。 x,,x lnx x，，,x意义:当n,,1时，?。 lnx 99100【例】求到之间的素数个数。 1010 10099101010099，，，，(解),?, ,10,1010099，，，，ln10ln10 979897?, 10,109,10 故多人选素数时重复的可能性很小。 20/20