正因數個數及正因數和

我們可以用 multiplicative arithmetic function 的概念很快的求出一正整數其正因數之個數及正因數和.

給定一正整數 n, 令 v(n) 表示 n 的正因數個數. 既然對任意 n $\in$ $\mathbb {N}$, v(n) 都有取值, 所以我們可以將其看成是一個函數 v : $\mathbb {N}$$\to$$\mathbb {N}$. 從函數的角度來看, v 就是一個 arithmetic function. 給定 n $\in$ $\mathbb {N}$ 如何求 v(n) 值呢? 直接的作法就是將 n 的正因數一一列出然後數有多少個. 例如 6 的正因數有 1, 2, 3, 6, 所以 v(6) = 4. 這樣的求法如何用式子表示呢? 我們可以善用 summation $\sum$ 的符號, 將 v(n) 寫成

v(n) = $$\sum_{d\vert n,d>0}^{}$$1.

上式的意思就是每次你看到 d 滿足 d| n 且 d > 0 就加一次, 所以很自然得到 n 的正因數個數.

Proposition 2.2.1   對任意 n $\in$ $\mathbb {N}$, 令 v(n) 表示 n 的正因數個數. 則 v : $\mathbb {N}$$\to$$\mathbb {N}$ 是一個 multiplicative arithmetic function. 而且若 n = p₁^{n₁ ...} p_r^n_r, 其中 p_i 為相異質數, 則 v(n) = (n₁ + 1) ^... (n_r + 1).

証 明. 若令 l : $\mathbb {N}$$\to$$\mathbb {N}$ 是一個 arithmetic function 滿足對任意 n $\in$ $\mathbb {N}$, l(n) = 1, 則 v(n) 可表為

v(n) = $$\sum_{d\vert n,d>0}^{}$$l(d ).

由於對任意 a, b $\in$ $\mathbb {N}$, l(ab) = l(a)l(b) = 1, 我們知 l 為 (completely) multiplicative. 因此由 Theorem 2.1.5 知 v 為 multiplicative.

既然 v 是 multiplicative, 我們可以利用 Proposition 2.1.3 求對任意 n $\in$ $\mathbb {N}$, v(n) 之值. 也就是說我們要先探討對任意質數 p 以及正整數 t, v(p^t) 之值. 由於 p^t 的正因數就是 pⁱ, 其中 i $\in$ {0, 1,..., t}, 我們得到 v(p^t) = t + 1. 因此對任意 n $\in$ $\mathbb {N}$, 若 n = 1, 我們知 v(n) = v(1) = 1; 而若 n = p₁^{n₁ ...} p_r^n_r 其中 p_i 為相異質數, 則由 v 是 multiplicative 知

v(n) = v(p₁^n₁) ^... v(p_r^n_r) = (n₁ + 1) ^... (n_r + 1).

$\qedsymbol$

舉例來說, 我們要求 360 的正因數個數, 由於 360 = 2^{3 .} 3^{2 .} 5, 利用 Proposition 2.2.1, 我們很快就可得 v(360) = (3 + 1)(2 + 1)(1 + 1) = 24. 從這裡大家應更能體會 multiplicative arithmetic function 的好處. 或許求 v(n) 的公式大家在高中時學排列組合時就用乘法原理得到過. 可以用乘法原理的原因其實就和 v 是 multiplicative 息息相關.

接下來我們探討正因數和. 給定一正整數 n, 令 $\sigma$(n) 表示 n 的所有正因數之和. 既然對任意 n $\in$ $\mathbb {N}$, $\sigma$(n) 都有取值, 所以我們可以將其看成是一個函數 $\sigma$ : $\mathbb {N}$$\to$$\mathbb {N}$. 從函數的角度來看, $\sigma$ 就是一個 arithmetic function. 給定 n $\in$ $\mathbb {N}$ 如何求 $\sigma$(n) 值呢? 直接的作法就是將 n 的正因數一一列出然後全部加起來. 例如 6 的正因數有 1, 2, 3, 6, 所以 $\sigma$(6) = 1 + 2 + 3 + 6 = 12. 這樣的求法如何用式子表示呢? 我們再一次善用 summation $\sum$ 的符號, 將 $\sigma$(n) 寫成

$$\sigma$$(n) = $$\sum_{d\vert n,d>0}^{}$$d.

上式的意思就是每次你看到 d 滿足 d| n 且 d > 0 就加 d, 所以很自然得到 n 的正因數和.

Proposition 2.2.2   對任意 n $\in$ $\mathbb {N}$, 令 $\sigma$(n) 表示 n 的正因數個數. 則 $\sigma$ : $\mathbb {N}$$\to$$\mathbb {N}$ 是一個 multiplicative arithmetic function. 而且若 n = p₁^{n₁ ...} p_r^n_r, 其中 p_i 為相異質數, 則

$$\sigma$$(n) = $${\frac{p_1^{n_1+1}-1}{p_1-1}}$$ ^... $${\frac{p_r^{n_r+1}-1}{p_r-1}}$$.

証 明. 若令 $\mathcal {I}$ : $\mathbb {N}$$\to$$\mathbb {N}$ 是一個 arithmetic function 滿足對任意 n $\in$ $\mathbb {N}$, $\mathcal {I}$(n) = n, 則 $\sigma$(n) 可表為

$$\sigma$$(n) = $$\sum_{d\vert n,d>0}^{}$$$$\mathcal {I}$$(d ).

由於對任意 a, b $\in$ $\mathbb {N}$, $\mathcal {I}$(ab) = ab = $\mathcal {I}$(a)$\mathcal {I}$(b), 我們知 $\mathcal {I}$ 為 (completely) multiplicative. 因此由 Theorem 2.1.5 知 $\sigma$ 為 multiplicative.

既然 $\sigma$ 是 multiplicative, 我們可以利用 Proposition 2.1.3 求對任意 n $\in$ $\mathbb {N}$, $\sigma$(n) 之值. 也就是說我們要先探討對任意質數 p 以及正整數 t, $\sigma$(p^t) 之值. 由於 p^t 的正因數就是 pⁱ, 其中 i $\in$ {0, 1,..., t}, 我們得到 $\sigma$(p^t) = 1 + p + ^... + p^t. 由於 1, p,..., p^t 是一個公比為 p 的等比數列, 我們得

$$\sigma$$(p^t) = $${\frac{p^{t+1}-1}{p-1}}$$.

因此對任意 n $\in$ $\mathbb {N}$, 若 n = 1, 我們知 $\sigma$(n) = $\sigma$(1) = 1; 而若 n = p₁^{n₁ ...} p_r^n_r 其中 p_i 為相異質數, 則由 $\sigma$ 是 multiplicative 知

$$\sigma$$(n) = $$\sigma$$(p₁^n₁) ^... $$\sigma$$(p_r^n_r) = $${\frac{p_1^{n_1+1}-1}{p_1-1}}$$ ^... $${\frac{p_r^{n_r+1}-1}{p_r-1}}$$.

$\qedsymbol$

舉例來說, 我們要求 360 的正因數和, 由於 360 = 2^{3 .} 3^{2 .} 5, 利用 Proposition 2.2.2, 我們很快就可得

$$\sigma$$(360) = $${\frac{2^4-1}{2-1}}$$$${\frac{3^3-1}{3-1}}$$$${\frac{5^2-1}{5-1}}$$ = 15 ^. 13 ^. 6 = 1170.