欧拉函数（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）将欧拉函数域 代数 中的 环论 相结合，研究了整数环上的欧拉函数。
定义
欧拉函数是重要的 数论 函数之一。欧拉函数 表示所有不超过正整数 ，且与 互素 的正整数的个数。若 ， ， ， 等，为了计算需要，规定 。如果 自然数 的标准分解式为 ，则 或 ，特别地，当 为素数时，有 ， 。
相关概念
简化剩余系
设 为一正整数，在模 的所有不同简化剩余类中，从每个类任取一个数组成的整数的集合，叫模 的一个简化剩余系。欧拉函数简化剩余系定义为：设 为一正整数， ，且 ，则 是模 的一个简化剩余系。
积性函数
设 是定义在集合 上的整数的函数，并满足当 ， 时，有 ，则称 为积性函数。
性质
性质1
欧拉函数 是积性函数，但不是完全积性函数。
证明 ：因为 ，设 是 互素 的正整数。若 或 ，则有 。设 ， 分别是 的标准分解式。由于 互素 ，故 的标准分解式为
。又因为 ，所以 是积性函数，欧拉函数 是积性函数。
性质2
设 ，则 。
证明 ：首先，对任意素数 ，有 当且仅当 ，和 或 ，根据欧拉函数是积性函数得
。
性质3
设 为大于 的整数且其标准分解式为 ，则 。
证明： 根据其他性质可知 是积性函数，可通过如下性质证明。
根据 是积性函数， 为大于 的整数且其标准分解式为 ，则 。令 ，根据若 是素数， 是正整数，则 ，可 ，得到 。
性质4
设 为大于 的整数且其标准分解式为 ，则
性质5
用 表示不超过整数 且与 互素 的正整数（共 ）之和。
设 ，则 。
证明： 如果 ，那么 。设 ，则 ， ，从而有 。 ，即 ，所以 。设 为不超过 且与 互素 的正整数的全体，则
也是不超过 且与 互素的正整数的全体。于是
， 。把两个式子加在一起得 ，即 。
性质6
如果整数 ，则 。
性质7
如果整数 ，则 。
相关定理
欧拉-费马定理
设 ，则有 ，当 为素数时，对任意 有 。通常将 称为 费马小定理 ， 称为 欧拉 定理，因此，欧拉定理是费马小定理对于欧拉函数的推广。
证明 ：该定理的证明需要引入如下定理： ，那么 遍历模 的简化剩余系的 充分必要条件 是 遍历模 的简化剩余系。也就是说， 是模 的简化剩余系的充分必要条件是 是模 的简化剩余系。因此，取 是模 的一个既约剩余系，由以上定理可得，当 时， 是模 的一个既约剩余系。由 知， 。由于 ，利用 自然数 与整数性质，得 费马小定理 ，当 为素数时，由费马小定理和 ，得到 ， 。因此，对任意 有 。
非欧拉商数
非欧拉商数
不属于欧拉函数值域的偶数，即如果一个正偶数 所对应的欧拉方程 无解，那么这个数称为非欧拉 商数 。
结论与构造方法
所有能被 整除，但不能被 整除的非欧拉商数，都可以用通式 表出，其中 为奇素数， 为正整数。
构造以下非欧拉商数：
其中 。
前面一个数可以表示为 的素数减去 ，如 ，后面一个数是取这个素数的整数倍加 ，且加 后得到的数应为素数，也就是 ，其中 ，令要求 为素数。
广义欧拉函数
给定正整数 和 ， 关于 的广义欧拉函数定义为 ，即 等于不超过 且与 互质 的正整数的 个数 ，这里 表示不超过 的最大整数。
由此定义易证明 ，其中 为莫比乌斯函数（Möbius），即当 为不同的素数， 时，
该函数有一些与欧拉函数相似的基本性质，如 ，且 。同时，它还存在如下特殊结论。
结论1 ：若 ， 为正整数， 且 ，则 特别地，当 时， 。
结论2 ：若 为正整数， 且 ，则 。
应用
数学
欧拉函数在 数论 中可以用于著名猜想的证明，如哥德巴赫猜想。基本思想是，对于任意给定的 自然数 n，按大小顺序把比它小的自然数列出，划掉比它小的2的 倍数 ，再剩下数中划掉3的倍数，一直做下去，直到所有合数被划掉。欧拉函数 给出了一种特殊情形的 筛法 ，可以对任意连续的 自然数 段进行筛选，或者对 等差数列 中任意连续的自然数段进行筛除，可快速解决诸多素数问题。 比如利用欧拉函数证明素数有无穷个。
证明 ：设所有不同的素数为 ，并记 。设 ，若 ，则必有素数 使得 ，但 是所有素数之积，故也有 ，这表明 与 不 互素 。于是 中与 互素的仅有 ，从而 。另一方面，根据性质6得到 ，矛盾，证明完毕。
加密学
密码学是用来保护 信息安全 的一种必要手段，其中RSA算法是主流的公钥加密算法之一，它的算法是以欧拉函数的性质设计而来，该算法基于 数论 事实是：计算两个大素数的乘积是简单的，但是要将这个乘积进行 因式分解 是很难的。所以RSA算法 中将 两个大素数的乘积作为公钥进行公开，而这两个大素数则用来获取私钥，私钥是保密的。因此，RSA加密算法中，要用到素数、互素数、模运算以及欧拉函数等数学知识。
未解决问题
莱默的欧拉函数问题
莱默的欧拉函数问题是数论中的一个未解决问题，它询问是否存在合成数n使得φ(n)整除n - 1。目前已知如果这样的n存在，它必须是 奇数 、无平方因子数，并且有至少七个不同的质因数。
卡迈克尔猜想的欧拉函数猜想
卡迈克尔猜想的欧拉函数猜想认为不存在正整数n，使得对于所有其他的m而言，在m ≠ n的情况下必有φ(m) ≠ φ(n)。如果存在这样的 反例 ，那么必然有无限多的反例存在。
黎曼猜想
黎曼猜想 与欧拉函数有着密切的联系。黎曼猜想成立的一个必要条件是存在一个与n相关的 不等式 ，涉及到欧拉函数值与n的比值。
程式代码
C++
```cpp
template <typename T>
inline T phi(T n) {
T ans = n;
for (T i = 2; i * i <= n; ++i)
if (n % i == 0) {
ans = ans / i * (i - 1);
while (n % i == 0) n /= i;
}
if (n > 1) ans = ans / n * (n - 1);
return ans;
}
```