数论与有限域-第二章.pptVIP

第二章 数论函数 第一节 积性函数 一、积性函数的定义 二、除数函数 一、积性函数的定义 定义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的积性，可以得到 一、积性函数的定义 例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