因子个数函数与因子和函数
最近在学初等数论，记一些有意思的东西。
主要参考孙智宏《数和数列》以及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$，容易知道等式成立，于是结论得证。