What is the true status of the Lehmer totient problem?

586 Views Asked by At

The Lehmer-totient problem : For a prime number $\ n\ $ we have $\ \varphi(n)=n-1\ $. In particular, we have $\ \varphi(n) \mid n-1\ $. Is there a composite number $\ n\ $ with $\ \varphi(n)\mid n-1\ $ ?

It can easily be shown that such a number must be a Carmichael number.

What is the real status of this problem ?

I found some pages in the internet claiming a proof, but neither Wikipedia nor Mathworld consider this problem to be solved. The best lower bound is claimed to be $10^{22}$ in Mathworld, but Wikipedia still gives $10^{20}$ as the best bound. Which is true ? And is the problem solved or not ?

1

There are 1 best solutions below

6
On BEST ANSWER

A quick search through arXiv yields the following results:

(1) This proof for the Lehmer-totient problem has been withdrawn:

On the Lehmer's problem involving Euler's totient function (Huan Xiao)

(2) I highly doubt the validity of the following proof, although it is not yet withdrawn:

An analytical proof for Lehmer's totient conjecture using Mertens' theorems (Ahmad Sabihi)

Regarding the lower bounds for $n$ and $\omega(n)$ when $\varphi(n) \mid (n-1)$, I quote from the MathWorld website:

The best current result is $n > {10}^{22}$ and $\omega(n) \geq 14$, improving the ${10}^{20}$ lower bound of Cohen and Hagis (1980) - "On the Number of Prime Factors of $n$ is $\varphi(n) \mid (n-1)$", since there are no Carmichael numbers less than ${10}^{22}$ having $\geq 14$ distinct prime factors (Pinch).

When $3 \mid n$, then it is known that $$\omega(n) \geq 40000000$$ and $$n > {10}^{360000000}$$ by computational work of P. Burcsi, S. Czirbusz, and G. Farkas (2011).