数论与有限域第二章

第二章数论函数第一节

积性函数一、积性函数的定义二、除数函数一、积性函数的定义定义2.1.1

设正整数m与n互素，若f(mn)=f(m)f(n)，则称数论函数f为积性函数。更一般的，若对所有的正整数m,n都有f(mn)=f(m)f(n)，则称数论函数f为完全积性函数。例2.1.1

若函数f在任意正整数n处的函数值都为1，即

n

Z+，f(n)=1，则函数f是完全积性函数；而若函数f在任意正整数n处的函数值都为正整数n自身，即

n

Z+，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.1

设正整数n有素分解式，则积性函数f的函数值。证明：对正整数n的素分解式中不同素因子的个数进行数学归纳。若n的素分解式中只有素因子p1，即，则结论显然成立。假设n的素分解式中有k个不同素因子时结论成立。接下来假设n的素分解式中有k+1个不同的素因子，即。则由以及函数f的积性，可以得到

由归纳假设因而f(n)=一、积性函数的定义例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=22×3，因而f(12)=f(22)f(3)，即125=(22)5×(3)5=248832。二、除数函数定义2.1.2

除数和函数σ(n)定义为自然数n的所有正因数的和。例2.1.3σ(1)=1；σ(2)=3；σ(3)=4；σ(4)=7；σ(10)=18；σ(12)=28，…。定义2.1.3

除数个数函数τ(n)定义为自然数n的正因数的个数。例2.1.4

τ(1)=1；τ(2)=2；τ(3)=2；τ(4)=3；τ(10)=4；τ(12)=6，…。易知除数和函数σ(n)与除数个数函数τ(n)以求和记号可以分别表示为

σ(n)=与τ(n)=

二、除数函数定义2.1.4

设f是数论函数，则表达式表述了对n的各正因子d的函数值f(d)求和的结果，称函数F为数论函数f的求和函数。例2.1.5

若数论函数f(d)=5d+1，则对于f的求和函数F有F(15)=f(1)+f(3)+f(5)+f(15)=(5×1+1)+(5×3+1)+(5×5+1)+(5×15+1)=128。二、除数函数定理2.1.2

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

=F(m)F(n)。

二、除数函数

推论2.1.1

除数和函数σ(n)与除数个数函数τ(n)都是积性函数。证明：设f(n)=n，g(n)=1，则由例2.1.1知道f与g都是完全积性函数。进而f(n)与g(n)的求和函数σ(n)与τ(n)是积性函数。引理2.1.1

设p是素数，a为正整数，则σ(pa)=1+p+p2+…+pa=(pa+1-1)/(p-1)且τ(pa)=a+1。证明：由于pa恰有a+1个因子：1,p,p2,…,pa-1,pa。因而τ(pa)=a+1。同时σ(pa)=1+p+p2+…+pa=(pa+1-1)/(p-1)。例如：当p=7，a=6时，σ(74)=1+7+72+73+74+75+76=(77-1)/(7-1)=137257，而

τ(76)=6+1=7。二、除数函数定理2.1.3设正整数n有素分解式，则且证明：由于σ(n)与τ(n)都是积性函数，因而有且。二、除数函数例2.1.6利用定理2.1.3我们可以得到第二节高斯函数[x]一、高斯函数[x]的性质二、n！的标准分解式一、高斯函数[x]的性质定义2.2.1

一个实数x的高斯函数（也称为下取整函数，地板（floor）函数），是指不超过x的最大整数，记为[x]，即[x]≤x<[x]+1。例如

[3.6]=3，[-3.1]=-4，[π]=3，[-3]=-3，[0]=0。若记x的小数部分为{x}，则{x}=x-[x]，且0≤{x}<1，同时x是整数的充要条件是{x}=0。例如

{7/6}=7/6-[7/6]=7/6-1=1/6，

{-7/8}=-7/8-[-7/8]=-7/8-(-1)=1/8。

一、高斯函数[x]的性质定理2.2.1

