因子個數函數與因子和函數
最近在學初等數論，記一些有意思的東西。
主要參考孫智宏《數和數列》以及Kenneth H. Rosen《初等數論及其應用》
0. 算術基本定理
似乎數學的每一個分支都有基本定理，算術也不例外。
算術基本定理：$n$為大於1的自然數，在不計次序的情況下，$n$可唯一地表示為有限個素數的乘積。
結論是trivial的，就不證明了。
由算術基本定理，定義$n$的標准分解式：
$$n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_r^{\alpha_r}$$
其中$p_1,p_2,\cdots,p_r$為素數且$p_1<p_2<\cdots<p_r$
1. 因子個數函數
定義因子個數函數$\tau(n)$為正整數$n$的正因子個數，因子和函數$\sigma(n)$為$n$的所有正因子的和。
由正整數$n$的標准分解式$n=p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_r^{\alpha_r}$可知，$n$的所有因子形如$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdots p_r^{\beta_r}$，其中$\beta_i\in\{0,1,2,\cdots,\alpha_i\}$，由於$p_1,p_2,\cdots,p_r$是$r$個素因子，$\beta_i$有$\alpha_i+1$種可能，根據簡單的排列組合知識，容易得到因子個數函數：
$$\tau(n)=\sum_{d\mid n}1=(\alpha_1+1)(\alpha_2+1)\cdots(\alpha_r+1)=\prod_{i=1}^r(a_i+1)$$
相比因子個數函數，因子和函數不那麼容易得到，需先證明相關結論。
2. 乘性函數
乘性函數指定義在正整數集合上的函數$f$，對任意互素的$m,n$，都有$f(mn)=f(m)f(n)$。可以證明，因子個數函數與因子和函數都為乘性函數。
定理：如果$f$是乘性函數，則$f$的和函數也為乘性函數，即$F(n)=\sum_{d\mid n}f(d)$是乘性函數。
證明：設$m,n$是互素的自然數，則$F(mn)=\sum_{d\mid mn}f(d)$，由於$(m,n)=1$，$mn$的每一個因子都可寫成$m$的因子$d_1$和$n$的因子$d_2$，且$(d_1,d_2)=1$，所以：
$$
\begin{align*}
F(mn)&=\sum_{\stackrel{d_1\mid m}{d_2\mid n}}f(d_1d_2) \\
&=\sum_{\stackrel{d_1\mid m}{d_2\mid n}}f(d_1)f(d_2) \\
&=\sum_{d_1\mid m}f(d_1)\sum_{d_2\mid m}f(d_2) \\
&=F(m)F(n)
\end{align*}
$$
定理得證。
根據該定理，由於$f(n)=n$和$g(n)=1$都是乘性的，所以函數$\sigma(n)=\sum_{d\mid n}f(d)$和$\tau(n)=\sum_{d\mid n}g(d)$為乘性函數。
根據此結論，重新考慮因子個數函數。當$m=p^\alpha$，其中$p$為素數時，$m$的因數個數為$\alpha+1$，這是容易證明的。又由乘性函數可知：
$$\tau(n)=\tau(p_1^{\alpha_1}\cdots p_r^{\alpha_r})=\tau(p_1^{\alpha_1})\cdot\tau(p_2^{\alpha_2})\cdots\tau(p_r^{\alpha_r})=\prod_{i=1}^r(a_i+1)$$
與上面得到的式子相同。
3. 因子和函數
同樣的，先考慮$m=p^\alpha$的情況，則$m$的因子分別為$1,p,p^2,\cdots,p^\alpha$，於是：
$$\sigma(m)=1+p+p^2+\cdots+p^\alpha=\frac{p^{\alpha+1}-1}{p-1}$$
由於$\sigma$是乘性函數，得到因子和函數：
$$\sigma(n)=\sigma(p_1^{\alpha_1}\cdots p_r^{\alpha_r})=\sigma(p_1^{\alpha_1})\cdot\sigma(p_2^{\alpha_2})\cdots\sigma(p_r^{\alpha_r})=\prod_{i=1}^r\frac{p_i^{\alpha_i+1}-1}{p_i-1}$$
4. 應用-完全數
完全數指因子和等於其自身兩倍的數，即滿足$\sigma(n)=2n$的自然數$n$。最小的三個完全數是6，28和496。
古希臘人很早就知道了偶完全數的一種表示方法：$n=2^{p-1}(2^p-1)$，其中$p$和$2^p-1$都為素數。設$2^p-1=q$直接用因子和函數求$n$的因子和：
$$\sigma(n)=\sigma(2^{p-1}q)=\frac{2^p-1}{2-1}\cdot(q+1)=(2^p-1)\cdot2^p=2n$$
1747年，歐拉證明了，所有偶完全數都具有上述形式，證明如下：
設$n$為偶完全數，則$n=2^\alpha n_0$，其中$n_0$為奇數，$\alpha\ge1$，求$n$的因子和：
$$\sigma(n)=\sigma(2^\alpha n_0)=\sigma(2^\alpha)\sigma(n_0)=(2^{\alpha+1}-1)\sigma(n_0)$$
因為$n$為偶完全數，所以：
$$(2^{\alpha+1}-1)\sigma(n_0)=2n=2^{\alpha+1} n_0$$
因此$2^{\alpha+1}-1\mid 2^{\alpha+1} n_0$，又由於$2^{\alpha+1}-1$與$2^{\alpha+1}$互素，所以$2^{\alpha+1}-1\mid n_0$
設$n_0=k(2^{\alpha+1}-1)$，顯然$k<n$，由上知：
$$\sigma(n_0)=2^{\alpha+1}k=n_0+k$$
這表明$k$與$n_0$是$n_0$僅有的兩個因子，於是可知$k=1$且$n_0=2^{\alpha+1}-1$是素數。
設$p$是$\alpha+1$的素因子，則由：
$$2^{\alpha+1}-1=(2^p)^{\frac{\alpha+1}{2}}-1$$
可知其為$2^p-1$的倍數，但$2^{\alpha+1}-1$是素數，所以$\alpha+1=p$是素數。
此時$n_0=2^p-1$是素數，$n=2^{\alpha}n_0=2^{p-1}(2^p-1)$，定理得證。
5. 推廣(一道習題)
書後有一道習題，要求證明Liouville關於$1^3+2^3+\cdots+n^3=(1+2+\cdots+n)^2$的如下推廣：
$$\sum_{m\mid n}(\tau(m))^3=\left(\sum_{m\mid n}\tau(m)\right)^2$$
根據定理：乘性函數的和函數是乘性函數，一眼就能看出左右式都是乘性函數。所以只要考慮$m=p^\alpha$，$p$為素數的情況。對於這種情況，$\tau(m)=\alpha+1$，結合已知結論$\sum_1^n i^3=(\sum_1^n i)^2$，容易知道等式成立，於是結論得證。