Lehmer's totient problem explained

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.^[1]

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.^[2]
• In 1988, Hagis showed that if 3 divides any solution n, then n > 10 and ω(n) ≥ .^[3] This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if 3 divides any solution n, then n > 10 and ω(n) ≥ .^[4]
• A result from 2011 states that the number of solutions to the problem less than

X is at most {X ^{1/2} /( log X) ^{1/2+o(1)} }.^[5]

References

• 0436.10002 . Cohen . Graeme L. . Hagis . Peter, jun. . On the number of prime factors of n if φ(n) divides n−1 . Nieuw Arch. Wiskd. . III Series . 28 . 177–185 . 1980 . 0028-9825 .
• Book: Guy, Richard K. . Richard K. Guy

. Richard K. Guy . Unsolved problems in number theory . . 3rd . 2004 . 0-387-20860-7 . 1058.11001 . B37.

• 0668.10006 . Hagis . Peter, jun. . On the equation M⋅φ(n)=n−1 . Nieuw Arch. Wiskd. . IV Series . 6 . 3 . 255–261 . 1988 . 0028-9825 .
• Lehmer . D. H. . Derrick Henry Lehmer . On Euler's totient function . . 38 . 745–751 . 1932 . 10 . 0002-9904 . 0005.34302 . 10.1090/s0002-9904-1932-05521-5. free .
• Luca . Florian . Pomerance . Carl . On composite integers n for which \varphi(n)\mid n -1 . Bol. Soc. Mat. Mexicana . 17 . 3 . 13–21 . 2011 . 1405-213X . 2978700 .
• Book: Paulo Ribenboim

. Ribenboim . Paulo . Paulo Ribenboim . 3rd . The New Book of Prime Number Records . . New York . 1996 . 0-387-94457-5 . 0856.11001 .

• Book: Sándor . József . Mitrinović . Dragoslav S. . Crstici . Borislav . Handbook of number theory I . Dordrecht . . 2006 . 1-4020-4215-9 . 1151.11300 .
• 1240.11005. 2894552 . Burcsi . Péter . Czirbusz . Sándor . Farkas . Gábor . Computational investigation of Lehmer's totient problem . Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Comput. . 35 . 43–49 . 2011 . 0138-9491 .

Notes and References

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)