设x与y是实数，则若x≤y，则[x]≤[y]；若x=m+v，m是整数，0≤v<1，则m=[x]，v={x}。特别地，当0≤x<1时，[x]=0，{x}=x；对任意整数m有：[x+m]=[x]+m，{x+m}={x}；[x]+[y]≤[x+y]≤[x]+[y]+1，其中等号有且仅有一个成立；及；对正整数m有；一、高斯函数[x]的性质定理2.2.1

设x与y是实数，则不小于x的最小整数是-[-x]；小于x的最大整数是-[-x]-1；大于x的最小整数是[x]+1；离x最近的整数是[x+1/2]和-[-x+1/2]，当x+1/2是整数时，这两个不同的整数和x等距；当x+1/2不是整数时，它们相等；若x≥0，则不超过x的正整数n的个数等于[x]，即；设a与N都是正整数，则正整数1,2,…,N中被a整除的正整数的个数是[N/a]。一、高斯函数[x]的性质若x≤y，则[x]≤[y]；

证明：由[x]≤x≤y<[y]+1即得；若x=m+v，m是整数，0≤v<1，则m=[x]，v={x}。特别地，当0≤x<1时，[x]=0，{x}=x；证明：由0≤v<1，得到m≤x<m+1；对任意整数m有：[x+m]=[x]+m，{x+m}={x}。

证明：设[x]=n，则

[x]=n

n≤x<n+1

n+m≤x+m<n+m+1，因而[x+m]=[x]+m。而

{x+m}=x+m-[x+m]=x+m-([x]+m)={x}；一、高斯函数[x]的性质[x]+[y]≤[x+y]≤[x]+[y]+1，等号有且仅有一个成立；

证明：x+y=[x]+{x}+[y]+{y}=[x]+[y]+{x}+{y}，及0≤{x}+{y}<2，那么当0≤{x}+{y}<1时，由（ii）知[x+y]=[x]+[y]；当1≤{x}+{y}<2时，x+y=[x]+[y]+1+({x}+{y}-1)，由（ii）知[x+y]=[x]+[y]+1；及；

证明：x为整数时显然成立，当x不是整数时，

-x=-[x]-{x}=-[x]-1+1-{x}，0<1-{x}<1,

由（ii）知成立。一、高斯函数[x]的性质对正整数m有；

证明：由带余数除法知，存在整数q，r使得

[x]=qm+r，0≤r<m，即

[x]/m=q+r/m，0≤r/m<1，

[[x]/m]=q；另一方面x/m=[x]/m+{x}/m=q+({x}+r)/m，注意到0≤{x}<1，0≤r<m，由于r是整数，因而0≤r≤m-1，∴0≤({x}+r)/m<1，

[x/m]=q。一、高斯函数[x]的性质不小于x的最小整数是-[-x]；证明：设不小于x的最小整数是a，a-1<x≤a，因此，-a≤-x<-a+1，所以-a=[-x]，即a=-[-x]。小于x的最大整数是-[-x]-1；大于x的最小整数是[x]+1；一、高斯函数[x]的性质离x最近的整数是[x+1/2]和-[-x+1/2]，当x+1/2是整数时，这两个不同的整数和x等距；当x+1/2不是整数时，它们相等；证明：离x最近的整数必在[x]和[x]+1之中，当x+1/2是整数时，

[x]+1=[x+1/2]，[x]=-[-x+1/2]，且它们和x等距；当x+1/2不是整数时，若{x}<1/2，则离x最近的整数是[x]，又

x+1/2=[x]+{x}+1/2，0≤{x}+1/2<1，因而[x]=[x+1/2]；若1/2<{x}<1，则离x最近的整数是[x]+1，又

x+1/2=[x]+1+{x}-1/2，0<{x}-1/2<1，因而[x]+1=[x+1/2]，故在x+1/2不是整数时，离x最近的整数是[x+1/2]，又由(v)知此时

[x+1/2]=-[-x-1/2]-1=-[-x+1/2-1]-1=-[-x+1/2]。一、高斯函数[x]的性质若x≥0，则不超过x的正整数n的个数等于[x]，即；

证明：由于整数n≤x就是n≤[x]，所以结论成立。设a与N都是正整数，则正整数1,2,…,N中被a整除的正整数的个数是[N/a]。证明：被a整除的正整数是a,2a,3a,...。设1,2,...,N中被a整除的正整数的个数是k，那么必有ka≤N<(k+1)a，即k≤N/a<k+1，所以结论成立。

