因子個數函數與因子和函數

最近在學初等數論，記一些有意思的東西。
主要參考孫智宏《數和數列》以及 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\lbrace0,1,2,\cdots,\alpha_i\rbrace$, 由於 $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*}$$

定理得證. $\square$

根據該定理, 由於 $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)$, 定理得證. $\square$

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$, 容易知道等式成立, 於是結論得證.