欧拉函数

欧拉函数（Euler's totient function），即 $\phi (n)$，表示的是小于等于 $n$ 和 $n$ 互质的数的个数.

比如说 $\phi (1)=1$, $\phi (2)=1$.

当 $n$ 是质数的时候，显然有 $\phi (n)=n-1$.

欧拉函数的性质

欧拉函数是积性函数

对任意满足 $\gcd (a,b)=1$ 的整数 $a,b$，有 $\phi (ab)=\phi (a)\phi (b)$.

特别地，当 $n$ 是奇数时 $\phi (2n)=\phi (n)$.

n 的约数的欧拉函数之和等于 n

$$n=\sum _{d\mid n}\phi (d)$$

证明 1

对于 $n$，定义以下数列

$$\frac{1}{n},\frac{2}{n},\dots ,\frac{n-1}{n},\frac{n}{n},$$

对每个分式进行通分，分母相同的作为一组. 分母只可能是 $n$ 的因子 $d$，即 $d\mid n$.

对于分母为 $d$ 的这一组分式，分子为 $1$ 和 $d$ 之间与 $d$ 互素的数，共有 $\phi (d)$ 个.

每组 $\phi (d)$ 个数，这些组加起来刚好是 $n$ 个数，即

$$n=\sum _{d\mid n}\phi (d)$$

证明 2

如果我们设 $f(d)$ 表示 $\gcd (k,n)=d$ 的数 $k$ 的个数，那么 $n={\sum }_{d\mid n}f(d)$.

给定数 $n$，对于数 $k$ ( $k<n$ ) 如果 $\gcd (k,n)=d$，那么 $\gcd (\frac{k}{d},\frac{n}{d})=1$.

$\phi (\frac{n}{d})$ 表示 $\gcd (\frac{k}{d},\frac{n}{d})=1$，$\frac{k}{d}$ 的数量，即 $\gcd (k,n)=d$，$k$ 的数量，即 $f(d)$.

所以 $f(d)=\phi (\frac{n}{d})$，从而 $n={\sum }_{d\mid n}\phi (\frac{n}{d})$. 注意到约数 $d$ 和 $\frac{n}{d}$ 具有对称性，所以上式化为 $n={\sum }_{d\mid n}\phi (d)$.

质数的 k 次方的欧拉函数

若 $n=p^k$，其中 $p$ 是质数，那么 $\phi (n)=p^k-p^{k-1}$

证明：根据定义可知.

小于等于 $n$ 的数有 $p^k$ 个. 其中与 $n$ 不互质的数有 $p,2p,3p,\dots ,p^{k-1}p$，共 $p^{k-1}$ 个. 其他数均与 $n$ 互质，有 $p^k-p^{k-1}$ 个. 故 $\phi (n)=p^k-p^{k-1}$.

欧拉定理

若 $\gcd (a,m)=1$，则 $a^{\phi (m)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}m)$.

详见 欧拉定理 词条.

分解 n

由唯一分解定理，设 $n={\prod }_{i=1}^s{p}_i^{k_i}$，其中 $p_i$ 是质数，有 $\phi (n)=n\times {\prod }_{i=1}^s\frac{p_i-1}{p_i}$。

参考

https://oi-wiki.org/math/number-theory/euler-totient/