math.NT — Number Theory

Lehmer's totient problem with fewer than sixteen prime factors

Contributed by Deep Bhattacharjee

A composite number $n$ whose totient divides $n-1$ was known to have at least fourteen prime factors. We prove that it has at least sixteen, at least $16001$ if $(n-1)/\varphi(n)\ge3$, and more than $10^8$ if $3\mid n$, and that $n<2^{2^{k-7}}$ if $n$ has $k$ prime factors. For the companion equation $\varphi(n)\mid n+1$ we show that the nine known solutions are the only ones with at most eight prime factors, and that a further solution prime to $3$ has at least sixteen. Each statement is reduced by hand to a finite computation, which independent programs carry out. Lehmer's conjecture remains open, and we state the assertion that would settle it.