莱默的欧拉函数问题

在数学上，莱默的欧拉函数问题（Lehmer's totient problem）指的是是否有合成数$n$，其欧拉函数$\varphi (n)$的值可整除$n-1$。这问题迄今仍未得证。

已知$\varphi (n)=n-1$，当且仅当$n$是质数，故对于任何质数$n$而言，有$\varphi (n)=n-1$，且$\varphi (n)$可整除$n-1$；而德里克·亨利·莱默猜想说，没有任何合成数$n$，使得$\varphi (n)$整除$n-1$。

历史

• 莱默证明了说如果有这样的合成数$n$，那么$n$必然是奇数、必然是无平方因子数，且必然有至少七个不同的质因数（$\omega (n)\geq 7$）。此外这样的数必然是个卡迈克尔数。
• 1980年，Cohen和Hagis证明了说，若这样的$n$存在，则$n>10^{20}$且$n$有至少14个不同的质因数（$\omega (n)\geq 14$）。
• 1988年，Hagis证明了说若这样的$n$存在且可被3除尽，那么$n>10^{1937042}$且$n$有至少298848个不同的质因数（$\omega (n)\geq 298848$）。这结果之后为Burcsi、Czirbusz和Farkas改进，他们证明了说若的$n$存在且可被3除尽，那么$n>10^{360000000}$且$n$有至少40000000个不同的质因数（$\omega (n)\geq 40000000$）。
• 一个2011年的结果显示，这问题小于$X$的解的数量至多有${X^{1/2}/(\log X)^{1/2+o(1)}}$个。

参考资料

• Cohen, Graeme L.; Hagis, Peter, jun. On the number of prime factors of n if φ(n) divides n−1. Nieuw Arch. Wiskd. III Series. 1980, 28: 177–185. ISSN 0028-9825. Zbl 0436.10002. 
• Guy, Richard K. Unsolved problems in number theory 3rd. Springer-Verlag. 2004. B37. ISBN 0-387-20860-7. Zbl 1058.11001. 
• Hagis, Peter, jun. On the equation M⋅φ(n)=n−1. Nieuw Arch. Wiskd. IV Series. 1988, 6 (3): 255–261. ISSN 0028-9825. Zbl 0668.10006. 
• Lehmer, D. H. On Euler's totient function. Bulletin of the American Mathematical Society. 1932, 38 (10): 745–751. ISSN 0002-9904. Zbl 0005.34302. doi:10.1090/s0002-9904-1932-05521-5 . 
• Luca, Florian; Pomerance, Carl. On composite integers n for which $\varphi (n)\mid n-1$. Bol. Soc. Mat. Mexicana. 2011, 17 (3): 13–21. ISSN 1405-213X. MR 2978700. 
• Ribenboim, Paulo. The New Book of Prime Number Records 3rd. New York: Springer-Verlag. 1996. ISBN 0-387-94457-5. Zbl 0856.11001. 
• Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav (编). Handbook of number theory I. Dordrecht: Springer-Verlag. 2006. ISBN 1-4020-4215-9. Zbl 1151.11300. 
• Burcsi, Péter; Czirbusz, Sándor; Farkas, Gábor. Computational investigation of Lehmer's totient problem (PDF). Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. 2011, 35: 43–49 [2024-01-09]. ISSN 0138-9491. MR 2894552. Zbl 1240.11005. （原始内容存档 (PDF)于2024-01-09）.