数论函数：\(f:\Z^*\rightarrow C\)
积性函数：对任意 \((m,n)=1\) 满足 \(f(mn)=f(m)f(n)\) 的函数
完全积性函数：对任意 \(m,n\) 满足 \(f(mn)=f(m)f(n)\) 的函数
数论卷积：\(f*g(n)=\sum\limits_{d\mid n} f(d)g(\frac nd)\)
特别地， \(\tau=1*1,\sigma=1*id\)
- 积性函数的数论卷积是积性函数
设 \((n,m)=1\) ，关键是， \(nm\) 的所有因子存在唯一分解 \(d=d_1d_2\) 使得 \(d_1\mid n,d_2\mid m,(d_1,d_2)=1\) （因为它们互素）
\(\sum\limits_{d\mid nm}f(d)g(\frac {nm}d)=\sum\limits_{d_1\mid n,d_2\mid m}f(d_1)f(d_2)g(\frac n{d_1})g(\frac m{d_2})=(\sum\limits_{d\mid n}f(d)g(\frac nd))(\sum\limits_{d\mid m}f(d)g(\frac nd))\)
-
数论卷积具有交换律，结合律和分配律
-
(莫比乌斯反演) \(f*1=g\iff g*\mu =f\)
同样地， \(f(n)=\prod_{d\mid n}g(d)\iff g(n)=\prod_{d\mid n} f(d)^{\mu(\frac nd)}\)
例1
证明： \(\sum\limits_{d\mid n}\sigma(d)=n\cdot \sum\limits_{d\mid n}\frac{\tau(d)}d,n\sum\limits_{d\mid n}\frac{\sigma(d)}d=\sum\limits_{d\mid n}d\tau(d)\)
第一个等式等价于 \(\sigma *1=\tau *id\) ，即 \((1*id)*1=(1*1)*id\) ，由数论卷积的交换律和结合律显然
由于 \(n\tau(n)=\sum\limits_{d\mid n}d\cdot \frac nd=id*id\) ， 第二个等式等价于 \(\sigma*id=1*(id*id)\)
例2
证明： \((\sum_{d\mid n}\tau(d))^2=\sum_{d\mid n}\tau^3(d)\)
由于左右均为积性函数（根据性质1），只需证明 \(n=p^k\) 情况
\(LHS=(\frac{(k+1)(k+2)}2)^2=RHS\)
例3
设 \(g=f*1\) ，求证： \(\sum\limits_{k=1}g(k)=\sum\limits_{k=1}^nf(k)[\frac nk]\)
数论中求和的重要方法是拆分+交换和号（在欧拉函数中已经提及）
实际上， \(RHS=\sum\limits_{k=1}^nf(k)\sum\limits_{k\mid i,i\le n}1=\sum\limits_{i=1}^n\sum\limits_{k\mid i}f(k)=\sum\limits_{i=1}^ng(i)\)
例4
对积性函数 \(f\) 证明： \(\sum\limits_{d\mid n}f(d)\mu(d)=\prod\limits_{p\mid n}(1-f(p))\)
实际上设 \(d\) 的素因子为 \(p_1,p_2,...,p_k\) ，则左式即 \(1-\sum f(p_i)+\sum f(p_ip_j)-...+(-1)^kf(p_1p_2...p_k)=RHS\)
例5
证明 \(\sum\limits_{m\le n,(m,n)=1}m^k=\sum \limits_{d\mid n}\mu(d)\sum\limits_{i\le n,d\mid i}i^k\)
关键是 \(\sum\limits_{d\mid n} \mu(d)=\delta_{n1}\) 给出 \(\sum\limits_{i\mid (d,n)}\mu(i)=1\) 当且仅当 \((d,n)=1\) ，这是使用莫比乌斯函数拆分 \(\delta_{i1}\)
\(RHS=\sum\limits_{i=1}^ni^k\sum\limits_{d\mid i,d\mid n}\mu(d)=\sum\limits_{i=1}^ni^k\sum\limits_{d\mid(i,n)}\mu(d)=LHS\)
例6
证明 \(\sum\limits_{k=0}^{m-1}\varphi(2k+1)[\frac{m+k}{2k+1}]=m^2\)
记 \(a_m=\sum\limits_{k=0}^{m-1}\varphi(2k+1)[\frac{m+k}{2k+1}]\) ，有 \(a_{m+1}-a_m=\sum\limits_{k=0}^{m-1}\varphi(2k+1)([\frac{m+k+1}{2k+1}]-[\frac{m+k}{2k+1}])+\varphi(2m+1)\)
关键是 \([\frac{m+k+1}{2k+1}]-[\frac{m+k}{2k+1}]=1_{2k+1\mid m+k+1}=1_{2k+1\mid2m+2k+2}=1_{2k+1\mid2m+1}\)
从而 \(a_{m+1}-a_m=\sum\limits_{2k+1\mid 2m+1}\varphi(2k+1)=2m+1\) （包含了 \(2m+1\) ）
归纳完成证明
标签：frac,函数,limits,数论,sum,mid,计算,id,2k From： https://www.cnblogs.com/Rocking-Yoshi/p/18309119