一、高斯函数[x]的性质例2.2.1

解方程[(x+1)/4]=[(x-1)/2]。解：由高斯函数的性质，得：-1<(x+1)/4-(x-1)/2<1，即-1<x<7。而在区间(-1,7)内，显然：当x

(-1,1)时，[(x+1)/4]=0，而[(x-1)/2]=-1，方程不成立；当x

[1,3)时，[(x+1)/4]=[(x-1)/2]=0；当x

[3,5)时，[(x+1)/4]=[(x-1)/2]=1；当x

[5,7)时，[(x+1)/4]=1，而[(x-1)/2]=2，方程不成立。综上所述，原方程的解是：{x|1≤x<5}。二、n！的标准分解式

若素数p|n！，则必有某个正整数k

n，使得p|k；另一方面，任一素数p≤n必有p|n！。所以n！的标准分解式必为，其中2=p1<p2<…ps≤n是所有不超过n的素数。如此，为了求出n！的标准分解式，在确定了不超过n的素数为p1，p2，…，ps之后，只需要确定pj的幂指数aj，1≤j≤s。为此先引入一个符号，设k是非负整数，记号ak||b表示b恰被a的k次幂整除，即ak|b，而ak+1∤b。二、n！的标准分解式定理2.2.2

设n是正整数，p是素数，pα||n!，则α=α(p,n)=。证明：由于一定可以找到整数k使得pk≤n<pk+1，因而α实际上是一有限和，即。设j是给定的正整数，cj表示1,2,...,n中能被pj整除的个数，即cj=[n/pj]，dj表示1,2,...,n中恰被pj整除的个数，则dj=cj-cj+1，即dj=[n/pj]-[n/pj+1]，那么当j>k时dj=0。二、n！的标准分解式定理2.2.2

设n是正整数，p是素数，pα||n!，则α=α(p,n)=。证明：接下来把整数1,2,...,n分为两两不相交的k个集合，其中第j个集合由1,2,...,n中的dj个恰被pj整除的整数组成。则第j个集合的所有整数的乘积恰被p的j∙dj次方整除，由此得到α=1∙d1+2∙d2+…+k∙dk。推论2.2.2

设n是正整数，则，这里连乘号表示对所有不超过n的素数求积，α(p,n)由前定义。例2.2.2

求35!的标准分解式，并求出35！的十进位表示中有多少个零？解：不超过35的素数有2,3,5,7,11,13,17,19,23,29,31，故所以35!=228∙315∙58∙75∙113∙132∙172∙19∙23∙29∙31。第三节欧拉函数

(x)一、欧拉函数

(x)的定义二、欧拉函数

