約數個數函數的一個性質證明，以及其推廣
- 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}) ，就容易證明了。
已打表檢驗正確。
