In mathematics, Lehmer's totient problem asks whether there is any composite number such that Euler's totient function divides . This is an unsolved problem.
It is known that if and only if is prime. So for every prime number , we have and thus in particular divides . D. H. Lehmer asked in 1932 whether there exist composite numbers with this property.
History Lehmer showed that if any composite solution exists, it must be odd, square-free, and divisible by at least seven distinct primes (i.e. ). Such a number must also be a Carmichael number. In 1980, Cohen and Hagis proved that, for any solution to the problem, and . In 1988, Hagis showed that if 3 divides any solution , then and . This was subsequently improved by Burcsi, Czirbusz, and Farkas, who showed that if 3 divides any solution , then and . A 2011 result of Luca and Pomerance states that the number of solutions to the problem less than is at most . In 2019 Burek and Żmija proved that any solution satisfies .
References