欧拉函数 在数论中，对正整数"n"，欧拉函数formula_1是小于等于"n"的正整数中与"n"互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。 例如，因为1、3、5和7均与8互质。 欧拉函数实际上是模"n"的同余类所构成的乘法群（即环formula_2的所有单位元组成的乘法群）的阶。这个性质与拉格朗日定理一起构成了欧拉定理的证明。 历史：欧拉函数与费马小定理. 1736年，欧拉证明了费马小定理： 假若 formula_3 为质数，formula_4 为任意正整数，那么 formula_5 可被 formula_3 整除。 然后欧拉予以一般化： 假若 formula_4 与 formula_8 互质，那么 formula_9 可被 formula_8 整除。亦即，formula_11。 其中 formula_1 即为欧拉总计函数。如果 formula_8 为质数，那么 formula_14，因此，有高斯的版本： 假若 formula_3 为质数，formula_4 与 formula_3 互质（formula_4 不是 formula_3 的倍数），那么 formula_20。 欧拉函数的值. 以下为formula_8 为formula_22至formula_23时，对应formula_1 的值 若formula_8有标准分解formula_26（其中各formula_27为互异的质因子，各formula_28为质因子的次数），则欧拉函数在该处的值为 formula_29 亦可等价地写成 formula_30 此结果可由formula_31在质数幂处的取值，以及其积性得到。 质数幂处取值. 最简单的情况有formula_32（小于等于1的正整数中唯一和1互质的数就是1本身）。 一般地，若"n"是质数"p"的"k"次幂，则formula_33，因为除了"p"的倍数外，其他数都跟"n"互质。 积性. 欧拉函数是积性函数，即是说若"m","n"互质，则formula_34。使用中国剩余定理有较简略的证明：设"A", "B", "C"是跟"m", "n", "mn"互质的数的集，据中国剩余定理，formula_35和formula_36可建立双射（一一对应）关系，因此两者元素个数相等。 较详细的证明如下： 设formula_37，且formula_38。若formula_39与formula_40互质，则formula_39与formula_42、formula_8均互质。又因为formula_44，若formula_45分别与formula_46互质，则formula_39一定和formula_40互质。反之亦然，即若formula_39与formula_40互质，则亦有formula_45分别与formula_46互质。 由中国剩余定理，方程组 formula_53 的通解可以写成formula_54 其中formula_55为固定的整数，故二元组formula_56（要满足formula_57）与小于formula_40且与formula_40互质的正整数formula_39一一对应。 由formula_31的定义（和乘法原理），前一种数对formula_56的个数为formula_63。而后一种数formula_39的个数为formula_65。 所以，formula_66 公式的证明. 结合以上两小节的结果可得：若formula_8有质因数分解式formula_68，则 -{zh-hant: formula_69; zh-hans: formula_70; 例子. 计算formula_71的欧拉函数值： formula_72 性质. "n"的欧拉函数formula_1 也是循环群 "C""n" 的生成元的个数（也是"n"阶分圆多项式的次数）。"C""n" 中每个元素都能生成 "C""n" 的一个子群，即必然是某个子群的生成元。而且按照定义，不同的子群不可能有相同的生成元。此外， "C""n" 的所有子群都具有 "C""d" 的形式，其中"d"整除"n"（记作"d" | "n"）。因此只要考察"n"的所有因数"d"，将 "C""d" 的生成元个数相加，就将得到 "C""n" 的元素总个数："n"。也就是说： formula_74 其中的"d"为"n"的正约数。 运用默比乌斯反转公式来“翻转”这个和，就可以得到另一个关于formula_1的公式： formula_76 其中 μ 是所谓的默比乌斯函数，定义在正整数上。 对任何两个互质的正整数"a", "m"（即 gcd("a","m") = 1），formula_77，有 formula_78 即欧拉定理。 这个定理可以由群论中的拉格朗日定理得出，因为任意与"m"互质的"a"都属于环 formula_2 的单位元组成的乘法群formula_80 当"m"是质数"p"时，此式则为： formula_20 即费马小定理。 欧拉商数. 欧拉商数（totient number）指的是欧拉函数的值，也就是说，若m是一个欧拉商数，那至少存在一个n，使得"φ"("n") "m"。而欧拉商数m的「重复度」（valency或multiplicity），指的是这等式的解数。相对地，一个非欧拉商数指的是不是欧拉商数的自然数。显然所有大于1的奇数都是非欧拉商数，此外也存有无限多的偶数是非欧拉商数，且所有的正整数都有一个倍数是非欧拉商数。 不大于x的欧拉商数个数可由以下公式给出： formula_82 其中"C" 0.8178146...。 考虑重复度，那么不大于x的欧拉商数个数可由以下公式给出： formula_83 其中对任意正数k而言，误差项R至多与成比例。 目前已知对于任意的"δ" m，其重复度超过"m""δ"。 Ford定理. "m"有刚好k个解。这结果由瓦茨瓦夫·谢尔宾斯基所猜测，且是的一个结果。事实上，对于任何出现的重复度而言，该重复度会出现无限多次。 然而，没有任何数字m的重复度为"k" 1。讲的是没有m的重复度为"k" 1。 完全欧拉商数. -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}- 完全欧拉商数（perfect totient number）是一个等同于其欧拉函数迭代总和的整数，也就是说，如果将欧拉函数套用在一个正整数formula_8之后，并将欧拉函数套用在如此所得的结果上，如此下去，直到最后得到1为止，并将这一系列的数给加总起来。若这总和为formula_8，那么formula_8就是一个完全欧拉商数。 生成函数. 以下两个由欧拉函数生成的级数都是来自于上节所给出的性质：formula_87。 由formula_31("n")生成的狄利克雷级数是： formula_89 其中ζ("s")是黎曼ζ函数。推导过程如下： formula_90 formula_91 formula_92 使用开始时的等式，就得到：formula_93 于是formula_94 欧拉函数生成的朗贝级数如下： formula_95 其对于满足 |"q"| 0，都有"n" > "N"(ε)使得 formula_101 如果考虑比值： formula_102 由以上已经提到的公式，可以得到其值等于类似formula_103的项的乘积。因此，使比值小的"n"将是两两不同的质数的乘积。由素数定理可以知道，常数 ε 可以被替换为： formula_104 formula_31就平均值的意义上来说是与"n"很相近的，因为： formula_106 其中的"O"表示大O符号。这个等式也可以说明在集合 {1, 2, ..., "n"} 中随机选取两个数，则当"n"趋于无穷大时，它们互质的概率趋于 formula_107 。一个相关的结果是比值formula_108的平均值： formula_109 formula_125 未解决问题. 莱默的欧拉函数问题. -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}- 若p是质数，则有"φ"("p") "p" − 1。1932年，德里克·亨利·莱默问说是否有合成数n使得"φ"("n")整除"n" − 1。目前未知是否有这样的数存在。 1933年莱默症明说若有这样的n,formula_8，那么formula_8必然是奇数、必然是无平方因子数，且必然有至少七个不同的质因数（formula_128）。1980年，Cohen和Hagis证明了说，若这样的formula_8存在，则formula_130且formula_8有至少14个不同的质因数（formula_132）；此外，Hagis证明了说若这样的formula_8存在且可被3除尽，那么formula_134且formula_8有至少298848个不同的质因数（formula_136）。 卡迈克尔猜想的欧拉函数猜想. -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}- 此猜想认为说不存在正整数n，使得对于所有其他的m而言，在"m" ≠ "n"的状况下必有"φ"("m") ≠ "φ"("n")。可见上述Ford定理一节的说明。 若有一个如此的反例存在，就必有无限多的反例存在，而最小的可能反例，在十进位下，其位数超过一百亿。 黎曼猜想. 黎曼猜想成立，当且仅当以下不等式对所有的"n" ≥ "p"120569#成立。此处的"p"120569#是最初的120569个质数的乘积： formula_137 此处的γ是欧拉常数。 程式代码. C++. template inline T phi(T n) { T ans = n; for (T i = 2; i * i 1) ans = ans / n * (n - 1); return ans;