萊默的歐拉函數問題

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

已知,當且僅當是質數,故對於任何質數而言,有,且可整除;而德里克·亨利·萊默猜想說,沒有任何合成數,使得整除[1]

歷史

  • 萊默證明了說如果有這樣的合成數 ,那麼 必然是奇數、必然是無平方因子數,且必然有至少七個不同的質因數( )。此外這樣的數必然是個卡邁克爾數
  • 1980年,Cohen和Hagis證明了說,若這樣的 存在,則  有至少14個不同的質因數( )。[2]
  • 1988年,Hagis證明了說若這樣的 存在且可被3除盡,那麼  有至少298848個不同的質因數( )。[3]這結果之後為Burcsi、Czirbusz和Farkas改進,他們證明了說若的 存在且可被3除盡,那麼  有至少40000000個不同的質因數( )。[4]
  • 一個2011年的結果顯示,這問題小於 的解的數量至多有 個。[5]

參考資料

  1. ^ Lehmer (1932)
  2. ^ Sándor et al (2006) p.23
  3. ^ Guy (2004) p.142
  4. ^ Burcsi, P. , Czirbusz,S., Farkas, G. Computational investigation of Lehmer's totient problem. Ann. Univ. Sci. Budapest. Sect. Comput. 2011, 35: 43-49. 
  5. ^ Luca and Pomerance (2011)