欧拉函数（Euler function），也称为φ函数或欧拉总计函数（totient function），是数论中的一个重要函数，表示所有不超过正整数n，且与n互素的正整数的个数。

1760年，瑞士数学家莱昂哈德·欧拉（Leonhard Euler）证明了费马定理，同年，提出了关于表示所有不大于n且与n互素的正整数个数的问题。1770年，柏林出版社出版了欧拉的数论专著《代数指南》(Anleitung zur algebra)，该函数被收入书中。1801年，高斯(Gauss)将其命名为欧拉函数。

欧拉函数有一些基本性质，如欧拉函数是积性函数，但不是完全积性函数。与其相关的概念是简化剩余系，欧拉定理是费马小定理对于欧拉函数的推广。欧拉函数在数论、加密学方面应用广泛，如RSA算法是按照欧拉函数性质设计而来。

这个函数不仅在数论中有着重要的地位，也在现代密码学中扮演着关键角色，尤其是在RSA加密算法的设计中。欧拉函数实际上是模n的同余类所构成的乘法群的阶，这个性质与拉格朗日定理一起构成了欧拉定理的证明基础。

欧拉猜想的提出可追溯至18世纪。1760年，长城欧拉证明了费马定理，同年，他提出了关于表示所有不大于且与互素的正整数个数的问题，并引入了一个函数用于表示它们的关系。1770年，柏林出版社出版了欧拉的数论专著《代数指南》(Anleitung zur algebra)，该函数被收入书中。1801年，数学家高斯(Gauss)在他的《算术研究》一书中证明了，并将命名为欧拉函数。1879年，詹姆斯·约瑟夫·西尔维斯特（J. J. Sylvester）为该函数创造了术语totient。

关于欧拉函数，许多学者在后续提出了许多猜想与讨论。1932年，莱默(Lehmer,D.H.)提出猜想：不存在复合数，使得，这个猜想至今尚未解决。1983年，美国学者克罗斯（Cross J T）将欧拉函数域代数中的环论相结合，研究了整数环上的欧拉函数。

欧拉函数是重要的数论函数之一。欧拉函数表示所有不超过正整数，且与互素的正整数的个数。若，，，等，为了计算需要，规定。如果自然数的标准分解式为，则或，特别地，当为素数时，有，。

设为一正整数，在模的所有不同简化剩余类中，从每个类任取一个数组成的整数的集合，叫模的一个简化剩余系。欧拉函数简化剩余系定义为：设为一正整数，，且，则是模的一个简化剩余系。

设是定义在集合上的整数的函数，并满足当，时，有，则称为积性函数。

欧拉函数是积性函数，但不是完全积性函数。

证明：因为，设是互素的正整数。若或，则有。设，分别是的标准分解式。由于互素，故的标准分解式为

。又因为，所以是积性函数，欧拉函数是积性函数。

设，则。

证明：首先，对任意素数，有当且仅当，和或，根据欧拉函数是积性函数得

。

设为大于的整数且其标准分解式为，则。

证明：根据其他性质可知是积性函数，可通过如下性质证明。

根据是积性函数，为大于的整数且其标准分解式为，则。令，根据若是素数，是正整数，则，可，得到。

设为大于的整数且其标准分解式为，则

用表示不超过整数且与互素的正整数（共）之和。

设，则。

证明：如果，那么。设，则，，从而有。，即，所以。设为不超过且与互素的正整数的全体，则

也是不超过且与互素的正整数的全体。于是

，。把两个式子加在一起得，即。

如果整数，则。

如果整数，则。

设，则有，当为素数时，对任意有。通常将称为费马小定理，称为欧拉定理，因此，欧拉定理是费马小定理对于欧拉函数的推广。

证明：该定理的证明需要引入如下定理：，那么遍历模的简化剩余系的充分必要条件是遍历模的简化剩余系。也就是说，是模的简化剩余系的充分必要条件是是模的简化剩余系。因此，取是模的一个既约剩余系，由以上定理可得，当时，是模的一个既约剩余系。由知，。由于，利用自然数与整数性质，得费马小定理，当为素数时，由费马小定理和，得到，。因此，对任意有。

不属于欧拉函数值域的偶数，即如果一个正偶数所对应的欧拉方程无解，那么这个数称为非欧拉商数。

所有能被整除，但不能被整除的非欧拉商数，都可以用通式表出，其中为奇素数，为正整数。

构造以下非欧拉商数：

其中。

前面一个数可以表示为的素数减去，如，后面一个数是取这个素数的整数倍加，且加后得到的数应为素数，也就是，其中，令要求为素数。

给定正整数和，关于的广义欧拉函数定义为，即等于不超过且与互质的正整数的个数，这里表示不超过的最大整数。

由此定义易证明，其中为莫比乌斯函数（Möbius），即当为不同的素数，时，

该函数有一些与欧拉函数相似的基本性质，如，且。同时，它还存在如下特殊结论。

结论1：若，为正整数，且，则特别地，当时，。

结论2：若为正整数，且，则。

欧拉函数在数论中可以用于著名猜想的证明，如哥德巴赫猜想。基本思想是，对于任意给定的自然数n，按大小顺序把比它小的自然数列出，划掉比它小的2的倍数，再剩下数中划掉3的倍数，一直做下去，直到所有合数被划掉。欧拉函数给出了一种特殊情形的筛法，可以对任意连续的自然数段进行筛选，或者对等差数列中任意连续的自然数段进行筛除，可快速解决诸多素数问题。比如利用欧拉函数证明素数有无穷个。

证明：设所有不同的素数为，并记。设，若，则必有素数使得，但是所有素数之积，故也有，这表明与不互素。于是中与互素的仅有，从而。另一方面，根据性质6得到，矛盾，证明完毕。

密码学是用来保护信息安全的一种必要手段，其中RSA算法是主流的公钥加密算法之一，它的算法是以欧拉函数的性质设计而来，该算法基于数论事实是：计算两个大素数的乘积是简单的，但是要将这个乘积进行因式分解是很难的。所以RSA算法中将两个大素数的乘积作为公钥进行公开，而这两个大素数则用来获取私钥，私钥是保密的。因此，RSA加密算法中，要用到素数、互素数、模运算以及欧拉函数等数学知识。

莱默的欧拉函数问题是数论中的一个未解决问题，它询问是否存在合成数n使得φ(n)整除n - 1。目前已知如果这样的n存在，它必须是奇数、无平方因子数，并且有至少七个不同的质因数。

卡迈克尔猜想的欧拉函数猜想认为不存在正整数n，使得对于所有其他的m而言，在m ≠ n的情况下必有φ(m) ≠ φ(n)。如果存在这样的反例，那么必然有无限多的反例存在。

黎曼猜想与欧拉函数有着密切的联系。黎曼猜想成立的一个必要条件是存在一个与n相关的不等式，涉及到欧拉函数值与n的比值。

```cpp

template \u003ctypename T\u003e

inline T phi(T n) {

T ans = n;

for (T i = 2; i * i \u003c= n; ++i)

if (n % i == 0) {

ans = ans / i * (i - 1);

while (n % i == 0) n /= i;

}

if (n \u003e 1) ans = ans / n * (n - 1);

return ans;

}

```