约数个数函数的一个性质证明，以及其推广
- 2020 年 3 月 15 日
- 笔记
要用到这个性质，而且网上几乎没有能看的证明，所以特别提出来整理一下。
Original
二维
[ d(AB) = sum_{x|A} sum_{y|B} [gcd (x,y) = 1] ]
其中 (d) 是约数个数函数，即 (d_k (n) = sum_{d|n} 1)
（看上去比较不可思议对吧）
右侧的枚举，一部分因子算多了（比如当 (gcd(x,y)=1) 且额外有 (x|B,y|A) 时，可以枚举出 (x*y = y*x) ），一部分因子又没有算（比如当 (gcd(A,B) not= 1) 时的 (A*B) ）。但是算多和算少之间达成了诡异的平衡。
首先考虑 (A,B) 互质的情况。显然此时右式中的 ([gcd (x,y) = 1]) 恒成立。而左式可以通过积性函数的性质拆开。两侧都为 (d(A)*d(B)) ，成立。（其实并没有按是否互质讨论的必要，但是这样想能让我们的思路更加清晰）
那么考虑 (gcd(A,B) not= 1) 时的情况。不妨先证明 (A = p^a, B = p^b) （ (p) 是素数，这两个 (p) 是同一个数）时等式成立。
这部分的证明是容易的。根据约数个数的定义，左式显然为 (a+b+1)。对于右式，设 (x = p^c, y= p^d) ，若要使 ([gcd (x,y) = 1]) 成立， (c,d) 中至少有一个为 (0) 。那么当 (b=0)时，(c in [0, a])；当 (a=0) 时， (c in [0,b]) ；其他情况都不满足条件。排除重复的 (c=0, d=0) ，共有 (a+b+1) 个情况成立，与左式相同，故等式成立。
讨论更加一般的情况。有了前面的证明，我们考虑将 (AB) 分解质因数后食用，分解后的每一项的形式为 (p^{a+b}) 。左边根据约数个数基本性质“指数加一连乘积”，即每一个 (p) 对应的 ((a+b+1)) 之积。对于右侧，前证说明对于每个 (p) ，合法的 (c,d) 的选择有对应的 (a+b+1) 种，要让 ([gcd(x,y)=1]) 需要每一个 (p) 都是合法情况。而每个 (p) 相对独立，其本质就是许多个“选择”，直接用乘法原理合并起来即可，于是也与左式相同。
用通俗一点的说法，我不管其他的 (p) 到底需要让 (x,y) 满足什么样的条件才能使 ([gcd(x,y)=1]) ，反正在我这个 (p) 这里只有 (a+b+1) 种方案合法。
总之这样就证毕了。
证明思路很像积性函数的合并，也许对其他一些积性函数命题的证明这种方法也管用。
高维
对于形如
[ d(ABC) = sum_{x|A} sum_{y|B} sum_{z|C} [gcd (x,y) = 1] [gcd (y,z) = 1] [gcd (x,z) =1] ]
的高维拓展，证明思路基本相同，不再赘述。（如果觉得有点迷可以先跳过，Extended里的证明更加接近本质）
Extended (update 2020/03/08)
下面研究 Original 推广到广义约数个数函数的形式。
二维
[ sigma_k (AB) = sum_{x|A} sum_{y|B} [gcd(x,y)=1] (x frac{B}{y})^k = sum_{x|A} sum_{y|B} [gcd(x,frac{B}{y})=1] (x y)^k ]
其中 (sigma_k) 是广义的约数个数函数，即 (sigma_k (n) = sum_{d|n} d^k)
显然中式和右式是等价的。现证明左式和右式等价。
证明思路与上面基本一致。同样的，我们先解决 (A=p^a, B=p^b) 的情况。
首先，直接由定义得出左式：
[ 左式 = sum_{i=0}^{a+b} p^{ik} ]
同样设 (x=p^c, y=p^d) 。分析 ([gcd(x,frac{B}{y})=1]) 的意义，它的意思是若 (x) 中不含 (p) （ (c=0) ），则 (y) 可以随便选（ (d in [0,b]) ）；若 (x) 中含 (p) （ (c in [1,a]) ），则 (y) 就必须包含所有的 (p) （ (d=b) ），否则 (frac{B}{y}) 里就含有 (p) 了；其他情况不满足条件 。
即合法的情况为 ((0,[0,b])) 和 (([1,a],b)) 。
那么，根据右式的形式，可以得出
[ begin{aligned} 右式 &= sum_{i=0}^b p^0 p^i + sum_{i=0}^a p^i p^b \ &= sum_{i=0}^b p^i + sum_{i=0}^a p^{b+i} end{aligned} ]
该式实际上只是将左式的枚举从 (b) 那里切开了。两式是等价的。
那么和上面一样的，对于一般的情况分解质因数，对每一个 (p) 分别考虑，积性合并即可。全部乘起来的依据也是乘法原理（ (sum * sum) 就是在枚举所有的方案对应贡献乘积之和）。可能有人问：这里的 (B) 不是发生变化了吗？其实 (B) 充当的是一个 (y) 的全集，不是 (p^b) 了也不影响 (x,y) 的取值，所以是没有关系的。可以参考一下 Original 里“通俗一点的说法”。
高维
形如
[ sigma_k (ABC) = sum_{x|A} sum_{y|B} sum_{z|C} [gcd(x,frac{B}{y})=1] [gcd(y,frac{C}{z})=1] [gcd(x, frac{C}{z}=1)] (x y z)^k ]
的高维拓展， (gcd) 部分就是如 (x-y) ， (x-z) ， (y-z) 两两配对的形式，这样来限制取值范围。
证明思路基本相同，同样写出合法情况 ((0,0,[0,c])) ， ((0,[1,b],c)) ， (([1,a],b,c)) ，对应 (p^{a+b+c+1}) ，就容易证明了。
已打表检验正确。
