Lehmer's totient problem

For Lehmer's Mahler measure problem, see Lehmer's conjecture.

Open problem in mathematics: Can the totient function of a composite number n divide n − 1? (more open problems in mathematics)

In mathematics, Lehmer's totient problem, named for D. H. Lehmer, asks whether there is any composite number n such that Euler's totient function φ(n) divides n − 1. This is true of every prime number, and Lehmer conjectured in 1932 that there are no composite solutions: he showed that if any such n exists, it must be odd, square-free, and divisible by at least seven primes (i.e. ω(n) ≥ 7). Such a number must also be a Carmichael number.

Properties

• 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^1937042 and ω(n) ≥ 298848.
• The number of solutions to the problem less than X is $O\left({X^{1/2}(\log X)^{3/4}}\right)$.

External links

• Weisstein, Eric W., "Lehmer's Totient Problem", MathWorld.

• Sándor et al (2006) p.23
• Guy (2004) p.142
• Sándor et al (2006) p.24