欧拉函数

欧拉函数（Euler's totient function），即 ，表示的是小于等于 和 互质的数的个数。

比如说 。

当 n 是质数的时候，显然有 。

欧拉函数是 积性函数。

即对任意满足 的整数 ，有 。

特别地，当 是奇数时 。

证明参见 剩余系的复合。

。

利用 莫比乌斯反演 相关知识可以得出。

也可以这样考虑：如果 ，那么 。

如果我们设 表示 的数的个数，那么 。

根据上面的证明，我们发现，，从而 。注意到约数 和 具有对称性，所以上式化为 。

若 ，其中 是质数，那么 。 （根据定义可知）

由唯一分解定理，设 ，其中 是质数，有 。

引理：设 为任意质数，那么 。

证明：显然对于从 1 到 的所有数中，除了 个 的倍数以外其它数都与 互素，故 ，证毕。

接下来我们证明 。由唯一分解定理与 函数的积性

对任意不全为 的整数 ，。

可由上一条直接计算得出。

如果只要求一个数的欧拉函数值，那么直接根据定义质因数分解的同时求就好了。这个过程可以用 Pollard Rho 算法优化。

注：如果将上面的程序改成如下形式，会提升一点效率：

如果是多个数的欧拉函数值，可以利用后面会提到的线性筛法来求得。 详见：筛法求欧拉函数

与欧拉函数紧密相关的一个定理就是欧拉定理。其描述如下：

若 ，则 。

当然也有扩展欧拉定理

证明和 习题 详见 欧拉定理