欧拉函数

欧拉函数，也称为欧拉φ函数，定义为小于或等于且与互质（即，没有公因子）的正整数的数目，其中 1 被认为是与所有数字互质的。由于小于或等于给定数字且与该数字互质的数被称为互质数，因此欧拉函数可以简单地定义为的互质数的数目。例如，24 有八个互质数（1, 5, 7, 11, 13, 17, 19 和 23），所以。

欧拉函数在 Wolfram Language 中实现为EulerPhi[n]。

数字被称为的非互质数，并给出小于或等于且至少与有一个公因子的正整数的数目。

对于总是偶数。按照惯例，，尽管 Wolfram Language 将EulerPhi[0] 定义为等于 0，以便与其FactorInteger[0] 命令保持一致。对于 , 2, ... 的前几个值为 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, ... (OEIS A000010)。欧拉函数由 1, 2, 3, 4, ... 的莫比乌斯变换给出 (Sloane and Plouffe 1995, p. 22)。上面绘制了小的值。

对于素数 ,

(1)

因为所有小于的数都与互质。如果是素数的幂，那么与有公因子的数是的倍数：, , ..., 。这些倍数有个，所以与互质的因子数目是

			(2)
			(3)
			(4)

现在取一个一般，它可以被整除。设为小于或等于且不被整除的正整数的数目。和以前一样，, , ..., 有公因子，所以

			(5)
			(6)

现在设是另一个除的素数。可被整除的整数是 , , ..., 。但是这些与 , , ..., 重复。因此，为了从获得，必须减去的项数为

			(7)
			(8)

和

			(9)
			(10)
			(11)

通过归纳法，一般情况是

			(12)
			(13)

其中乘积遍历所有除的素数。一个有趣的关于与的恒等式由下式给出

(14)

(A. Olofsson，私人通信，2004 年 12 月 30 日)。

另一个恒等式通过下式将的除数与联系起来

(15)

欧拉函数通过总和与莫比乌斯函数相关联

(16)

其中总和是对的除数求和，这可以通过对的归纳法以及和是乘法函数这一事实来证明（Berlekamp 1968, pp. 91-93；van Lint and Nienhuys 1991, p. 123）。

欧拉函数具有狄利克雷生成函数

(17)

对于 (Hardy and Wright 1979, p. 250)。

欧拉函数满足不等式

(18)

对于所有，除了和 (Kendall and Osborn 1965; Mitrinović and Sándor 1995, p. 9)。因此，的唯一值是、4 和 6。此外，对于合数 ,

(19)

(Sierpiński 和 Schinzel 1988；Mitrinović 和 Sándor 1995, p. 9)。

也满足

(20)

其中是欧拉-马歇罗尼常数。使得成立的值由 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 22, ... (OEIS A100966) 给出。

除数函数满足同余式

			(21)
			(22)

对于所有素数以及除了 4、6 和 22 之外的所有合数，其中是除数函数。Subbarao (1974) 证明了这个事实，尽管与此相反的暗示，“对于无限多个合数成立吗？” 在 Guy (1994, p. 92) 中提出，这个疑问随后从 Guy (2004, p. 142) 中删除。目前尚不清楚是否有合数解满足

(23)

(Honsberger 1976, p. 35)。

齐格蒙迪定理的一个推论导致以下同余式，

(24)

(Zsigmondy 1882, Moree 2004, Ruiz 2004ab)。

使得

(25)

成立的前几个由 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (OEIS A001274) 给出，它们具有共同值 , 2, 8, 48, 80, 96, 128, 240, 288, 480, ... (OEIS A003275)。

使得

(26)

成立的唯一是，给出

(27)

(Guy 2004, p. 139)。

在彼此接近的之间共享的值包括

			(28)
			(29)
			(30)
			(31)

(Guy 2004, p. 139)。McCranie 发现了一个由六个具有相等欧拉函数的数组成的等差数列，

(32)

以及从 1166400, 1749600, ... (OEIS A050518) 开始的其他六个数的数列。

如果哥德巴赫猜想为真，那么对于每个正整数，都存在素数和使得

(33)

(Guy 2004, p. 160)。Erdős 询问这是否适用于不一定是素数的和，但这种宽松的形式仍未得到证实 (Guy 2004, p. 160)。

Guy (2004, p. 150) 讨论了

(34)

的解，其中是除数函数。F. Helenius 发现了 365 个这样的解，其中第一个是 2, 8, 12, 128, 240, 720, 6912, 32768, 142560, 712800, ... (OEIS A001229)。

