信息安全数学基础第02章

1、第第2章章 数论函数数论函数第第2章章 数论函数数论函数数论函数数论函数就是以正整数为定义域的函数，本章讨论具有特殊性质的数论函数：积性函数积性函数高斯函数高斯函数x欧拉函数欧拉函数(x)默比乌斯函数默比乌斯函数完全数完全数2.1 积性函数积性函数积性函数的定义积性函数的定义除数函数除数函数2.1 积性函数积性函数积性函数的定义积性函数的定义定义定义2.1.1：设正整数m与与n互素互素，若f(mn)=f(m)f(n)则称数论函数f为积性函数积性函数。更一般的，若对所有的正整数m, n都有f(mn)=f(m)f(n)则称数论函数f为完全积性函数完全积性函数。2.1 积性函数积性函数积性函数的定义

2、积性函数的定义例例2.1.1：若函数f在任意正整数n处的函数值都为1，即nZ+，f(n)=1则函数f是完全积性函数；而若函数f在任意正整数n处的函数值都为正整数n自身，即nZ+，f(n)=n则函数f也是完全积性函数。证明证明：由于对所有的正整数m与n都有f(mn)=1，f(n)=1，f(m)=1，进而f(mn)=f(m)f(n)，因而函数f是完全积性函数。类似地可以证明函数f(n)=n也是完全积性函数。2.1 积性函数积性函数积性函数的定义积性函数的定义定理定理2.1.1：设正整数n有素分解式 则积性函数f的函数值证明：证明：对正整数n的素分解式中不同素因子的个数进行数学归纳。若n的素分解式中

3、只有素因子p1，即则结论显然成立。1212saaasnp pp1212( )() ()()saaasf nf pf pf p11anp2.1 积性函数积性函数积性函数的定义积性函数的定义假设n的素分解式中有k个不同素因子时结论成立。接下来假设n的素分解式中有k+1个不同的素因子，即则由 以及函数f的积性，可以得到由归纳假设因而112121kkaaaakknp ppp112121(,)1kkaaaakkp ppp112121( )() ()kkaaaakkf nf p ppf p12121212()() ()()kkaaaaaakkf p ppf pf pf p112121( )() ()()

4、()kkaaaakkf nf pf pf pf p2.1 积性函数积性函数积性函数的定义积性函数的定义例例2.1.2：计算数论函数f(d)=d5在d=12时的函数值。解解：首先由于对所有的正整数m, n都有f(mn)=(mn)5，f(n)=n5，f(m)=m5进而 f(mn)=f(m)f(n)即数论函数f(d)=d5是完全积性函数。又12=223，因而 f(12)=f(22) f(3)即 125=(22)5(3)5=248832 2.1 积性函数积性函数除数函数除数函数这一节将证明给定的正整数n的除数（或因数）和除数（或因数）和与除除数（或因数）个数数（或因数）个数函数都是积性函数，并利用正整

5、数n的素分解式给出计算这两个函数的函数值的方法。2.1 积性函数积性函数除数函数除数函数定义定义2.1.2：除数和除数和函数(n)定义为自然数n的所有正因数的和。例例2.1.3： (1)=1 (2)=3 (3)=4 (4)=7 (10)=18 (12)=28 2.1 积性函数积性函数除数函数除数函数定义定义2.1.3：除数个数除数个数函数(n)定义为自然数n的正因数的个数。例例2.1.4： (1)=1 (2)=2 (3)=2 (4)=3 (10)=4 (12)=6 2.1 积性函数积性函数除数函数除数函数易知除数和函数(n)与除数个数函数(n)以求和记号可以分别表示为接下来证明(n)和(n)都

