積性函數

維基百科

• 定義：對於一個定義域在正整數的函數 $f(n)$，當 $a$ 和 $b$ 互質時 $f(ab)=f(a)f(b)$
• 例子 1：歐拉函數 $\phi(n)$
• 例子 2：最大公因數 $gcd(n,k)$，當 $k$ 固定時
• 性質 1：將 n 分解為質因數相乘，即 $n=p_1^{n_1}p_2^{n_2}p_3^{n_3}…p_k^{n_k}$，$f(n)=f(p_1^{n_1})f(p_2^{n_2})f(p_3^{n_3})…f(p_k^{n_k})$
• 性質 2：若 $f(p^n)=f^n(p)$，則 $f(n)$ 為完全積性函數

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)