萊默的歐拉函數問題

在數學上，萊默的歐拉函數問題（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)\ge7）。此外這樣的數必然是個卡邁克爾數。
• 1980年，Cohen和Hagis證明了說，若這樣的n存在，則n > 10^{20}且n有至少14個不同的質因數（\omega(n)\ge14）。
• 1988年，Hagis證明了說若這樣的n存在且可被3除盡，那麼n > 10^{1937042}且n有至少298848個不同的質因數（\omega(n)\ge298848）。這結果之後為Burcsi、Czirbusz和Farkas改進，他們證明了說若的n存在且可被3除盡，那麼n > 10^{360000000}且n有至少40000000個不同的質因數（\omega(n)\ge40000000）。
• 一個2011年的結果顯示，這問題小於X的解的數量至多有{X^{1/2}/(\log X)^{1/2+o(1)}}個。

參考資料
*
*
*
*
*
*
*
*