約數個數與約數和定理

約數個數定理:

約數個數=\(\displaystyle \prod^{k}_{i= 1} (a_i + 1)\)

證明：

由唯一分解定理\(n = p_1 ^{a_1} p_2 ^{a_2}p_3 ^{a_3}...p_k ^{a_k}\)可得:

\(n\)的約數一定是 \(p_1^{x} ... p_k^{z}\) \(x \in [0, a_1] ... z \in [0, a_k]\)

每一個可以取 \(a_i +１\)種可能.

根據乘法原理約數個數\(= (a_1 + 1) \ast (a_2 + 1) \ast ...\ast (a_k + 1)\).

即:

\[\displaystyle \prod^{k}_{i= 1} (a_i + 1)

\]

約數和定理

\(sum = \displaystyle \prod_{i =1}^n \sum_{j = 0}^{a_i}p_i^j\)

現将n質因數分解.

\(n = p_1^{a_1}p_2^{a_2}...p_k^{a_k}\)

則：其任意一因子p可表示為：

\(p=p_1^{b1}\times p_2^{b2}\times ... (0 =<b1<=a1,0=<b2<=a2,...)\)

根據乘法原理他們的和為：

\((p_1^0 +p_1^1 +…p_1^{a_1})(p_2^0 +p_2^1 +…p_2^{a_2})…(p_k^0+p_k^1 +…p_k ^{a_k})\)

是以sum = \(\displaystyle \prod_{i =1}^n \sum_{j = 0}^{a_i}p_i^j\)