Lehmer's totient problem
{{Short description|Unsolved problem in mathematics}}
{{for|Lehmer's Mahler measure problem|Lehmer's conjecture}}
{{unsolved|mathematics|Can the totient function of a composite number divide ?}}
In mathematics, Lehmer's totient problem asks whether there is any composite number {{Mvar|n}} such that Euler's totient function {{Math|φ(n)}} divides {{Math|n − 1}}. This is an unsolved problem.
It is known that {{Math|1=φ(n) = n − 1}} if and only if {{Mvar|n}} is prime. So for every prime number {{Mvar|n}}, we have {{Math|1=φ(n) = n − 1}} and thus in particular {{Math|φ(n)}} divides {{Math|n − 1}}. D. H. Lehmer conjectured in 1932 that there are no composite numbers with this property.Lehmer (1932)
History
- Lehmer showed that if any composite solution {{Mvar|n}} exists, it must be odd, square-free, and divisible by at least seven distinct primes (i.e. {{Math|ω(n) ≥ 7}}). Such a number must also be a Carmichael number.
- In 1980, Cohen and Hagis proved that, for any solution {{Mvar|n}} to the problem, {{Math|n > 1020}} and {{Math|ω(n) ≥ 14}}.Sándor et al (2006) p.23
- In 1988, Hagis showed that if 3 divides any solution {{Mvar|n}}, then {{Math|n > 101{{px2}}937{{px2}}042}} and {{Math|ω(n) ≥ 298848}}.Guy (2004) p.142 This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if 3 divides any solution {{Mvar|n}}, then {{Math|n > 10360{{px2}}000{{px2}}000}} and {{Math|ω(n) ≥ 40{{px2}}000{{px2}}000}}.{{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 |pages=43–49}}
- A result from 2011 states that the number of solutions to the problem less than {{Mvar|X}} is at most {{Math|X1/2 / (log X)1/2 + o(1)}}.Luca and Pomerance (2011)
References
{{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 | 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 | 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 | 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 }}