萊默的歐拉函數問題

在數學上，萊默的歐拉函數問題（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]