6、是积性函数，首先有如下定义：|( )d nnd|( )1d nn2.1 积性函数积性函数除数函数除数函数定义定义2.1.4：设f是数论函数，则表达式表述了对n的各正因子d的函数值f(d)求和的结果，称函数F为数论函数f的求和函数求和函数。|( )( )d nF nf d2.1 积性函数积性函数除数函数除数函数例例2.1.5：若数论函数f(d)=5d+1则对于f的求和函数F有 F(15)=f(1)+f(3)+f(5)+f(15) =(51+1)+(53+1)+(55+1)+(515+1) =1282.1 积性函数积性函数除数函数除数函数定理定理2.1.2：若f是积性函数，则f的求和函数也是积性函

7、数。证明：证明：需要证明：对于相对互素的正整数m与n，应有F(mn)=F(m)F(n)因而首先假设(m,n)=1。此时由第一章的引理1.3.6我们知道mn的每个因子d都可以唯一地写成m的一个因子d1与n的一个因子d2的乘积，且(d1,d2)=1。|( )( )d nF nf d2.1 积性函数积性函数除数函数除数函数又由f的求和函数的定义2.1.4有进而由于f是积性函数，且(d1,d2)=1，因而|()( )d mnF mnf d1212|()()d md nF mnf d d11221212|()() ()()()( ) ( )d md md nd nF mnf df df df dF m

8、F n2.1 积性函数积性函数除数函数除数函数推论推论2.1.1：除数和函数(n)与除数个数函数(n)都是积性函数。证明：证明：设f(n)=n，g(n)=1，则由例2.1.1知道f与g都是完全积性函数。进而f(n)与g(n)的求和函数(n)与(n)是积性函数。2.1 积性函数积性函数除数函数除数函数接下来我们利用(n)与(n)的积性性质以及n的素分解式，计算(n)与(n)的函数值。2.1 积性函数积性函数除数函数除数函数引理引理2.1.1：设p是素数，a为正整数，则(pa)=1+p+p2+ pa=(pa+1-1)/(p-1)且(pa)=a+1证明：证明：由于pa恰有a+1个因子：1, p, p

9、2, , pa-1, pa因而(pa)=a+1同时 (pa)=1+p+p2+ pa=(pa+1-1)/(p-1)2.1 积性函数积性函数除数函数除数函数例如例如：当p=7，a=6时， (76)=1+7+72+73+74+75+76 =(77-1)/(7-1) =137257而 (76)=6+1 =72.1 积性函数积性函数除数函数除数函数定理定理2.1.3：设正整数n有素分解式则且1212saaasnp pp121111121121111( )1111jsaaaasjsjsjppppnpppp121( )(1)(1)(1)(1)ssjjnaaaa2.1 积性函数积性函数除数函数除数函数证明：证

10、明：由于(n)与(n)都是积性函数，因而有且利用引理2.1.1即知结论成立。12121212( )()() ()()ssaaaaaassnp ppppp12121212( )()() ()()ssaaaaaassnp ppppp2.1 积性函数积性函数除数函数除数函数例例2.1.6：利用定理2.1.3我们可以得到32322222432323221 31 51 71(2100)(23 57)2 13 15 17 17 4 31 86944(2100)(2 35 7)(2 1)(1 1)(2 1)(1 1)4831 51 71(4725)(3 5 7)40 31 83 15 17 19920(47

11、25)(3 5 7)(3 1)(2 1)(1 1)24 2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质n!的标准分解式的标准分解式2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质定义定义2.2.1：一个实数x的高斯函数（也称为下取整函数，地板（floor）函数），是指不超过x的最大整数，记为x，即xxx+1例如：3.6=3，-3.1=-4，=3，-3=-3，0=0。2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质由高斯函数的定义知道，若记x的小数部分为x，则x=x-x且显然0 x1同时x是整数的充要条件是x=0例如： 7/6=7/6-7/6=7/6-1=1/6 -7/

12、8=-7/8-7/8=-7/8-(-1)=1/8 2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(i) 若xy，则xy。证明：证明：由xxyy+1可得xy+1由于x和y都是整数，因此xy2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(ii) 若x=m+v，m是整数，0v1，则m=x，v=x。特别地，当0 x1时，x=0，x=x。证明：证明：由0v1，得到mxm+1故由高斯函数的定义知道结论成立。2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(iii)