(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为合数。若p=1，则由于φ(p)=1，因而φ(p)≠p-1，矛盾。若p为合数，则p必有一个因子d，1<d<p，且d不与p互素，即p-1个整数1,2,…,p-1中至少有一个不与p互素，因而φ(p)≤p-2，矛盾。因而若φ(p)=p-1，则p必定是素数。二、欧拉函数

(x)值的计算定理2.3.2

设p是素数，a为正整数，则φ(pa)=pa-pa-1。证明：首先小于pa且不与pa互素的自然数是不大于pa且被p整除的一些整数。这些整数应具有形式kp，其中1≤k≤pa-1。由于恰有pa-1个这样的整数，因而共有pa-pa-1个小于pa且与pa相对互素的整数，进而有φ(pa)=pa-pa-1。例如φ(212)=212-211=2048，φ(73)=73-72=294。

二、欧拉函数

(x)值的计算定理2.3.3

设m,n是两个相对互素的正整数，则φ(mn)=φ(m)φ(n)。证明：首先将所有不超过mn的正整数作如下排列1m+12m+1…(n-1)m+12m+22m+2…(n-1)m+23m+32m+3…(n-1)m+3…..r

m+r2m+r

…(n-1)m+r.............................m2m3m

…

nm

接下来设正整数r

m，且(m,r)=d>1，则d|(km+r)，1≤k≤n-1，即第r行中的每个元素km+r与nm都有大于1的公因子d，也即满足条件(m,r)=d>1的第r行中的每个元素都不与nm互素。满足(m,r)=d>1的第r行中的每个元素都不与nm互素。因而，只需考察满足条件(m,r)=1的第r行中的元素。若(m,r)=1，1≤r≤m，在这一行中有r,m+r,2m+r,…,(n-1)m+r。由于(m,r)=1，因而这一行中的每一个整数都与m互素。同时所有n个整数形成了模n的一个完全剩余系。因而这些整数中恰有φ(n)个整数与n相对互素，由于这φ(n)个整数也与m互素，故他们与nm互素。因为一共有φ(m)行，每一行有φ(n)个整数与nm互素，因而φ(mn)=φ(m)φ(n)。二、欧拉函数

(x)值的计算定理2.3.4

设正整数n有素分解式，则证明：由于欧拉函数是积性函数，因而另外因而二、欧拉函数

(x)值的计算定理2.3.5

设正整数n>2，则欧拉函数φ(n)是偶数。证明：设正整数n有素分解式。由于欧拉函数是积性函数，因而又，进而若pj是奇素数，由pj-1是偶数，就有是偶数；若pj=2且aj>1，则由于是偶数，因而有是偶数。只要n>2，则上面两个条件中必定有一个成立，因而至少存在一个整数j，1≤j≤s，使得是偶数。因而只要n是大于2的正整数，则欧拉函数φ(n)必定是偶数。二、欧拉函数

(x)值的计算例如

第四节Möbius函数

一、Möbius函数二、Möbius反演公式

若f为数论函数，则由f的函数值我们可以计算出f的求和函数F的值，那么反过来是否可以通过一个简便的方法由f的求和函数F的值来计算f的函数值呢？本节我们将证明这样的方法确实存在。

一、Möbius函数

设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)….若求和函数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)….一、Möbius函数

由此我们观察到f(n)等于形如±F(n/d)的求和函数的值之和，其中d|n。进而我们得到等式