另请参阅

非互质数, 戴德金函数, 欧拉定理, 费马小定理, 莱默欧拉函数问题, Leudesdorf 定理, 非非互质数, 非互质数, 西尔弗曼常数, 互质数, 欧拉函数求和函数, 欧拉函数价函数在 MathWorld 课堂中探索这个主题

使用 Wolfram|Alpha 探索

更多尝试

参考文献

Abramowitz, M. and Stegun, I. A. (Eds.). "The Euler Totient Function." §24.3.2 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 826, 1972.Beiler, A. H. Ch. 12 in Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, 1966.Berlekamp, E. R. Algorithmic Coding Theory. New York: McGraw-Hill, 1968.Cohen, G. L. and Segal, S. L. "A Note Concerning Those

for which

Divides

." Fib. Quart. 27, 285-286, 1989.Conway, J. H. and Guy, R. K. "Euler's Totient Numbers." The Book of Numbers. New York: Springer-Verlag, pp. 154-156, 1996.Courant, R. and Robbins, H. "Euler's

Function. Fermat's Theorem Again." §2.4.3 in Supplement to Ch. 1 in What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 48-49, 1996.Guy, R. K. Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, 1994.Guy, R. K. "Euler's Totient Function," "Does

Properly Divide

," "Solutions of

," "Carmichael's Conjecture," "Gaps Between Totatives," "Iterations of

and

," "Behavior of

and

." §B36-B42 in Unsolved Problems in Number Theory, 3rd ed. New York: Springer-Verlag, pp. 138-151, 2004.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, pp. 115-116, 2003.Helenius, F. Untitled. http://pweb.netcom.com/~fredh/phisigma/pslist.html.Honsberger, R. Mathematical Gems II. Washington, DC: Math. Assoc. Amer., p. 35, 1976.Jones, G. A. and Jones, J. M. "Euler's Function." Ch. 5 in Elementary Number Theory. Berlin: Springer-Verlag, pp. 83-96, 1998.Kendall, D. G. and Osborn, R. "Two Simple Lower Bounds for Euler's Function." Texas J. Sci. 17, 1965.Mitrinović, D. S. and Sándor, J. Handbook of Number Theory. Dordrecht, Netherlands: Kluwer, 1995.Moree, P. "Phi Function Congruence." 13 Oct 2004. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0410&L=nmbrthry&T=0&F=&S=&P=1222.Nagell, T. "Relatively Prime Numbers. Euler's

-Function." §8 in Introduction to Number Theory. New York: Wiley, pp. 23-26, 1951.Niven, I. M.; Zuckerman, H. S.; and Montgomery, H. L. An Introduction to the Theory of Numbers, 5th ed. New York: Wiley, p. 51, 1991.Perrot, J. 1811. Quoted in Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Dover, p. 126, 2005.Ruiz, S. "A Congruence With the Euler Totient Function." 11 Oct 2004a. http://arxiv.org/abs/math.GM/0410241.Ruiz, S. "Phi Function Congruence." 12 Oct 2004b. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0410&L=nmbrthry&T=0&F=&S=&P=834.Séroul, R. "The Euler Phi Function." §2.7 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 14-15, 2000.Shanks, D. "Euler's

Function." §2.27 in Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 68-71, 1993.Sierpiński, W. and Schinzel, A. Elementary Theory of Numbers, 2nd Eng. ed. Amsterdam, Netherlands: North-Holland, 1988.Sloane, N. J. A. Sequences A000010/M0299, A001229, A001274/M2999, A002088/M1008, A003275/M1874, A050518, and A100966 in "The On-Line Encyclopedia of Integer Sequences."Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego, CA: Academic Press, 1995.Subbarao, M. V. "On Two Congruences for Primality." Pacific J. Math. 52, 261-268, 1974.van Lint, J. H. and Nienhuys, J. W. Discrete Wiskunde.9062333680 Academic Service, 1991.Zsigmondy, K. "Zur Theorie der Potenzreste." Monatshefte für Math. u. Phys. 3, 265-284, 1882.

在 Wolfram|Alpha 上引用

欧拉函数

请引用本文为

Weisstein, Eric W. "欧拉函数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/TotientFunction.html

欧拉函数

另请参阅

相关 Wolfram 站点

使用 Wolfram|Alpha 探索

参考文献

在 Wolfram|Alpha 上引用

请引用本文为

主题分类