13、对任意整数m有：x+m=x+m，x+m=x。 证明：证明：设x=n，因而n是整数，且nxn+1 ，则n+mx+mn+m+1因而x+m=n+m=x+m而 x+m=x+m-x+m=x+m-(x+m)=x2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(iv) x+yx+yx+y+1，其中等号有且仅有一个成立。证明：证明：由x+y=x+x+y+y=x+y+x+y及0 x+y2，那么a) 当0 x+y1时，由(ii)知x+y=x+y；b) 当1x+y2时，x+y=x+y+1+(x+y-1)，由(ii)知x+y=x+y+1。2.2 高斯函数高斯函数x高斯函数

14、高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(v)证明：证明：x为整数时显然成立，当x不是整数时， -x=-(x+x) =-x-x =-x-1+1-x，01-x1由(ii)知成立。 , , 1, 1, xxxxxxxxxxZZZZ及2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(vi) 对正整数m有证明：证明：由带余数除法知，存在整数q，r使得x=qm+r，0rm即x/m=q+r/m，0r/m1故x/m=q xxmm2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质另一方面x/m=x/m+x/m=q+(x+r)/m注意到0

15、x1，0rm由于r是整数，因而0rm-1所以0(x+r)/m1故x/m=q=x/m2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(vii) 不小于x的最小整数是-x。证明：证明：设不小于x的最小整数是a，a-1xa因此， -a-x-a+1所以 -a=-x即 a=-x2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(viii) 小于x的最大整数是-x-1。证明：证明：设小于x的最大整数是a，axa+1因此-a-1 x-a-a-x+1-a+1-x+1=-aa=-x+1=-(-x+1)=-x-12.2 高斯

16、函数高斯函数x高斯函数高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(ix) 大于x的最小整数是x+1。证明：证明：设大于x的最小整数是a，a-1 xa因此a x+1a+1x+1=aa=x+1=x+12.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(x) 离x最近的整数是x+1/2和-x+1/2，当x+1/2是整数时，这两个不同的整数和x等距；当x+1/2不是整数时，它们相等。证明：证明：离x最近的整数必在x和x+1之中，a) 当x+1/2是整数时，由(iii)易知 x=(x+1/2)-1/2 =x+1/2+-1/2=x+1/2-1=

17、x-1/2 =-(-x+1/2)=-(-x-1/2+1)=-(-(x+1/2)+1) =-(x+1/2)+1=-x+1/22.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质 x+1=x-1/2+1 =x+1/2 =x+1/2故x+x+1=x-1/2+ x+1/2=2x所以(x+(x+1)/2=x故x和x+1的中点是x，即它们和x等距。2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质b) 当x+1/2不是整数时，I. 若x1/2，则离x最近的整数是x，又x+1/2=x+x+1/2，0 x+1/21因而x+1/2=x即x=x+1/2II. 若1/2x1，则离x最近的整数是x+1，x+

18、1/2=x+1+x-1/2，0 x-1/21/212.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质因而x+1/2=x+1即x+1=x+1/2故在x+1/2不是整数时，离x最近的整数是x+1/2，又由(v)知此时 -x+1/2=-(x-1/2)=-(-x-1/2-1) =x-1/2+1=x+1/2-1+1 =x+1/2-1+1 =x+1/2 2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质定理定理2.2.1：设x与y是实数，则(xi) 若x0，则不超过x的正整数n的个数等于x，即证明：证明：由于整数nx就是nx，所以结论成立。11 n xx 2.2 高斯函数高斯函数x高斯函数高斯

