欧拉函数（数论）

贡献者： int256

　　 考察一个数论函数，我们经常按素数——素数幂次——非零自然数的顺序去考察。先探讨前两个的性质。

　　 显然对于任意素数 $p$，其欧拉函数为 $\phi (p)=p-1$。

　　 对于一个素数幂次 $p^k$，可以想象在 $[1,p^k]$ 内每 $p$ 个数就有一个与 $p^k$ 不互素（有公因子 $p$）。也就是除去所有的 $p$ 的倍数，均与 $p^k$ 互质，故素数幂次的欧拉函数可以表示为 $\phi (p^k)=p^k(1-(1/p))$。

　　 证明：可以利用容斥原理： 不妨设 $n=\prod p_i^{k_i}$，$p_i$ 是 $n$ 的各素因子，$k_i$ 是其幂次。则有：

1. 不超过 $n$ 的是某个 $p_i$ 的倍数的分别有 $n/p_i$ 个。
2. 不超过 $n$ 的是某两 $p_i$ 的倍数的，也即是 $p_i{p}_j$ 的倍数（$i\ne j$）的，有 $n/(p_i{p}_j)$ 个。在上面重复计数，需要减去。
3. 不超过 $n$ 的是某三 $p_i$ 的倍数的，也即是 $p_i{p}_j{p}_k$ 的倍数（$i,j,k$ 互不相等），有 $n/(p_i{p}_j{p}_k)$ 个。在上面被减去了，没有计数到，需要加上。
4. 依此类推...
5. 不超过 $n$ 的是所有 $p_i$ 的倍数的，即 $\prod p_i$ 的，有 $n/(\prod p_i)$ 个。根据 $i$ 的奇偶性决定是要加上或减去。

　　 我们发现这表达式可以将欧拉函数表示为： $$\phi (n)=n-\sum (n/p_i)+\sum _{i\le j}(n/(p_i{p}_j))\cdots ,$$ 恰好与下面的展开式对应（之后默认的情况下忽略 $p_i|n$ 的条件不写）： $$\phi (n)=n\cdot \prod _i(1-\frac{1}{p_i}).$$ 这就是计算某任意数的欧拉函数的方法。

1. 积性函数

　　 证明： 回顾积性函数的定义，对于互质的 $n,m$，要求 $\phi (nm)=\phi (n)\phi (m)$。将 $n$、$m$ 的质因子列出，假设 $n$、$m$ 分别有质因子 $p_i$、$q_i$，则 $nm$ 的所有质因子为 $p_i,q_i$（$p_i\ne q_j,\mathrm{\forall }(i,j)$，因为 $n$ 与 $m$ 互质）。从而利用上面的推论 1 ，他们的积的欧拉函数可以表示为，

2. 缩系

　　 由欧拉函数的定义，我们可以立刻得知一个推论：

　　 证明可以直接考虑模仿完全剩余系时的情形，即定理 2 的证明。可以证明 $k{a}_i$ 之间两两不同余，而由于 $(k,m)=1$，各 $k{a}_i$ 必定都与 $m$ 互质，故他们取遍 $m$ 的一个缩系。