積性函數(shù)

• （積性函數(shù)）.
  如果算術(shù)函數(shù)$f$對任意兩個互素的正整數(shù)a和b，$f(ab)=f(a)f(b)$，則$f$被稱為積性函數(shù)（或乘性函數(shù)）；如果對任意兩個正整數(shù)a和b，$f(ab)=f(a)f(b)$，則$f$被稱為完全積性函數(shù)（或完全乘性函數(shù)）。

• $$\begin{gathered} 如果f是一個積性函數(shù)，n是一個正整數(shù)，且n有素冪因子分解 \\ n=p_1^{a_1}{p}_2^{a_2}...p_m^{a_m},則f(n)=f(p_1^{a_1})f(p_2^{a_2})...f(p_m^{a_m}). \end{gathered}$$

歐拉函數(shù)

• （歐拉函數(shù)$?(n)$）
  設(shè)$n$是一個正整數(shù)。歐拉$?$函數(shù)$?(n)$是不超過$n$且與$n$互素的正整數(shù)的個數(shù);
  如果$n$是素數(shù)，$?(n)=n?1$；如果n是合數(shù)，$?(n)<n?1$.

• （$?$函數(shù)公式）
  如果p是一個素數(shù)，且k是正整數(shù)，則$?(p^k)=p^k?p^{k?1}$。
  如果m和n是互素的正整數(shù)，$?(mn)=?(m)?(n)$。
  所以，$?(n)$是積性函數(shù)，但不是完全積性函數(shù)。

• （$?(n)$計算公式）
  如果$n$有素因子分解$n=p_1^{a_1}{p}_2^{a_2}...p_m^{a_m}$，那么有歐拉$?$函數(shù)$$?(n)=n?(1?\frac{1}{p_1})(1?\frac{1}{p_2})...(1?\frac{1}{p_m})$$

• （歐拉定理）
  如果$n$和$a$ 是互素的正整數(shù)，則$a^{?(n)}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}n$.

• （a模n的階）
  設(shè)a和n是互素的整數(shù)，a>=0，n>0。使得$a^x\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}n$成立的最小正整數(shù)x被稱為a模n的階，并記為$or{d}_{n}a$。

• （原根）
  設(shè)a和n是互素的整數(shù)，且n>0。如果$or{d}_{n}a=?(n)$，則稱a是模n的原根，并稱n有一個原根。

  如果正整數(shù)n有一個原根，那么它有$?(?(n))$個不同余的原根。

• (模$n$的既約剩余系)
  模n的既約剩余系是由$?(n)$個整數(shù)構(gòu)成的集合，集合中的每個元素均與$n$互素，且任何兩個元素模$n$不同余。

  定理：如果集合$\{r_1,r_2,\dots ,r_n\}$是一個模n的既約剩余系，并且$n$和$a$是互素的正整數(shù)，則集合$\{a?r_1,a?r_2,\dots ,a?r_n\}$也是一個模$n$的既約剩余系。

• 計算$\sum gcd(i,N)$
  首先，在從1到N的每個數(shù)中，如果$gcd(i,N)=p,（1<p\le N）$，則i/p和N/p互素，且滿足$gcd(i,N)=p$的i的個數(shù)是$?(N/p)$，所以，相應(yīng)的和為$p??(N/p)$。所以，要計算$\sum gcd(i,N)$，只需要根據(jù)gcd的值不同，分類進(jìn)行計算即可，$\sum gcd(i,N)={\sum }_{p|N}p??(N/p)$.

莫比烏斯函數(shù)

考慮非平方數(shù)的因子個數(shù)，$f$的和函數(shù)$F(n)={\sum }_{d|n}f(d)$.
由此可見，$f(n)$等于$\pm F(n/d)$之和。

• （莫比烏斯函數(shù)）
  $$\mu (n)=\begin{array}{r}?\begin{array}{lr}1& n=1\\ (?1{)}^m& n=p_1{p}_2...p_m,其中p_i為不同的素數(shù)\\ 0& 其他\end{array}\end{array}$$
• 定理：莫比烏斯函數(shù)$\mu (n)$是積性函數(shù)。、
• （莫比烏斯反演公式）
  設(shè)$f$是算術(shù)函數(shù)，$F$是$f$的和函數(shù)，$F(n)={\sum }_{d|n}f(d)$,則$f(n)={\sum }_{d|n}\mu (d)F(n/d)$。

總結(jié)

以上是生活随笔為你收集整理的积性函数欧拉函数莫比乌斯函数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。