19、函数x的性质的性质定理定理2.2.1：设x与y是实数，则(xii) 设a与N都是正整数，则正整数1,2,N中被a整除的正整数的个数是N/a。证明：证明：被a整除的正整数是a,2a,3a,.。设1,2,.,N中被a整除的正整数的个数是k，那么必有kaN(k+1)a即kN/ak+1所以结论成立。 2.2 高斯函数高斯函数x高斯函数高斯函数x的性质的性质例例2.2.1：解方程(x+1)/4=(x-1)/2。解：由高斯函数的性质，得：-1(x+1)/4-(x-1)/21，即-1x7而在区间(-1,7)内，显然：当x(-1,1)时，(x+1)/4=0，而(x-1)/2=-1，方程不成立；当x1,3)时，

20、(x+1)/4=(x-1)/2=0；当x3,5)时，(x+1)/4=(x-1)/2=1；当x5,7)时，(x+1)/4=1，而(x-1)/2=2，方程不成立。综上所述，原方程的解是：x|1x5。2.2 高斯函数高斯函数xn!的标准分解式的标准分解式若素数p|n!，则必有某个正整数kn，使得p|k；另一方面，任一素数pn必有p|n!。所以n!的标准分解式必为其中2=p1p2psn是所有不超过n的素数。如此，为了求出n!的标准分解式，在确定了不超过n的素数为p1, p2, , ps之后，只需要确定pj的幂指数aj, 1js。为此先引入一个符号，设k是非负整数，记号ak|b表示b恰被恰被a的的k次幂

21、整除次幂整除，即ak|b，而ak+1 b。11!saasnpp2.2 高斯函数高斯函数xn!的标准分解式的标准分解式定理定理2.2.2：设n是正整数，p是素数，p|n!，则证明：证明：由于一定可以找到整数k使得pknk时dj=02.2 高斯函数高斯函数xn!的标准分解式的标准分解式接下来把整数1, 2,., n分为两两不相交的k个集合，其中第j个集合由1, 2,., n中的dj个恰被pj整除的整数组成。则则第第j个集合的所有整数的乘积恰被个集合的所有整数的乘积恰被p的的jdj次方整除次方整除，由此得到 =1d1+2d2+kdk =c1-c2+2c2-2c3+kck-kck+1 =c1+c2+c

22、k-kck+1 =c1+c2+ck结论得证。2.2 高斯函数高斯函数xn!的标准分解式的标准分解式推论推论2.2.2：设n是正整数，则这里连乘号表示对所有不超过连乘号表示对所有不超过n的素数求积的素数求积，(p,n)由前定义。 此结论可以由定理2.2.2立即推出，显然如果p2p1有(p1,n) (p2,n)( , )!p np nnp2.2 高斯函数高斯函数xn!的标准分解式的标准分解式例例2.2.2：求35!的标准分解式，并求出35!的十进位表示中有多少个零？解解：不超过35的素数有2,3,5,7,11,13,17,19,23,29,31，故3535353535(2,35)1782 1282

23、481632353535(3,35)11 3 1153927353535(5,35)7 1 8(7,35)5525735(11,35)3(13,3511 35)2132.2 高斯函数高斯函数xn!的标准分解式的标准分解式所以35!=228315587511313217219232931。要求出35!的十进位表示中零的个数，就是要求正整数k，使得10k|35!，由上面知道k=8，即5的幂指数，所以结尾处有8个零。3535(17,35)2(19,35)117193535(23,35)1(29,35)1232935(31,35)1312.3 欧拉函数欧拉函数(x) 在第1章中我们定义了欧拉函数，但未

24、给出欧拉函数的性质与函数的求法，本节我们来解决这一问题。欧拉函数欧拉函数(x)的定义的定义欧拉函数欧拉函数(x)值的计算值的计算注：注：(p)：小写希腊字母?(x)：大写希腊字母2.3 欧拉函数欧拉函数(x) 欧拉函数欧拉函数(x)的定义的定义定理定理2.3.1：若p是素数，则(p)=p-1；反之，若自然数p满足等式(p)=p-1，则p是素数。证明：证明：若p是素数，则每个小于p的自然数都与p互素。由于共有p-1个这样的整数，因而(p)=p-1反之，若自然数p满足等式(p)=p-1，若p不是素数，则p=1或p为合数。2.3 欧拉函数欧拉函数(x) 欧拉函数欧拉函数(x)的定义的定义若p=1，则

