Lehmer's totient problem - Alchetron, the free social encyclopedia

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 ( X 1 / 2 ( log ⁡ X ) 3 / 4 ) .

References

Lehmer's totient problem Wikipedia

(Text) CC BY-SA