Misplaced Pages

In mathematics, Lehmer's totient problem asks whether there is any composite number n such that Euler's totient function φ(n) divides n − 1. This is an unsolved problem.

It is known that φ(n) = n − 1 if and only if n is prime. So for every prime number n, we have φ(n) = n − 1 and thus in particular φ(n) divides n − 1. D. H. Lehmer conjectured in 1932 that there are no composite numbers with this property.

History

• Lehmer showed that if any composite solution n exists, it must be odd, square-free, and divisible by at least seven distinct primes (i.e. ω(n) ≥ 7). Such a number must also be a Carmichael number.
• In 1980, Cohen and Hagis proved that, for any solution n to the problem, n > 10 and ω(n) ≥ 14.
• In 1988, Hagis showed that if 3 divides any solution n, then n > 10 and ω(n) ≥ 298848. This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if 3 divides any solution n, then n > 10 and ω(n) ≥ 40000000.
• A result from 2011 states that the number of solutions to the problem less than ${\displaystyle X}$ is at most ${\displaystyle {X^{1/2}/(\log X)^{1/2+o(1)}}}$.

References

1. Lehmer (1932)
2. Sándor et al (2006) p.23
3. Guy (2004) p.142
4. Burcsi, P., Czirbusz, S., Farkas, G. (2011). "Computational investigation of Lehmer's totient problem". Ann. Univ. Sci. Budapest. Sect. Comput. 35: 43–49.{{cite journal}}: CS1 maint: multiple names: authors list (link)
5. Luca and Pomerance (2011)

• Cohen, Graeme L.; Hagis, Peter, jun. (1980). "On the number of prime factors of n if φ(n) divides n−1". Nieuw Arch. Wiskd. III Series. 28: 177–185. ISSN 0028-9825. Zbl 0436.10002.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. B37. ISBN 0-387-20860-7. Zbl 1058.11001.
• Hagis, Peter, jun. (1988). "On the equation M⋅φ(n)=n−1". Nieuw Arch. Wiskd. IV Series. 6 (3): 255–261. ISSN 0028-9825. Zbl 0668.10006.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• Lehmer, D. H. (1932). "On Euler's totient function". Bulletin of the American Mathematical Society. 38 (10): 745–751. doi:10.1090/s0002-9904-1932-05521-5. ISSN 0002-9904. Zbl 0005.34302.
• Luca, Florian; Pomerance, Carl (2011). "On composite integers n for which ${\displaystyle \varphi (n)\mid n-1}$". Bol. Soc. Mat. Mexicana. 17 (3): 13–21. ISSN 1405-213X. MR 2978700.
• Ribenboim, Paulo (1996). The New Book of Prime Number Records (3rd ed.). New York: Springer-Verlag. ISBN 0-387-94457-5. Zbl 0856.11001.
• Sándor, József; Mitrinović, Dragoslav S.; Crstici, Borislav, eds. (2006). Handbook of number theory I. Dordrecht: Springer-Verlag. ISBN 1-4020-4215-9. Zbl 1151.11300.
• Burcsi, Péter; Czirbusz, Sándor; Farkas, Gábor (2011). "Computational investigation of Lehmer's totient problem" (PDF). Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. 35: 43–49. ISSN 0138-9491. MR 2894552. Zbl 1240.11005.

• Conjectures
• Unsolved problems in number theory
• Multiplicative functions