25、由于(p)=1，因而(p)p-1，矛盾。若p为合数，则p必有一个因子d，1d1，则d|(km+r)，1kn-1即第第r行中的每个元素行中的每个元素km+r与与nm都有大于都有大于1的公因子的公因子d， 也即满足条件(m,r)=d1的第r行中的每个元素都不与nm互素。因而，要找到所有不超过mn且与mn互素的整数，只需只需考察满足条件考察满足条件(m,r)=1的第的第r行中的元素行中的元素。若(m,r)=1，1rm，在这一行中有r, m+r, 2m+r, , (n-1)m+r2.3 欧拉函数欧拉函数(x) 欧拉函数欧拉函数(x)值的计算值的计算由于(m,r)=1，因而这一行中的每一个整数都与这一行

26、中的每一个整数都与m互素互素。同时所有所有n个整数形成了模个整数形成了模n的一个完全剩余系的一个完全剩余系。因而这些整数中恰有(n)个整数与n相对互素，由于这(n)个整数也与m互素，故他们与故他们与nm互素互素。因为一共有一共有(m)行行，每一行有(n)个整数与nm互素，因而(mn)=(m)(n)2.3 欧拉函数欧拉函数(x) 欧拉函数欧拉函数(x)值的计算值的计算定理定理2.3.4：设正整数n有素分解式 则证明：证明：由于欧拉函数是积性函数，因而另外1212saaasnp pp12111( )(1)(1)(1)knnppp1212( )() ()()saaasnppp11()(1),1,2,

27、jjjjaaaajjjjjppppjsp2.3 欧拉函数欧拉函数(x) 欧拉函数欧拉函数(x)值的计算值的计算因而例如 12121212121212111( )(1)(1)(1)111(1)(1)(1)111(1)(1)(1)ssaaassaaasssnppppppp pppppnppp221111(2100)(23 57)2100(1)(1)(1)(1)4802357 2.3 欧拉函数欧拉函数(x) 欧拉函数欧拉函数(x)值的计算值的计算定理定理2.3.5：设正整数n2，则欧拉函数(n)是偶数。证明：证明：设正整数n有素分解式 由于欧拉函数是积性函数，因而又进而1212saaasnp pp1

28、212( )() ()()saaasnppp1()(1)jjaajjjppp2.3 欧拉函数欧拉函数(x) 欧拉函数欧拉函数(x)值的计算值的计算若pj是奇素数，由pj-1是偶数，就有 是偶数；若pj=2且aj1，则由于 是偶数，因而有 是偶数。只要n2，则上面两个条件中必定有一个成立，因而至少存在一个整数j，1js，使得 是偶数。因而只要n是大于2的正整数，则欧拉函数(n)必定是偶数。 ()jajp1jajp()jajp()jajp2.3 欧拉函数欧拉函数(x) 欧拉函数欧拉函数(x)的补充知识的补充知识定理（补充）：定理（补充）：设n为一个正整数，那么|( )d ndn2.4 默比乌斯函数

29、默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念默比乌斯反演公式默比乌斯反演公式2.4 默比乌斯函数默比乌斯函数 若f为数论函数，则由f的函数值我们可以计算出f的求和函数F的值，那么反过来是否可以通过一个简便的方法由f的求和函数F的值来计算f的函数值呢？本节我们将证明这样的方法确实存在。 2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念设f为数论函数，F为f的求和函数则 F(1)=f(1) F(2)=f(1)+f(2) F(3)=f(1)+f(3) F(4)=f(1)+f(2)+f(4) F(5)=f(1)+f(5) F(6)=f(1)+f(2)+f(3)+f(6) .

