查看“︁萊默的歐拉函數問題”︁的源代码

{{unsolved|數學|是否有合成數<math>n</math>的歐拉函數的值可整除<math>n-1</math>？}}

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

已知<math>\varphi(n)=n-1</math>，當且僅當<math>n</math>是質數，故對於任何質數<math>n</math>而言，有<math>\varphi(n)=n-1</math>，且<math>\varphi(n)</math>可整除<math>n-1</math>；而[[德里克·亨利·萊默]]猜想說，沒有任何合成數<math>n</math>，使得<math>\varphi(n)</math>整除<math>n-1</math>。<ref>Lehmer (1932)</ref>

==歷史==
* 萊默證明了說如果有這樣的合成數<math>n</math>，那麼<math>n</math>必然是奇數、必然是[[無平方因子數]]，且必然有至少七個不同的質因數（<math>\omega(n)\ge7</math>）。此外這樣的數必然是個[[卡邁克爾數]]。
* 1980年，Cohen和Hagis證明了說，若這樣的<math>n</math>存在，則<math>n > 10^{20}</math>且<math>n</math>有至少14個不同的質因數（<math>\omega(n)\ge14</math>）。<ref name="HBI23">Sándor et al (2006) p.23</ref>
* 1988年，Hagis證明了說若這樣的<math>n</math>存在且可被3除盡，那麼<math>n > 10^{1937042}</math>且<math>n</math>有至少298848個不同的質因數（<math>\omega(n)\ge298848</math>）。<ref name=Guy142>Guy (2004) p.142</ref>這結果之後為Burcsi、Czirbusz和Farkas改進，他們證明了說若的<math>n</math>存在且可被3除盡，那麼<math>n > 10^{360000000}</math>且<math>n</math>有至少40000000個不同的質因數（<math>\omega(n)\ge40000000</math>）。<ref>{{cite journal |last1=Burcsi, P. , Czirbusz,S., Farkas, G. |title=Computational investigation of Lehmer's totient problem |journal=Ann. Univ. Sci. Budapest. Sect. Comput. |date=2011 |volume=35 |page=43-49}}</ref>
* 一個2011年的結果顯示，這問題小於<math>X</math>的解的數量至多有<math>{X^{1/2}/(\log X)^{1/2+o(1)}}</math>個。<ref name=LP2011>Luca and Pomerance (2011)</ref>

==參考資料==
{{reflist}}
* {{cite journal | zbl=0436.10002 | last1=Cohen | first1=Graeme L. | last2=Hagis | first2=Peter, jun. | title=On the number of prime factors of ''n'' if φ(''n'') divides ''n''−1 | journal=Nieuw Arch. Wiskd. |series=III Series | volume=28 | pages=177–185 | year=1980 | issn=0028-9825 }}
* {{cite book |last=Guy | first=Richard K. | authorlink=Richard K. Guy | title=Unsolved problems in number theory |url=https://archive.org/details/unsolvedproblems0003guyr | publisher=[[Springer-Verlag]] |edition=3rd | year=2004 |isbn=0-387-20860-7 | zbl=1058.11001 | at=B37}}
* {{cite journal | zbl=0668.10006 | last=Hagis | first=Peter, jun. | title=On the equation ''M''⋅φ(''n'')=''n''−1 | journal=Nieuw Arch. Wiskd. |series=IV Series | volume=6 | number=3 | pages=255–261 | year=1988 | issn=0028-9825 }}
* {{cite journal | last=Lehmer | first=D. H. | authorlink=Derrick Henry Lehmer | title=On Euler's totient function | journal=[[Bulletin of the American Mathematical Society]] | volume=38 | pages=745–751 | year=1932 | issue=10 | issn=0002-9904 | zbl=0005.34302 | doi=10.1090/s0002-9904-1932-05521-5| doi-access=free }}
* {{cite journal | last1=Luca | first1=Florian | last2=Pomerance | first2=Carl | title=On composite integers ''n'' for which <math>\varphi(n)\mid n-1</math> | journal=Bol. Soc. Mat. Mexicana | volume=17 | number=3 | pages=13–21 | year=2011 | issn=1405-213X | mr=2978700 | url=https://www.researchgate.net/publication/265577414 }}
*{{cite book | last1=Ribenboim  | first1=Paulo | authorlink=Paulo Ribenboim | edition=3rd | title=The New Book of Prime Number Records | url=https://archive.org/details/newbookofprimenu0000ribe  | publisher=[[Springer-Verlag]] | location=New York | year=1996 | isbn=0-387-94457-5 | zbl=0856.11001 }}
* {{cite book | editor1-last=Sándor | editor1-first=József | editor2-last=Mitrinović | editor2-first=Dragoslav S. | editor3-last=Crstici | editor3-first=Borislav | title=Handbook of number theory I | location=Dordrecht | publisher=[[Springer-Verlag]] | year=2006 | isbn=1-4020-4215-9 | zbl=1151.11300 }}
* {{cite journal | zbl=1240.11005 | mr=2894552 | last1=Burcsi | first1=Péter | last2=Czirbusz | first2=Sándor | last3=Farkas | first3=Gábor | title=Computational investigation of Lehmer's totient problem | url=http://ac.inf.elte.hu/Vol_035_2011/043.pdf | journal=Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. | volume=35 | pages=43–49 | year=2011 | issn=0138-9491 | access-date=2024-01-09 | archive-date=2024-01-09 | archive-url=https://web.archive.org/web/20240109062755/http://ac.inf.elte.hu/Vol_035_2011/043.pdf | dead-url=no }}

[[Category:猜想]]
[[Category:數論未解决問題]]
[[Category:積性函數]]