主題
Search

尤拉函式

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
TotientFunction

尤拉函式 phi(n)，也稱為尤拉φ函式，定義為小於或等於 <=n 且與 n 互質（即，沒有公因子）的正整數的數目，其中 1 被認為是與所有數字互質的。由於小於或等於給定數字且與該數字互質的數被稱為互質數，因此尤拉函式 phi(n) 可以簡單地定義為 n 的互質數的數目。例如，24 有八個互質數（1, 5, 7, 11, 13, 17, 19 和 23），所以 phi(24)=8。

尤拉函式在 Wolfram Language 中實現為EulerPhi[n]。

數字 n-phi(n) 被稱為 n 的非互質數，並給出小於或等於 <=n 且至少與 n 有一個公因子的正整數的數目。

phi(n) 對於 n>=3 總是偶數。按照慣例，phi(0)=1，儘管 Wolfram Language 將EulerPhi[0] 定義為等於 0，以便與其FactorInteger[0] 命令保持一致。phi(n) 對於 n=1, 2, ... 的前幾個值為 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, ... (OEIS A000010)。尤拉函式由 1, 2, 3, 4, ... 的莫比烏斯變換給出 (Sloane and Plouffe 1995, p. 22)。上面繪製了小 phi(n) 的 n 值。

對於素數 p,

phi(p)=p-1,
(1)

因為所有小於 p 的數都與 p 互質。如果 m=p^alpha 是素數的冪，那麼與 m 有公因子的數是 p 的倍數：p, 2p, ..., (p^(alpha-1))p。這些倍數有 p^(alpha-1) 個，所以與 p^alpha 互質的因子數目是

phi(p^alpha)=p^alpha-p^(alpha-1)
(2)
=p^(alpha-1)(p-1)
(3)
=p^alpha(1-1/p).
(4)

現在取一個一般 m，它可以被 p 整除。設 phi_p(m) 為小於或等於 <=m 且不被 p 整除的正整數的數目。和以前一樣，p, 2p, ..., (m/p)p 有公因子，所以

phi_p(m)=m-m/p
(5)
=m(1-1/p).
(6)

現在設 q 是另一個除 m 的素數。可被 q 整除的整數是 q, 2q, ..., (m/q)q。但是這些與 pq, 2pq, ..., (m/(pq))pq 重複。因此，為了從 phi_p 獲得 phi_(pq)，必須減去的項數為

Deltaphi_q(m)=m/q-m/(pq)
(7)
=m/q(1-1/p),
(8)

和

phi_(pq)(m)=phi_p(m)-Deltaphi_q(m)
(9)
=m(1-1/p)-m/q(1-1/p)
(10)
=m(1-1/p)(1-1/q).
(11)

透過歸納法，一般情況是

phi(n)=nproduct_(p|n)(1-1/p)
(12)
=n(1-1/(p_1))(1-1/(p_2))...(1-1/(p_r)),
(13)

其中乘積遍歷所有除 n 的素數 p。一個有趣的關於 phi(n^k) 與 phi(n) 的恆等式由下式給出

phi(n^k)=n^(k-1)phi(n)
(14)

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

另一個恆等式透過下式將 n 的除數 d 與 n 聯絡起來

sum_(d|n)phi(d)=n.
(15)

尤拉函式透過總和與莫比烏斯函式 mu(n) 相關聯

sum_(d)dmu(n/d)=phi(n),
(16)

其中總和是對 n 的除數求和，這可以透過對 n 的歸納法以及 mu(n) 和 phi(n) 是乘法函式這一事實來證明（Berlekamp 1968, pp. 91-93；van Lint and Nienhuys 1991, p. 123）。

尤拉函式具有狄利克雷生成函式

sum_(n=1)^infty(phi(n))/(n^s)=(zeta(s-1))/(zeta(s))
(17)

對於 s>2 (Hardy and Wright 1979, p. 250)。

尤拉函式滿足不等式

phi(n)>=sqrt(n)
(18)

對於所有 n，除了 n=2 和 n=6 (Kendall and Osborn 1965; Mitrinović and Sándor 1995, p. 9)。因此，phi(n)=2 的唯一 n 值是 n=3、4 和 6。此外，對於合數 n,