30、|( )( )d nF nf d2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念若求和函数F的值已知，则由上面的方程组可以求得 f(1)=F(1) f(2)=F(2)-F(1) f(3)=F(3)-F(1) f(4)=F(4)-F(2) f(5)=F(5)-F(1) f(6)=F(6)-F(3)-F(2)+F(1) .2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念由此我们观察到f(n)等于形如F(n/d)的求和函数的值之和，其中d|n。进而我们得到等式 其中是一个数论函数。如果这个等式成立，则 (1)=1，(2)=-1，(3)=-1，(4)=0，

31、(5)=-1，(6)=1， (7)=-1，(8)=0，|( )( ) ( /)d nf nd F n d2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念进一步地，当当p是素数时是素数时，由F(p)=f(1)+f(p)得到f(p)=F(p)-F(1)即(p)=-1。同时，由F(p2)=f(1)+f(p)+f(p2)得到f(p2)=F(p2)-(F(p)-F(1)-F(1)=F(p2)-F(p)即对每个素数p，有(p2)=0。2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念类似的可以证明对每个素数p，有(pk)=0，其中k是大于1的整数。如果我们能证明是

32、积性函数，则的值可以由它在各个素数的幂次的值所确定。由此得到如下定义：2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念定义定义2.4.1：默比乌斯（Mbius）函数定义如下即若即若n能被分解成互不相同的素数的乘积时，能被分解成互不相同的素数的乘积时，r为互不相为互不相同的素数的个数。同的素数的个数。由此定义，一旦n被一个素数的平方整除，则(n)=0121 1( )( 1) 0 rrinnnp ppp若若，其中 是不同的素数其它情况2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念例2.4.1：利用Mbius函数定义2.4.1容易计算得到 (286)=(

33、21113)=(-1)3=-1 (2100)=(223527)=0 (1190)=(25717)=(-1)4=12.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念定理定理2.4.1：Mbius函数(n)是积性函数。证明：证明：设正整数m与n互素，只需证明(mn)=(m)(n)首先考虑m=1或n=1的情形：当m=1时，等式(mn)=(m)(n)两边都等于(n)；对于n=1有类似的结果。2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念接下来考虑m与n中至少有一个可以被一个素数的平方整除的情形：当m与n中至少有一个可以被一个素数的平方整除时，mn也可以被这个

34、素数的平方整除。因而(mn)与(m)(n)都等于0。最后考虑m与n都是无平方因子且大于1的整数：当整数m与n都无平方因子且大于1时，即m=p1p2ps，其中p1, p2, ,ps是不同的素数且2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念n=q1q2qt，其中q1, q2, ,qt也是不同的素数由于m与n互素，因而mn是s+t个不同素数的乘积。进而(mn)=(-1)s+t=(-1)s(-1)t=(m)(n)综上，结论得证。接下来我们证明默比乌斯函数的求和函数是一个特别简单的函数。2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念定理定理2.4.2：M

35、bius函数在整数n处的求和函数F(n)，满足证明：证明：首先当n=1时，有接下来，设n1。|1 1( )( )0 1d nnF ndn若若|1(1)( )(1)1dFd2.4 默比乌斯函数默比乌斯函数 默比乌斯函数的概念默比乌斯函数的概念因为Mbius函数(n)是积性函数，因而其求和函数也是积性函数。现在假设p是素数，k是正整数，则由于当k2时，有(pk)=0，因而有下式成立最后，设n是大于1的正整数，且有素分解式。由于上述等式右边的每一个因子都为0，因而有F(n)=0。2|()( )( 111)( )()()000kkkd pF pdppp 2.4 默比乌斯函数默比乌斯函数 默比乌斯反演公

36、式默比乌斯反演公式默比乌斯反演公式将提供给我们一个以求和函数F的函数值来表述函数f的函数值的方法。2.4 默比乌斯函数默比乌斯函数 默比乌斯反演公式默比乌斯反演公式定理定理2.4.3：设F为数论函数f的求和函数，则对正整数n有证明：证明：该公式的证明涉及到了双重求和。首先，由f的求和函数的定义有进而 |( )( ) ( /)d nf nd F n d|( / )()( )/e n df eF n d |( / )|( / )( ) ( /)( ( )( )( ) ( )d nd ne n dd ne n dd F n ddf ed f e 2.4 默比乌斯函数默比乌斯函数 默比乌斯反演公式默比

37、乌斯反演公式这里需要注意：由对称性，满足条件满足条件d|n且且e|(n/d)的的整数对整数对(d,e)与满足条件与满足条件e|n且且d|(n/e)的整数对的整数对(d,e)是等价是等价的的，因此当n/e1时，求和公式当n/e=1时，即n=e时，求和公式因而定理得证。|( / )|( / )|( / )( ) ( )( ) ( )( ( )( )d ne n de nd n ee nd n ed f ef edf ed |( / )( )0d n ed|( / )( )1d n ed|( / )( ( )( )( ) 1( )e nd n ef edf nf n 2.4 默比乌斯函数默比乌斯函数

38、 默比乌斯反演公式默比乌斯反演公式利用默比乌斯反演公式可以很容易证明以前看起来似乎是很困难的结论。2.4 默比乌斯函数默比乌斯函数 默比乌斯反演公式默比乌斯反演公式例例2.4.2：由推论2.1.1：函数(n)与(n)分别是函数f(n)=n与f(n)=1的求和函数，即且 那么利用Mbius反演公式，得到以下结论：对于所有的整数n，有 且|( )d ndn|( )1d nn|( /) ( )d nnn dd|1( /) ( )d nn dd2.4 默比乌斯函数默比乌斯函数 默比乌斯反演公式默比乌斯反演公式又我们知道若f是积性函数，则f的求和函数也是积性函数。利用默比乌斯反演公式，我们可以将这个结论

39、反过来，即有如下结论：|( )( )d nF nf d2.4 默比乌斯函数默比乌斯函数 默比乌斯反演公式默比乌斯反演公式定理定理2.4.4：设数论函数f具有求和函数 则若F是积性函数，则f也是积性函数。证明：证明：设正整数m与n相对互素，希望证明f(mn)=f(m)f(n)首先若d是mn的因子，则d=d1d2，且d1|m，d2|n，(d1,d2)=1|( )( )d nF nf d2.4 默比乌斯函数默比乌斯函数 默比乌斯反演公式默比乌斯反演公式由Mbius反演公式以及和f都是积性函数，有 12121212| ,|1212| ,|1212|12()( ) ()() ()() () () ()(

40、) ()() ()( ) ( )d mnd m d nd m d nd md nmnmnf mnd Fd dFdd dmnddFFddmnd Fd Fddf m f n2.5 完全数完全数出于某些神秘的信仰，古希腊人对那些除数和函数的函数值等于自身两倍的正整数非常感兴趣，这样的整数称为完全数完全数。2.5 完全数完全数完全数的概念完全数的概念梅森数、费马数梅森数、费马数2.5 完全数完全数完全数的概念完全数的概念定义定义2.5.1：若n是正整数，且其除数和函数(n)=2n，则称n为完全数完全数。2.5 完全数完全数完全数的概念完全数的概念例如：由于 (496)=(3116) =1+2+4+8+

41、16+31+62+124+248+496 =4962=992因而496为完全数。下面的定理告诉我们哪些偶数是完全数。2.5 完全数完全数完全数的概念完全数的概念定理定理2.5.1：正整数n是偶完全数偶完全数的充要条件为n=2m-1(2m-1)其中整数m满足条件m2且2m-1为素数为素数。证明：证明：首先证明若n=2m-1(2m-1)且2m-1为素数，则n是完全数。由于2m-1是奇数，因而(2m-1, 2m-1)=1而除数和函数是积性函数，于是(n)=(2m-1)(2m-1)2.5 完全数完全数完全数的概念完全数的概念由于2m-1为素数，因而(2m-1)=(2m-1+1-1)/(2-1)=2m-

42、1，且(2m-1)=1+2m-1=2m即(n)=(2m-1)2m=2n故n是完全数。接下来证明若n是偶完全数，则n=2m-1(2m-1)这里整数m满足条件m2且2m-1为素数。2.5 完全数完全数完全数的概念完全数的概念记n=2st这里s与t都是正整数，且t为奇数。由于(2s,t)=1因而(n)=(2st)=(2s)(t)=(2s+1-1)(t) (1)由于n是完全数，因而(n)=2n=2s+1t (2)结合(1)与(2)得到2.5 完全数完全数完全数的概念完全数的概念(2s+1-1) (t)=2s+1t (3)由于(2s+1,2s+1-1)=1，进而2s+1|(t)，即存在整数q使得(t)=

43、2s+1q将(t)代入(3)，有(2s+1-1)2s+1q=2s+1t，进而 (2s+1-1)q=t (4)因而q|t且qt。在(4)两边同时加上q，得到t+q=(2s+1-1)q+q=2s+1q=(t) (5)接下来证明q=1。2.5 完全数完全数完全数的概念完全数的概念若q1，由q|t且qt，则t至少有三个不同的正的素因子1，q和t。这表明(t)1+q+t这与(5)相矛盾，因而q=1，因此由(5)得到(t)=1+t即t的正因子只有1和t，因而t为素数。同时由(4)知道t =2s+1-1。故n=2s(2s+1-1)其中2s+1-1为素数。 定理得证。2.5 完全数完全数完全数的概念完全数的概

44、念由上述定理我们看到，要找到完全数，必须找到形如2s-1的素数（称之为梅森素数），即我们已经将偶完全数的研究归结到了梅森素数的研究。但是这里我们需要注意的是完全数和完美无缺的人一样是十分罕见的。从欧几里得开始起，几千年的研究仍然没有搞清楚有没有奇完全数奇完全数。现在只知道如果奇完全数存在，则它们一定具有一定的性质：例如，没有小于100300的奇完全数，奇完全数至少要有8个不同的素因子，最大的素因子至少为1020。2.5 完全数完全数梅森数梅森数、费马数、费马数梅森曾经研究过形如2p-1的素数，并得到结论：当p=2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 1

45、27, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937时，2p-1都是素数。2.5 完全数完全数梅森数梅森数、费马数、费马数定理定理2.5.2：如果m是正整数，且2m-1是素数，则m必为素数。证明：证明：假设则m不为素数，则m=ab，1am，1b1），因而2m-1=2ab-1=(2a-1)(2a(b-1)+2a(b-2)+2a+1)由于等式右边的两个因子都大于1，因而若m不为素数，则2m-1是合数。与假设矛盾，故2m-1是素数时，m必为素数。2.5 完全数完全数梅森数梅森数、费马数、费马数定义定义2.

46、5.2：如果m是正整数，则Mm=2m-1称为第m个梅森梅森(Mersenne)数数。若p为素数，且2p-1也是素数，则称Mp为梅森梅森(Mersenne)素数素数。2.5 完全数完全数梅森数梅森数、费马数、费马数定理定理2.5.3：如果p为奇素数为奇素数，k是正整数，则梅森(Mersenne)数Mp的任意一个因子都具有形式2kp+1。证明：证明：设素数素数q|Mp=2p-1。由费马小定理，有q|(2q-1-1)同时， (2p-1, 2q-1-1)=2(p,q-1)-1 (1)由于素数q是2p-1与2q-1-1的公因子，于是(2p-1,2q-1-1)12.5 完全数完全数梅森数梅森数、费马数、费马数因此(p, q-1)=p。否则若(p, q-1)=1，则由(1)有(2p-1, 2q-1-1)=1矛盾，故(p, q-1)=p即p