莱默的欧拉函数问题

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

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

历史

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