phi(n)<=n-sqrt(n)
(19)

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

TotientFunctionInequality

phi(n) 也滿足

liminf_(n->infty)phi(n)(lnlnn)/n=e^(-gamma),
(20)

其中 gamma 是尤拉-馬歇羅尼常數。使得 phi(n)<e^(-gamma)n/(lnlnn) 成立的 n 值由 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 22, ... (OEIS A100966) 給出。

除數函式滿足同餘式

nsigma(n)=2 (mod phi(n))
(21)
={0 (mod phi(n)) if phi(n)=2; 2 (mod phi(n)) otherwise
(22)

對於所有素數 p>=5 以及除了 4、6 和 22 之外的所有合數，其中 sigma(n) 是除數函式。Subbarao (1974) 證明了這個事實，儘管與此相反的暗示，“對於無限多個合數 n 成立嗎？” 在 Guy (1994, p. 92) 中提出，這個疑問隨後從 Guy (2004, p. 142) 中刪除。目前尚不清楚是否有合數解滿足

n-1=0 (mod phi(n))
(23)

(Honsberger 1976, p. 35)。

齊格蒙迪定理的一個推論導致以下同餘式，

phi(a^n+b^n)=0 (mod n)
(24)

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

使得

phi(n)=phi(n+1)
(25)

成立的前幾個 n 由 1, 3, 15, 104, 164, 194, 255, 495, 584, 975, ... (OEIS A001274) 給出，它們具有共同值 phi(n)=1, 2, 8, 48, 80, 96, 128, 240, 288, 480, ... (OEIS A003275)。

使得

phi(n)=phi(n+1)=phi(n+2)
(26)

成立的唯一 n<10^(10) 是 n=5186，給出

phi(5186)=phi(5187)=phi(5188)=2^53^4
(27)

(Guy 2004, p. 139)。

在彼此接近的 n 之間共享的 phi(n) 值包括

phi(25930)=phi(25935)=phi(25940)=phi(25942)
(28)
=2^73^4
(29)
phi(404471)=phi(404473)=phi(404477)
(30)
=2^83^25^27
(31)

(Guy 2004, p. 139)。McCranie 發現了一個由六個具有相等尤拉函式的陣列成的等差數列，

phi(583200)=phi(583230)=phi(583260)=phi(583290) =phi(583320)=phi(583350)=155520,
(32)

以及從 1166400, 1749600, ... (OEIS A050518) 開始的其他六個數的數列。

如果哥德巴赫猜想為真，那麼對於每個正整數 m，都存在素數 p 和 q 使得

phi(p)+phi(q)=2m
(33)

(Guy 2004, p. 160)。Erdős 詢問這是否適用於不一定是素數的 p 和 q，但這種寬鬆的形式仍未得到證實 (Guy 2004, p. 160)。

Guy (2004, p. 150) 討論了

phi(sigma(n))=n,
(34)

的解，其中 sigma(n) 是除數函式。F. Helenius 發現了 365 個這樣的解，其中第一個是 2, 8, 12, 128, 240, 720, 6912, 32768, 142560, 712800, ... (OEIS A001229)。

另請參閱

非互質數, 戴德金函式, 尤拉定理, 費馬小定理, 萊默尤拉函式問題, Leudesdorf 定理, 非非互質數, 非互質數, 西爾弗曼常數, 互質數, 尤拉函式求和函式, 尤拉函式價函式 在 課堂中探索這個主題

相關 Wolfram 站點

http://functions.wolfram.com/NumberTheoryFunctions/EulerPhi/

使用 探索

參考文獻

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 n for which phi(n)+1 Divides n." 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 phi 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 phi(n) Properly Divide n-1," "Solutions of phi(m)=sigma(n)," "Carmichael's Conjecture," "Gaps Between Totatives," "Iterations of phi and sigma," "Behavior of phi(sigma(n)) and sigma(phi(n))." §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 phi-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 phi 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.

在 上引用

尤拉函式

請引用本文為

Weisstein, Eric W. "尤拉函式。" 來自 Web 資源。 https://mathworld.tw/TotientFunction.html

主題分類