其中μ是一个数论函数。如果这个等式成立，则μ(1)=1，μ(2)=-1，μ(3)=-1，μ(4)=0，μ(5)=-1，μ(6)=1，μ(7)=-1，μ(8)=0，…。进而由F(p)=f(1)+f(p)，得到f(p)=F(p)-F(1)这里p是素数，即μ(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。类似的推理可以证明对每个素数p，有μ(pk)=0，其中k是大于1的整数。如果我们能证明μ是积性函数，则μ的值可以由它在各个素数的幂次的值所确定。由此得到如下定义一、Möbius函数

定义2.4.1Möbius函数定义如下由此定义，一旦n被一个素数的平方整除，则μ(n)=0。例2.4.1利用Möbius函数定义2.4.1容易计算得到μ(286)=μ(2×11×13)=(-1)3=-1，μ(2100)=μ(22×3×52×7)=0，μ(1190)=μ(2×5×7×17)=(-1)4=1。一、Möbius函数

定理2.4.1Möbius函数μ(n)是积性函数。证明：设正整数m与n互素。以下证明μ(mn)=μ(m)μ(n)。首先考虑m=1或n=1的情形。当m=1时，等式μ(mn)=μ(m)μ(n)两边都等于μ(n)。当m与n中至少有一个可以被一个素数的平方整除时，mn也可以被这个素数的平方整除。因而μ(mn)与μ(m)μ(n)都等于0。当整数m与n都无平方因子且大于1时，即m=p1p2…ps，其中p1,p2,…,ps是不同的素数，且n=q1q2…qt，其中q1,q2,…,qt也是不同的素数。由于m与n互素，因而mn是s+t个不同素数的乘积。进而μ(mn)=(-1)s+t=(-1)s(-1)t=μ(m)μ(n)。一、Möbius函数

定理2.4.2Möbius函数在整数n处的求和函数F(n)，满足证明：首先当n=1时，有设n>1。因为Möbius函数μ(n)是积性函数，因而其求和函数也是积性函数。现在假设p是素数，k是正整数，则由于当i≥2时，有μ(pi)=0，因而有下式成立=1+(-1)+0+…+0=0。最后，设n是大于1的正整数，且有素分解式。由于上述等式右边的每一个因子都为0，因而有F(n)=0。二、Möbius反演公式定理2.4.3

设F为数论函数f的求和函数，则对

正整数n有证明：该公式的证明涉及到了双重求和.首先，由f的求和函数的定义有F(n/d)=，进而这里需要注意：由对称性，满足条件d|n且e|(n/d)的整数对(d,e)与满足条件e|n且d|(n/e)的整数对(d,e)是等价的，因而二、Möbius反演公式定理2.4.3

设F为数论函数f的求和函数，则对

正整数n有证明：当n/e≠1时，知求和式而当n/e=1时，即n=e时，求和式因而二、Möbius反演公式例2.4.2由推论2.1.1：函数σ(n)与τ(n)分别是函数f(n)=n与f(n)=1的求和函数，即

σ(n)=且

τ(n)=那么利用Möbius反演公式，得到以下结论：对于所有的整数n，有

n=且

1=

二、Möbius反演公式定理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。由Möbius反演公式以及μ和f都是积性函数，有

第五节完全数一、完全数定义与性质二、梅森数、费马数一、完全数定义与性质定义2.5.1

若n是正整数，且其除数和函数σ(n)=2n，则称n为完全数。例如由于σ(496)=σ(31×16)=1+2+4+8+16+31+62+124+248+496=496×2=992，

因而496为完全数。一、完全数定义与性质定理2.5.1

正整数n是偶完全数的充要条件为n=2m-1(2m-1)，其中整数m满足条件m≥2且2m-1为素数。证明：首先证明若n=2m-1(2m-1)且2m-1为素数则n是完全数。由于2m-1是奇数，因而(2m-1,2m-1)=1，而除数和函数是积性函数，于是σ(n)=σ(2m-1)σ(2m-1)。由于2m-1为素数，因而σ(2m-1)=2m-1，且σ(2m-1)=2m，即σ(n)=(2m-1)2m=2n，故n是完全数。定理2.5.1

正整数n是偶完全数的充要条件为n=2m-1(2m-1)，其中整数m满足条件m≥2且2m-1为素数。证明：接下来证明若n是偶完全数，则n=2m-1(2m-1)，这里整数m满足条件m≥2且2m-1为素数。记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）得到(2s+1-1)σ(t)=2s+1t。（3）由于(2s+1,2s+1-1)=1，进而2s+1|σ(t)，即存在整数q使得σ(t)=2s+1q。证明：

(2s+1-1)σ(t)=2s+1t。（3）由于(2s+1,2s+1-1)=1，进而2s+1|σ(t)，即存在整数q使得σ(t)=2s+1q。将σ(t)代入（3），有(2s+1-1)2s+1q=2s+1t，进而

(2s+1-1)q=t。（4）因而q|t且q≠t。在（4）两边同时加上q，得到t+q=(2s+1-1)q+q=2s+1q=σ(t)。（5）接下来证明q=1。若q≠1，由q|t且q≠t，则t至少有三个不同的正的素因子1，q和t。这表明σ(t)≥1+q+t，这与（5）相矛盾，因而q=1，进而由（4）知道t=2s+1-1。而由（5）得到σ(t)=1+t，即t的正因子只有1和t，因而t为素数。故n=2s(2s+1-1)，其中2s+1-1为素数。二、梅森数、费马数定理2.5.2

如果m是正整数，且2m-1是素数，则m必为素数。证明：假设则m不为素数，则m=ab，1<a<m，1<b<m，（2m-1是素数，所以1<m），因而2m-1=2ab-1=(2a-1)(2a(b-1)+2a(b-2)+…+2a+1)由于等式右边的两个因子都大于1，因而若m不为素数，则2m-1是合数。与假设矛盾，故2m-1是素数时，m必为素数。定义2.5.2

如果m是正整数，则Mm=2m-1称为第m个梅森(Mersenne)数；若p为素数，2p-1也是素数，则称Mp为梅森(Mersenne)素数。二、梅森数、费马数定理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