Lehmer's totient problem

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

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.

Unsolved problem in mathematics

Can the totient function of a composite number ${\displaystyle n}$ divide ${\displaystyle n-1}$?

More unsolved problems in mathematics

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^{1‍937‍042} and ω(n) ≥ 298848.^[3] This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if 3 divides any solution n, then n > 10^{360‍000‍000} and ω(n) ≥ 40‍000‍000.^[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]