萊默的歐拉函數問題

在數學上，萊默的歐拉函數問題（Lehmer's totient problem）指的是是否有合成數 $n$ ，其歐拉函數 $φ (n)$ 的值可整除 $n - 1$ 。這問題迄今仍未得證。

已知 $φ (n) = n - 1$ ，當且僅當 $n$ 是質數，故對於任何質數 $n$ 而言，有 $φ (n) = n - 1$ ，且 $φ (n)$ 可整除 $n - 1$ ；而德里克·亨利·萊默猜想說，沒有任何合成數 $n$ ，使得 $φ (n)$ 整除 $n - 1$ 。^[1]

歷史

萊默證明了說如果有這樣的合成數 $n$ ，那麼 $n$ 必然是奇數、必然是無平方因子數，且必然有至少七個不同的質因數（ $ω (n) \geq 7$ ）。此外這樣的數必然是個卡邁克爾數。
1980年，Cohen和Hagis證明了說，若這樣的 $n$ 存在，則 $n > 1 0^{20}$ 且 $n$ 有至少14個不同的質因數（ $ω (n) \geq 14$ ）。^[2]
1988年，Hagis證明了說若這樣的 $n$ 存在且可被3除盡，那麼 $n > 1 0^{1937042}$ 且 $n$ 有至少298848個不同的質因數（ $ω (n) \geq 298848$ ）。^[3]這結果之後為Burcsi、Czirbusz和Farkas改進，他們證明了說若的 $n$ 存在且可被3除盡，那麼 $n > 1 0^{360000000}$ 且 $n$ 有至少40000000個不同的質因數（ $ω (n) \geq 40000000$ ）。^[4]
一個2011年的結果顯示，這問題小於 $X$ 的解的數量至多有 $X^{1 / 2} / (\log X)^{1 / 2 + o (1)}$ 個。^[5]